Rectangle Packing Algorithms

This problem is NP complete, meaning that it's impossible to write an algorithm that gives you THE best result (unless constrained to a very few rectangles).

Typically you sort the rectangles to be inserted by area.
Then for each rectangle (starting with the largest one), insert with a first fit strategy.
I.e testing every possible (x, y) position in the target rectangle and choose the first spot that is available.

Other strategies could of course give better results in some cases, but the above is "good enough" IMO.

http://www.blackpawn.com/texts/lightmaps/default.html

Link to the above for the lazy people

A note, the link to the source / article above doesn't do what I described previously.
It's easy to see that using a tree structure like that fails to insert som rectangles when it's surely possible.
For instance, imagine that the second rectangle to be inserted (the red number two) instead has the height of 1 and 2 combined.
It can't fit into the white rectangle because of the A split.
It's obvious that there is space for it to the right of rectangle 1 but the algorithm presented failed to "see" that.

The algorithm I proposed,
"I.e testing every possible (x, y) position in the target rectangle and choose the first spot that is available.",
would have realized that.
Although this is slower (can be sped up quite a lot from the brute force), but surely you're doing this as an offline operator, i.e nothing you'd do every frame!?

I don't think you need to test every position in the target rectangle. If you sort the rectangles to be placed in order of decreasing width, assuming all rectangles have a width that is a power of 2, and then place them in that order, you only need to search x coordinates that are aligned with the width of the object currently being placed. For example, something 32 wide would have its first fit x coordinate of 0, 32, 64, 96, 128, 160, 192, etc. This is because if the rectangles are inserted in order of decreasing width, all of the previous rectangles must have been a width that is a multiple of 32. The first open space that will be wide enough must therefore occur on a multiple of 32 (in the x direction; for the y axis you'd still need to do a more exhaustive search).

Another path towards an approximate solution might be to merge together smaller rectangles to form bigger rectangles, repeating until all the rectangles are merged. A greedy way to select the rectangles to merge would be to select the merge that would waste the least space. A way to find an optimal solution would be to search all of the different orders and ways (horizontal or vertical) the merges can be done, backtracking when the wasted space exceeds the space wasted by a previously found solution. Also a merge is clearly not part of the optimal solution if the space it wastes is big enough for another rectangle to fit inside.

Quote:

Original post by eq This problem is NP complete

ICBW, but I don't think that is true given the restrictions (POT sources and POT result).

If all your blocks sizes are multiples of 32, then you end up with Tetris-like problem.

So it might be possible to find optimal (or one of) solution through exhaustive search in reasonable time.

For one, rather than partitioning the space in both directions, you build from bottom up, while trying to vertically fill the space from one side.

Tetris is apparently NP hard (finding minimum number of rows, for example), but I'm not sure if this problem is simpler or harder. While it looks simpler, there's always a nasty special case or two.

But I don't know if extra knowledge about dimensions helps solving the problem.

Thanks for the suggestions.

What I have done so far is make it so that a rectangle is only placed in the hole that will result in the least possible area afterwards. This means that a rectangle will be placed in a hole that results in no increase in area, rather than a hole that will increase the area.

This works pretty well.

And beyond that it is getting the right sorting methods for the rectangles and the holes.