Possible Duplicate:
Algorithm needed for packing rectangles in a fairly optimal way
I have N rectangles, each of a random size (random width & height). All rectangles are parallel to the X & Y axes. I'm looking for an algorithm that helps me arrange these rectangles side-by-side in a way that the resulting bounding rectangle has minimum area and the potential gaps around / between the input rectangles are as small as possible. Rectangles cannot be rotated and may not overlap each other.
(I need these to automate the arrangement of game sprites so I can create sprite sheets and save sprite locations from the various images I get from animators.)
For example:
+---+ +----------+
| 1 | | 2 |
+---+ +----------+ +----------+.. +---+----------+
| 2 |.. | 1 | 2 |
+--------+ ===> +--------+-+-+ vs +---+----+-----+
| | | | 1 | | |......
| 3 | | 3 +---+ | 3 |......
+--------+ +--------+.... +--------+......
Unused: 8 Unused: 18
Unused space is marked by the dots (.) in the drawing. Since the first result has a bounding rectangle with smaller unused space, it'd be preferable to find this arrangement of the input rectangles.
Is there an algorithm already that helps with this? I did a lot of googling but most results are related to finding minimum bounding rectangle or to finding if N rectangles cover a pre-determined area.
The solution suggested at What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way? looks nice, but I would change it slightly: Rather than greedily extend the bounding box by the smallest area, greedily extend it to the smallest area leaving space greater than the area used by the remaining rectangles. Also, select the next rectangle by greatest dimension, not greatest area.
That should give it more room early on, and prevent it from always running out of space at the last minute and leaving a mostly-empty margin.