logo标签列表

平铺不同尺寸的矩形

algorithmoptimizationtiling
7
我正在寻找一些算法指导，可以在不重叠的情况下平铺不同大小的矩形。
给定一组不同大小的矩形，在大小为H x W的区域内平铺它们，不允许重叠。目标是最大化使用空间或相反地-最小化间隙面积。如果没有足够的空间，请继续使用相同大小的第二个区域，以此类推。
假设每个矩形的宽度和高度都小于平铺区域的相应尺寸。矩形不会旋转或以其他方式变换-即其边缘要么是水平的，要么是垂直的。
我不是在寻找完成的代码，只是想知道解决这个问题的最佳方法/算法是什么。
1
对我来说，这听起来像是一个教科书式的装箱问题。维基百科链接了这个页面，看起来很有用。 - Kevin
太好了！这是一个能立即找到正确算法的关键字！我就知道这个问题应该有一个特殊的名称！谢谢！ - Vladislavs Dovgalecs
2个回答
2

最简单的方法是使用kd树将树分成垂直和水平欧几里得二维空间。然后，您可以将矩形包装到创建的空间之一中，并递归地划分树。在线上有一个Jquery treemap插件示例。Jquery插件masonry也可以做同样的事情，但它更像是1d bin-packing求解器。2d bin-packing要复杂得多，还可能意味着旋转矩形。这是一个打包lightmaps的示例: http://www.blackpawn.com/texts/lightmaps/default.html。

嗯，你能详细说明一下你的方法吗？如果有几百或几千个矩形，欧几里得空间会发生什么？会不会有建立庞大树的风险？ - Vladislavs Dovgalecs
Xeon：你不能把苹果和橙子相比较。欧几里得空间是一个数学定律。这是事实。 - Micromega
抱歉，我不明白如何构建这样的树以及分割欧几里得空间的意义。也就是说，你是如何从输入的矩形转换成树形结构的，然后又是如何使用这棵树来得到最终的平铺结果的。 - Vladislavs Dovgalecs
1
@xeon：我添加了一个C++示例的链接。 - Micromega
谢谢！正如我所担心的那样，我问了一个已经存在的问题：https://dev59.com/iV_Va4cB1Zd3GeqPSVQr - Vladislavs Dovgalecs
0

我有一个可能朝着正确方向的想法。这个想法是追踪边界框中瓷砖区域与白色区域的比率。

输入：无序的输入矩形集合 输出：填充面积

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

仍然有一些要定义的问题-如何最好地决定边界框的位置？如何强制执行边界框增长限制？如何有效地找到最佳边界框？

不，这是一个算法，我应该在我的应用程序中快速使用它。如果已经存在好的软件包，我就没有时间从头开始编写它（通过关键字“2d binning problem”，“packaging problem”等进行快速搜索，发现这是许多领域都非常知名的问题）。 - Vladislavs Dovgalecs
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接