3

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?

Sklivvz
  • 30,601
  • 24
  • 116
  • 172
ChrisV
  • 2,213
  • 1
  • 18
  • 30
  • For most computers, a vertical layout will have much better cache behaviour (see [Why does the Internet Explorer animated logo arrange its frame vertically?](http://blogs.msdn.com/oldnewthing/archive/2005/08/05/448073.aspx)). 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? – Pete Kirkham Apr 08 '09 at 13:04

1 Answers1

5

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.

David Norman
  • 19,396
  • 12
  • 64
  • 54