Nice, I didn’t know stb had a rect packer: https://github.com/nothings/stb/blob/master/stb_rect_pack.h
The standard heuristic any 2D packing algorithm starts with is left-bottom or bottom-left (the choice is symmetrical). Place a piece as much to the left as possible, and among equal choicse as low as possible (or vice versa, as the choice was in the linked article). From this base heuristic, further meta-heuristics can be developed with choices for the order to pack parts, how to choose among "almost equal" positions, choosing among rotations and symmetries, and so on.
As far as I can tell, the "Skyline algorithm" is bottom-left with the limitation that created holes can not be packed. This doesn't feel like a packing algorithm as much as it feels like a heuristic to speed up position finding.
Great writeup. Sucks when this gets asked in a coding interview to be solved in 15min :)
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.
I wonder how good random placement would work.
IE :
Create a number of compositions where you put everything in random locations.
Discard any compositions with overlaps.
Keep the ones with the smallest wasted space or whatever.
Also, this might be a good application for AI.
There is a machine in a certain wood window manufacturer's plant that I have toured, which uses lasers to measure odd pieces of wood and then table saws to cut them into necessary sized pieces, minimizing waste - even cuts for fingerjoints - it all happens on a moving belt, and it happens extremely fast and in real-time. I was impressed. Probably powered by something like this algorithm (or the MAXRECTS one)
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.
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:
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
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 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).
I always thought this was called the Tetris packing algorithm. Because you drop in pieces from the top like in a game of Tetris. (no sliding in sideways allowed :))
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).
Can't wait to ask this one as a Leetcode warmup.
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.
This looks useful for auto-placing parts inside a PCB.
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...
[dead]
[dead]
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.