Optimal Layout Algorithm [duplicate]

Question

This question already has an answer here:

• What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way? 8 answers

I'm implementing a CSS Sprites setup in my ASP.NET application based on this article..

http://weblogs.asp.net/zowens/archive/2008/03/05/css-sprite-for-asp-net.aspx

In the section "Get the SPRITE already!"... the author says...

"The only real down side to this is that all your images are lined up vertically. I'm not quite sure that this matters, but most other generators have the ability to somehow line the images up vertically and horizontally."

I'm sure this must be a previously solved problem so my question is, "Given a collection of rectangles, can you efficiently lay these out in an optimal way?" (I suppose it depends on my definition of optimal, but being the closest possible to a square as a start. (although this may not actually be the case.)) Also, would you need all the rectangles in advance or could this be done progressively?

Answer 1

This is known as the rectangle packing problem. Even in very simple cases, finding the optimal solution is NP-hard, although often there are good heuristics. Googling rectangle packing gives some interesting algorithms and code.