最佳布局算法

Question

3

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

在节目《快使用 SPRITE 吧！》中，作者说道：“唯一的真正缺点是你所有的图像都竖着排列。我不太确定这是否重要，但大多数其他生成器都有某种能够竖向和横向地排列图像的功能。”

我相信这一定是一个之前已经解决的问题，所以我的问题是，“给定一个矩形集合，你能够有效地以最优的方式布置它们吗？”（我想这取决于我对最优的定义，但首先要尽可能接近一个正方形。（虽然这可能并不完全正确。））此外，你需要事先知道所有的矩形，还是可以逐步完成？

- ChrisV

对于大多数计算机而言，垂直布局会有更好的缓存行为（参见为什么Internet Explorer动画标志将其帧垂直排列？）。为什么说正方形是最优的？为什么您链接的页面认为引用局部性是一个缺点？ - Pete Kirkham

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Norman · Accepted Answer

这被称为矩形装箱问题。即使在非常简单的情况下，找到最优解也是NP难的，尽管通常有很好的启发式算法。谷歌搜索矩形装箱会给出一些有趣的算法和代码。