平铺不同大小的矩形(Tiling different size rectangles)

我要寻找一些指针算法，应该允许瓷砖没有重叠不同大小的矩形。

给定一组不同尺寸的矩形，瓦片他们的大小高x的区域W的没有重叠。 其目标是最大限度地使用或相反的空间 - 尽量缩小差距的领域。 如果没有足够的空间，请在同尺寸等的第二区域。

据推测，各矩形的宽度和高度比矩形区域的各个尺寸。 矩形是不旋转或以其它方式转化 - 即它们的边是水平或垂直的。

我不是在找完成的代码，只是好奇，什么样的方法/算法是最好的使用来解决这个问题。

Answer 1:

最简单的就是用kd树树细分为垂直和水平euklidian二维空间。 然后你就可以收拾一个矩形创建的空间之一，递归细分树。 有是一个jQuery插件树状图例如可在网上。 该jQuery插件砖石可以做同样的，但它更像是一维装箱求解。 2D装箱要复杂得多，也可能意味着旋转矩形。 下面是包装光照贴图的例子： http://www.blackpawn.com/texts/lightmaps/default.html 。

Answer 2:

我有一个想法，能走在正确的方向。 这样做是为了跟踪瓦片面积比VS白色区域的边界框。

输入：无序集合输入的矩形输出：填充区域

1. 定义空边框
2. 从输入集合，其边界框B含有最小空白面积比选择这样的两个矩形A_I和B_j
3. 更新与两个最佳盒边框
4. 把边框在一个角落里，说（1,1）
5. 重复，直到没有哪个包装盒
   1. 就拿从集的新盒子，如更新的边框具有最小空白
   2. 限制在水平或垂直方向生长，如果边界框的宽度或高度超过输出区域的
   3. 如果不能添加新的对话框，其中一个新的区域高x宽出发，重新启动算法，否则更新边界框

还有一些点来定义 - 如何最好地确定边界框的地方吗？ 如何征收边框越来越多的限制？ 如何有效地找到最好的边框？

文章来源: Tiling different size rectangles