Stacking rectangles to take as little space as possible

Question

Hello there

I have a program that will calculate the minimal area taken by fitting rectangles together.

Input: Rectangles of different height and width.
Output: One rectangle that contains all these rectangles.
Rules: One cannot turn or roll the rectangles around and they cannot overlap.

I understand that this is related or is possibly defined as a bin packing problem (NP-hard). However the algorithms i found for those often set a limit on for example width. I have no such limits, the only goal is to get the resulting area as small as possible.

Any pointers on what algorithm is appropriate to get a decent solution?

Answer 1

I'd start by skimming through http://mathworld.wolfram.com - they're awesome for stuff like this.

Second, I could envision a dopey algorithm that would put the longest (in the X dimension) box on the bottom, then the tallest (in the Y dimension) on top of it on one side or the other. Then continue stacking them in this "stair-stepped" fashion going right wards and upwards (for example go right until you can't, then go up, etc, etc).

That's probably non-ideal, and may very well give you bad results, but it's what popped to mind first.

Answer 2

I'd recommend starting with a simple greedy approach, and seeing if that is good enough for your needs. If your input is well-behaved or small, that may be all you need--and the complexity will go up quickly when you try to do something more sophisticated.

For example: sort the rectangles by size, largest first. Add the rectangles one at a time, trying each possible position for the new rectangle. Pick the position that results in the smallest bounding box.

Another greedy approach would be to pick a starting rectangle, then repeatedly add the rectangle which results in the most dense arrangement (where density is defined as the percentage of the bounding box's area that is filled).

Answer 3

http://www-rcf.usc.edu/~skoenig/icaps/icaps04/icapspapers/ICAPS04KorfR.pdf

Apparently this problem is harder than it looks at first. It's an interesting algorithm, since first it guesses a solution and then improves on it, so if you don't want to wait for the optimal solution, you can just run it for a set number of iterations to get an approximate solution (the longer you run it, the better the approximation).