Packing rectangles without rotation?

Question

Is the algorithm for packing rectangles without rotation?

Maybe implementation in C++?

I found this

and

• GuillotineBinPack
• ShelfBinPack
• SkylineBinPack

But they rotate rectangles.

Answer 1

You can sort the boxes by width and then place it into a node of a tree. Then split the tree along the 2 axis. For the next box look for the best fit, I.e. least waste and place the box into the free node. Rinse and repeat until no boxes or node is left. You can look into packing lightmaps with a kd-tree by blackpawn.

Answer 2

You can make your boxes square and ignore rotation after packing. This will waste some space but requires no changes to Guillotine library.

Answer 3

You can use this small code to pack rectangles:

http://www.flipcode.com/archives/Rectangle_Placement.shtml