I implemented a variation of this at Intel about 10 years ago to solve the efficient testing of microchips with different input/output pins on a limited-pin in/out tester. The goal was to efficiently load the chips in the tester to maximize utilization, with TT of each chip being the same. Fun times, heuristic-solving my way through the NP bin packing problem.
An interesting variation is Dynamic Storage Allocation, in which the rectangles can slide only alongside one axis.
AKA "static memory allocation", since the heights of the rectangles can be interpreted as buffer sizes, and their widths as lifetimes.
Most of my PhD's effort has been devoted to beating the SOTA in this. Problem's importance nowadays is owed to deep learning's memory wall.
nice! you have your thesis or any related paper available online?
You can probably get denser packing (at least in theory), if you allow rotation. It's just ugly:
https://kingbird.myphotos.cc/packing/squares_in_squares.html
I wonder how well Montecarlo works with a problem like this (for the online version), where you try all the potential places and run simulations adding new random boxes similar to the one added so far in order to see which option allows for better outcome. For sure it's slow, yet it should work well, which is interesting per-se since it would show once more how you can come up with slow but good solutions just simulating stuff. But likely, this is how this heuristics, like Skyline, were found: analyzing the properties of the brute-forced best picks.
They do this in subsets of aerodynamics for optimizing the tradeoff between simulation speed and fidelity in cases where there will be a lot of runs with the same geometry but different parameters
One of my first big personal programming projects was implementing this and a bunch of variations in python many years ago: https://github.com/solomon-b/greedypacker
Its still my most starred repo. :shrug:
Nice, I didn’t know stb had a rect packer: https://github.com/nothings/stb/blob/master/stb_rect_pack.h
Great writeup. Sucks when this gets asked in a coding interview to be solved in 15min :)
To be fair, in an interview context they’re probably looking for what you would implement in the mvp just to avoid getting blocked, and a brief acknowledgement that it’s an academic problem and once you have data to understand it better you’ll select and implement an appropriate algorithm after design review with colleagues.
If you're printing randomly sized rectangles and want to cut them apart with a guillotine paper cutter, then the algorithm can be much simpler: https://github.com/trathborne/guillot
This blog post references https://github.com/juj/RectangleBinPack/blob/master/Rectangl... ( and implicitly https://github.com/juj/RectangleBinPack/ ) as it's primary source.
The README even mentions the guillotine algorithm / method that someone else posted (not the same link, but the same method).
Very fun. I wonder if a heap could improve the performance of the "loop through the skyline in order to find the best candidate location" step. (I think it would improve the asymptotic time, if I'm understanding the algorithm correctly, but obviously the real performance is more complex).
With some clever bit twiddling hacks, you might be able to avoid the loop entirely.
Fun write up, kudos!
At a glance, this feels like a good case for an exact cover algorithm. Would be neat to see how that compares, here.
Can't wait to ask this one as a Leetcode warmup.
Yeah, that algorithm is pretty good.
BTW, when I needed it, I have ported C algorithm from fontstash library to C++: https://github.com/Const-me/nanovg/blob/master/src/FontStash...
Is this an algorithm in the family of "2D bin packing"?
As for packing sprites for games... I remember the fun on very constrained devices where many of the sprites where actually more round than square. So it was about packing both rectangles (for tiles and "rectangle" sprites) and packing circles too. The size of the spritesheet had to be kept small but in memory things were okay'ish (as in: a "round" sprite could be extracted from the spritesheet in its own rectangle).
Thankfully thing is: this can be done with a much more powerful machine than the device the sprite sheet shall eventually be on.
This looks useful for auto-placing parts inside a PCB.
Packing has so many applications for different things. Such as optimal packing of a truck or shipping container. Or how to optimally pack graphics into a GPU texture.
I had this guy as a prof. https://en.wikipedia.org/wiki/David_A._Klarner I have never encountered someone so excited about dividing up rectangles, as it is related to combinatorics. Also with such a seething hatred for floating point numbers.
Packing things into a GPU texture is probably the #1 most common use. If you played a game today then your computer probably spent some time packing rectangles into rectangles.
Your web browser may have also spent some time packing rectangles into rectangles. I recall reading this article a while back about how Firefox does/did it.
https://mozillagfx.wordpress.com/2021/02/04/improving-textur...
That’s great; I’d forgotten about it.
Plus there are a fair few programs that render text by rendering the font into a texture atlas once and then using the GPU to copy from the atlas. Your terminal emulator may be doing this, for example.
Hell, I needed something like this when working on my Halloween costumes this year!
3d printing build plate optimalisation, passenger transport, real estate plot division. Let's make this list longer?
A long time ago, some websites used to pack their images and use css to display a piece of the larger image. It reduced the number of round trips by not having to fetch a bunch of small files.
This "sprite sheet" style hack is still used sometimes.
I guess it's not really that necessary now that most sites load 25MB of JavaScript and a 250MB video that plays onload.
HTTP/2's multiplexing is probably the main reason we don't need sprite sheets anymore. I guess icon fonts are the modern sprite sheet to some degree.
There are all sorts of application for this. E.g. optimally cutting carpets from rolls of carpet. It is a variant on the 2D knapsack problem, one of the classic operational research problems: https://en.wikipedia.org/wiki/Knapsack_problem
The knapsack problem gets much harder as you increase the dimensions.
Placing parts on a PCB is harder if you have to care about where the components go relative to each other (e.g. because they have to be electrically connected, a certain distance from ink marking or drill holes, due to thermal or interference issues etc) rather than just optimizing space used.