Fitting rectangles together in optimal fashion

Question

Hi,

I was wondering if anyone knows of any algorithms suited to fitting together N number of rectangles of unknown size into the smallest possible containing rectangle.

By optimal I mean with reducing the amount of white space left over in the resulting containing rectangle.

I would like to use this to generate css sprites from a series of images.

Many Thanks,

Ian

Answer 1

Through packing images into square texture and Simon's answer I got to this link http://code.activestate.com/recipes/442299/

I did not check the recipe, but it seems to allow using non-square containers.

Answer 2

I think what you describe is a variant of the "two dimensional bin packing" problem. The only difference is that you have the items and are trying to find the smallest rectangle.

This survey article is a good start.

Answer 3

The only way to guarantee and optimal solution is to brute force the answer. This quickly becomes unmanagable for personal computers when you have several rectangles, and allow for the possibility of rotation.

Wikipedia has a good article on packing problem http://en.wikipedia.org/wiki/Packing_problem