What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?

Fire_Lancer_6266 0
Viewed 109980

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)?

packing algorithm
7 Answers

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.

user_742220
user_10880

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.

user_1087960

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.

mgb_108970
Related