What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible 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)?

Solution 1

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.

Solution 2

See this page on the ARC project for a survey of solutions, there is a trade-off between implementation complexity/time and optimality, but there is a wide range of algorithms to choose from.

Here's an extract of the algorithms:

1. First-Fit Decreasing Height (FFDH) algorithm
   FFDH packs the next item R (in non-increasing height) on the first level where R fits. If no level can accommodate R, a new level is created.
   Time complexity of FFDH: O(n·log n).
   Approximation ratio: FFDH(I)<=(17/10)·OPT(I)+1; the asymptotic bound of 17/10 is tight.

2. Next-Fit Decreasing Height (NFDH) algorithm
   NFDH packs the next item R (in non-increasing height) on the current level if R fits. Otherwise, the current level is "closed" and a new level is created.
   Time complexity: O(n·log n).
   Approximation ratio: NFDH(I) <= 2·OPT(I)+1; the asymptotic bound of 2 is tight.

3. Best-Fit Decreasing Height (BFDH) algorithm
   BFDH packs the next item R (in non-increasing height) on the level, among those that can accommodate R, for which the residual horizontal space is the minimum. If no level can accommodate R, a new level is created.

4. Bottom-Left (BL) Algorithm
   BL first order items by non-increasing width. BL packs the next item as near to the bottom as it will fit and then as close to the left as it can go without overlapping with any packed item. Note that BL is not a level-oriented packing algorithm.
   Time complexity: O(n^2).
   Approximation ratio: BL(I) <= 3·OPT(I).

5. Baker's Up-Down (UD) algorithm
   UD uses a combination of BL and a generalization of NFDH. The width of the strip and the items are normalized so that the strip is of unit width. UD orders the items in non-increasing width and then divides the items into five groups, each with width in the range (1/2, 1], (1/3,1/2], (1/4,1/3], (1/5,1/4], (0,1/5]. The strip is also divided into five regions R1, ··· , R5. Basically, some items of width in the range (1/i+1, 1/i], for 1 <= i <= 4, are packed to region Ri by BL. Since BL leaves a space of increasing width from top to bottom at the right side of the strip, UD takes this advantage by first packing the item to Rj for j = 1, ··· , 4 (in order) from top to bottom. If there is no such space, the item is packed to Ri by BL. Finally, items of size at most 1/5 are packed to the spaces in R1, ··· , R4 by the (generalized) NFDH algorithm. Again if there is no space in these regions, the item is packed to R5 using NFDH.
   Approximation ratio: UD(I) <= (5/4) · OPT(I)+(53/8)H, where H is the maximum height of the items; the asymptotic bound of 5/4 is tight.

6. Reverse-fit (RF) algorithm
   RF also normalizes the width of the strip and the items so that the strip is of unit width. RF first stacks all items of width greater than 1/2. Remaining items are sorted in non-increasing height and will be packed above the height H0 reached by those greater than 1/2. Then RF repeats the following process. Roughly speaking, RF packs items from left to right with their bottom along the line of height H0 until there is no more room. Then packs items from right to left and from top to bottom (called reverse-level) until the total width is at least 1/2. Then the reverse-level is dropped down until (at least) one of them touches some item below. The drop down is somehow repeated.
   Approximation ratio: RF(I) <= 2·OPT(I).

7. Steinberg's algorithm
   Steinberg's algorithm, denoted as M in the paper, estimates an upper bound of the height H required to pack all the items such that it is proved that the input items can be packed into a rectangle of width W and height H. They then define seven procedures (with seven conditions), each to divide a problem into two smaller ones and solve them recursively. It has been showed that any tractable problem satisfies one of the seven conditions.
   Approximation ratio: M(I) <= 2·OPT(I).

8. Split-Fit algorithm (SF) SF divides items into two groups, L1 with width greater than 1/2 and L2 at most 1/2. All items of L1 are first packed by FFDH. Then they are arranged so that all items with width more than 2/3 are below those with width at most 2/3. This creates a rectangle R of space with width 1/3. Remaining items in L2 are then packed to R and the space above those packed with L1 using FFDH. The levels created in R are considered to be below those created above the packing of L1.
   Approximation ratio: SF(I) <= (3/2) ·OPT(I) + 2; the asymptotic bound of 3/2 is tight.

9. Sleator's algorithm
   Sleater's algorithm consists of four steps:

   1. All items of width greater than 1/2 are packed on top of one another in the bottom of the strip. Suppose h0 is the height of the resulting packing All subsequent packing will occur above h0.

   2. Remaining items are ordered by non-increasing height. A level of items are packed (in non-increasing height order) from left to right along the line of height h0.

   3. A vertical line is then drawn in the middle to cut the strip into two equal halves (note this line may cut an item that is packed partially in the right half). Draw two horizontal line segments of length one half, one across the left half (called the left baseline) and one across the right half (called the right baseline) as low as possible such that the two lines do not cross any item.

   4. Choose the left or right baseline which is of a lower height and pack a level of items into the corresponding half of the strip until the next item is too wide.

   A new baseline is formed and Step (4) is repeated on the lower baseline until all items are packed.
   Time complexity: O(n ·log n).
   The approximation ratio of Sleator's algorithm is 2.5 which is tight.

Solution 3

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.

Solution 4

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.

Solution 5

I'm fairly certain that this is an NP-hard problem, so, for an optimal solution, 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.

View more solutions

Comments

[Mantas Vidutis]

Isn't the second solution not optimal? Shouldn't it be 128 by 224?

[Carmen]

"the dimensions of this space should be powers of two" So it makes no difference, for what this was/is for I can not assume non-power of two is supported unconditionally by the underlying hardware.

[Carmen]

Anyway it made the algorithm simpler in the end(try to fit it all in 32x32, if nto then try 64x32, then 64x64, 128x64, etc) :)

[Jim Balter]

See jair.org/media/3735/live-3735-6794-jair.pdf

[Sean]

I put one type of brute force solution up here stackoverflow.com/a/47698424/1641247

[starblue]

You probably mean NP-complete.

[Carmen]

I was just playing with something like that on a bit of paper, right now looks fairly optimal in most cases, even without rotating the rectangles or anything

[mekanik]

Well, if it's NP complete, then it's easy to solve, just solve an equivalent instance of the travelling salesman, and there you go. But it's trivial to show that as posed, it's not, since NP-complete problems are decision problems (you get back yes/no answers), and have a polynomial time verfication algorithm. The question "is there a arrangement of rectangles a,b,c... that take up less area than 256*128 could be NP-complete.

[Carmen]

I implemented it and run a bunch of test data through it, seems to do a pretty good job only leaving a little wasted data. Now I just need to rewrite my implementation to be more efficient than a linear search for each rect through the available space checking each pixel is that point is blocked (against all the existing rects)...

[Anderson Green]

Here's another nice example of an optimizing rectangle-packing algorithm: codeproject.com/Articles/210979/…

[Jim Balter]

An optimal solution is given in jair.org/media/3735/live-3735-6794-jair.pdf

[Jim Balter]

@Eclipse is correct. From jair.org/media/3735/live-3735-6794-jair.pdf "The optimization problem is NP-hard, while the problem of deciding whether a set of rectangles can be packed in a given bounding box is NP-complete, via a reduction from bin-packing (Korf, 2003)." However, note that the OP asked for "a fairly optimal way", and there are solutions for that in P, for broad enough definitions of "fairly".

[Quantum7]

All of these require knowing the width of the space.

[Ciro Santilli OurBigBook.com]

I also suspect NP-hardness, but we need a reference / proof.

[Ciro Santilli OurBigBook.com]

Problem also mentioned in: en.wikipedia.org/wiki/… Notably, this restricts bin packing to a single bin of unknown size, I wonder if it is still NP-complete there.

[Ciro Santilli OurBigBook.com]

@Quantum7 possibly not too important since OP requires sides to be powers of two, so we could just try out a bunch of dimensions with enough area.

[Blindy]

Holy thread necro, Batman. This is a packing problem, and it's already proven to be NP-hard at best: en.wikipedia.org/wiki/Packing_problems

[Attila Tanyi]

I had a hard time trying to imagine how optimal this could work. So I've coded it (with a square shape) and the results are great. Here's a demo animation: imgur.com/ISjxuOR

[Arek Bal]

@JimBalter square space wise... probably... in terms of speed and scalability? Not really?

[Jim Balter]

@ArekBal Get a clue and read the paper. "Optimal" in this context refers to use of space.

[scunliffe]

@JimBalter any chance you have a new URL? that one seems to redirect to the site root. :-(

[Jim Balter]

@scunliffe Try googling ... I think this is the same paper: pdfs.semanticscholar.org/1120/…

[Jim Balter]

The link I gave above is gone; go here instead: pdfs.semanticscholar.org/1120/…