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