Packing rectangles

Sometimes you may run into a problem of placing a pile of rectangles as close as possible. Maybe you are visualising something, or you just want to create image sprites. The problem is NP-hard, this means that there is no algorithm that can produce ideal solution in a reasonable time. In this post I want to share with you an algorithm that I used myself. It's both easy to understand and does a good job of packing the rectangles.

Basics

Disclaimer

Please note that for all heuristics here use one dimension values (such as width, height and perimeter), but not area of the rectangles. This is done because I feel it works better this way. Don't take it too hard .

Sorting

First of all you have to sort elements, so you insert larger first, and then you can fit smaller in the gaps that are left. As a comparison metric I'm using perimeter, although some algorithms tend to use width or height only.

Because we are using perimeter as the comparison criterion we say that all this shapes are the same size:

But if we used area as the size criterion we'd get that these rectangle are same:

Free Spaces

One of the main concepts of this algorithm is a set of rectangles called free spaces, where we can insert our rectangles (taken from Ville Koskela's blog).
At the beginning we have one free space which dimensions are sum of widths and heights of all elements. Then we insert first element into that space, and it's divided into more free spaces. Please note that they overlap:

Then we insert another element into one of the free spaces, and they are re-divided once more:

Alignment

As you've seen in the example above we are placing our rectangles in a top left corner of free spaces.

Bounding box

One more property of our system are so called bounds or bounding box. A circumscribed rectangle for our currently placed elements.

One iteration step

After you've got familiar with the main ideas, you should start iterating over sorted rectangles and placing them one by one in the best positions. Here I'll describe what happens during each iteration and add some details on heuristics and free space recalculation.

Find the best placement

Well, first of all the rectangle should fit into a free space that you want to place it into. And then there are two heuristics to determine the best free space for a current rectangle.

Don't make it stick out

Firs of all check how much the rectangle the sticks out of the bounding box if you place it in a certain free space. You don't want to increase size of the bounding box, don't you? So you should choose a free space that will cause the least increase of the bounds.

Minimise space waste

If placing element in some two free spaces cause the same expansion of the bounding box (this usually happens when you are placing a rectangle inside the bounds) then you should use another heuristic. Just check which of this two free spaces is smaller. You want to put a rectangle into as small space as possible, so that you won't waste that precious resource for a gap.

Place it!

When you've found the best free space for your element - put it there. Also don't forget to recalculate bounds if needed.

Recalculate free spaces

Recalculating free spaces requires two actions.

Split intersected spaces

By placing a new rectangle you'll intersect some free spaces, at least the one that you've placed the rectangle into. So just iterate over all the free spaces, check if current rectangle intersects them and split them into parts if it's true. When splitting free spaces create the largest rectangles that can fit into the remaining free space, here are some examples:

Filtering subspaces

After splitting affected spaces there is a chance that you'll get some free spaces that are fully enclosed in the other ones. Be sure to remove all the subspaces.

The End

That's it, in the end you should get a nice rectangle like this one:

Feel free to ask questions. Also you can find an implementation of Roassal layout using this algorithm on SmalltalkHub.