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.