Fitting rectangles together in optimal fashion

Question

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

Zelda

Why does the containing shape also have to be square? Why can't it be rectangular but not square? – Chardin

Good point. I meant rectangle. I'll edit. – Zelda

google.com/search?q=rectangle+packing+algorithm – Anzac

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.

Zen

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.

Ruvolo

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

Polypeptide

Answer 4

Here is a good description of a fast packing algorithm - http://www.codeproject.com/KB/web-image/rectanglepacker.aspx

Kenley