Grab Bag Release: 2D Packing

It’s been three weeks since my last post, mostly because I’ve been working on the post-mortem of Campus Buddies which I’m gonna release soon. Until then, feel free to take a look at my implementation of two-dimensional strip packing algorithms.

2D Packing

We consider the problem of two-dimensional strip packing: The input is a set of items, in this case rectangles. The goal is to pack all items into a strip of unlimited height, minimizing the maximum height used, in such a way that the sides of all items are aligned with the sides the strip. The quality of strip packing algorithms is measured in terms of the optimal solution. Applications include cutting objects out of a strip of material minimizing the waste.

In my implementation, items that have to be packed are represented by rectangles. While the initial position of these rectangles doesn’t matter for the packing algorithms, their size does. Given a strip width, each algorithm is able to find a solution for an arbitrary list of items. Some of the algorithms, such as the Epstein/van Stee, rotate items in order to approximate a better solution.