7

我正在寻找一些指向算法的指针，这些算法应该允许平铺不重叠不同大小的矩形。

给定一组不同大小的矩形，将它们平铺在大小为 H x W 的区域上，不重叠。目标是最大化使用的空间或相反 - 最小化间隙面积。如果没有足够的空间，继续第二个相同大小的区域，依此类推。

假设每个矩形的宽度和高度都小于平铺区域的相应尺寸。矩形不会旋转或以其他方式变换 - 即它们的边是水平的或垂直的。

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

4

2 回答 2

2

最简单的是使用 kd-tree 将树细分为垂直和水平 euklidian 2d 空间。然后您可以将一个矩形打包到其中一个创建的空间中并递归地细分树。在线提供了一个 Jquery treemap 插件示例。jquery plugin masonry 可以做同样的事情，但它更像是一个 1d bin-packing 求解器。二维装箱要复杂得多，也可能意味着旋转矩形。这是打包光照贴图的示例：http: //www.blackpawn.com/texts/lightmaps/default.html。

于 2012-07-30T15:30:08.647 回答
0

我有一个想法可以朝着正确的方向发展。这个想法是在边界框中跟踪平铺区域与白色区域的比率。

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

  1. 定义空边界框
  2. 从边界框 B 包含最小空白区域比率的输入集中选择这两个矩形 A_i 和 B_j
  3. 用两个最优框更新边界框
  4. 将边界框放在一个角落里，比如 (1,1)
  5. 重复直到没有盒子
    1. 从集合中取出一个新框，例如更新的边界框具有最小空白
    2. 如果边界框的宽度或高度超过输出区域的宽度或高度，则限制在水平或垂直方向增长
    3. 如果无法添加新框，则继续使用新区域 H x W 并重新启动算法，否则更新边界框

还有一些要点需要定义——如何最好地确定边界框的位置？如何施加边界框增长限制？如何有效地找到最佳边界框？

于 2012-07-30T15:39:21.097 回答