algorithm - 最优布局算法

Question

我正在根据这篇文章在我的 ASP.NET 应用程序中实现 CSS Sprites 设置。

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

在“已经获取 SPRITE！”部分中 ……作者说……

“唯一真正的缺点是你所有的图像都是垂直排列的。我不太确定这是否重要，但大多数其他生成器都能够以某种方式垂直和水平排列图像。”

我确信这一定是一个以前解决过的问题，所以我的问题是，“给定一组矩形，你能以最佳方式有效地布置它们吗？” （我想这取决于我对最优的定义，但从最接近正方形开始。（尽管实际上可能并非如此。））另外，您是否需要提前所有矩形或可以这样做逐步？

Answer 1

这被称为矩形包装问题。即使在非常简单的情况下，找到最佳解决方案也是 NP 难的，尽管通常有很好的启发式方法。谷歌搜索矩形包装提供了一些有趣的算法和代码。