Optimal Layout Algorithm

Question

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?

I'm not looking for an answer urgently, as the solution in the article works very well. but I'm interested in seeing what a possible solution might look like.

Thank you.

Answer 1

It depends on your definition of "optimal". However, try looking at this and this.

Answer 2

For a page in a website for me, optimal is spanning the width of the screen, then wrapping - i.e. making the most of the available space.

Answer 3

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.

Answer 4

For most computers, a vertical layout will have much better cache behaviour (see Why does the Internet Explorer animated logo arrange its frame vertically?).

What is the reasoning behind saying a square is optimal? Why does the page you linked to think locality of reference is a down side?