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.

Grab Bag Release: Math

As you might have noticed, I have slightly changed the order of the development roadmap of my Grab Bag of Useful Stuff: 2D Packing heavily relies on rectangles, and that’s why I decided to implement to the Math classes first. These will come in handy for the second version of the ByChance Framework later, as well.

Math

The Npruehs.GrabBag.Math namespace contains utility classes for many math operations.

Math2 is a useful extension of the .NET System.Math class, providing constants like PiOverTwo, or methods like DegreesToRadians for converting angles and passing them to the .NET trigonometric functions.

John Carmack himself advises to use vector structs instead of fields for x- and y-coordinates, for example. Thus, other parts of the Grab Bag follow that advice, and you can do so as well. The vector structs are immutable and feature a lot of convenient operator overloads.

John Carmack @ID_AA_Carmack 9:15 PM – 5 Mar 13

I advocate the use of an idVec2i type for all two integer element tasks over discrete x/y, width/height, etc. A lot of code is improved.

Additionally, there are geometry classes for rectangles and boxes for the same reason.