Algorithm needed for packing rectangles in a fairly optimal way

Question

Ive got a bunch of rectangular objects which I need to pack into the smallest space possible (the dimensions of this space should be powers of two).

I'm aware of various packing algorithms that will pack the items as well as possible into a given space, however in this case I need the algorithm to work out how large that space should be as well.

Eg say Ive got the following rectangles

• 128*32
• 128*64
• 64*32
• 64*32

They can be packed into a 128*128 space

 _________________
|128*32          |
|________________|
|128*64          |
|                |
|                |
|________________|
|64*32  |64*32   |
|_______|________|

However if there was also a 160*32 and a 64*64 one it would need a 256*128 space

 ________________________________
|128*32          |64*64  |64*32  |
|________________|       |_______|
|128*64          |       |64*32  |
|                |_______|_______|
|                |               |
|________________|___            |
|160*32              |           |
|____________________|___________|

What algorithms are there that are able to pack a bunch of rectangles and determine the required size for the container (to a power of 2, and within a given maximum size for each dimension)?

Answer 1

I'm fairly certain that this is a NP problem, so you'd have to implement a backtracking algorithm that tries every possible combination. The good news is that because of the need to pack 2D rectangles in a limited 2D space, you can prune a lot of possibilities early on, so it might not be THAT bad.

Answer 2

Have a look at packing problems. I think yours falls under '2D bin packing.' You should be able to learn a lot from solutions to that and other packing problems.

Also see: Packing rectangular image data into a square texture.

Answer 3

A general solution is non-trivial (math speak for completely ****ing impossible)
Generally people use a genetic algorithm to try possible combinations but you can do reasonably well by justing putting the largest shape in first and then trying different places for the next largest and so on.

Answer 4

The quick and dirty first pass solution is always a great one to start with, as a comparison if nothing else.

Greedy placement from large to small.

Put the largest rectangle remaining into your packed area. If it can't fit anywhere, place it in a place that extends the pack region as little as possible. Repeat until you finish with the smallest rectangle.

It's not perfect at all but it's easy and a nice baseline. It would still pack your original example perfectly, and give you an equivalent answer for the second as well.

Answer 5

This sounds like a university problem. I don't know what your time constraints are or how big your problem size is but you can look at the textbook solution for the Knapsack problem (it is 1d but related). Your packing problem can be solved for small cases with branch and bound: - come up with a way to bound the best area you can pack your shapes into - find an iterator which branches overall possible ways to pack them - if your bound tells you that the best solution you can find from a current branch is worse than a solution you already have, cut the search.

Answer 6

There is extensive literature on this problem. A good greedy heuristic is to place rectangles from largest area to smallest in the first available position towards the bottom and left of the container. Think of gravity pulling all of the items down to the lower left corner. For a description of this google "Chazelle bottom left packing".

For optimal solutions, the state-of-the-art techniques can pack over 20 rectangles in a few seconds. Huang has an algorithm that separates the problem of finding the smallest enclosing bounding box from the problem of deciding whether or not a set of rectangle can fit in a bounding box of a specific size. You give his program a set of rectangles, and it tells you the smallest enclosing bounding box required to pack them.

For your case, your outer loop should iterate from the smallest possible bounding box upward (with the width and height successively increasing by powers of two). For each of these bounding boxes, test to see if you can find a packing for your rectangles. You will get a bunch of "no" answers, until the first "yes" answer, which will be guaranteed to be the optimal solution.

For the inner loop of your algorithm -- the one that answers "yes" or "no" to a bounding box of specific size, I would look up the Huang reference and just implement his algorithm. He includes a lot of optimizations on top of the basic algorithm, but you only really need the basic meat and potatoes. Since you want to handle rotations, at every branch point during your search, simply try both rotations and backtrack when both rotations do not result in a solution.