logo标签列表

矩形装箱算法

algorithmmathpacking
5
我需要解决以下问题： 我有多个矩形，它们的尺寸为：宽度高度，宽度/2高度/2，宽度/4高度/4，宽度/8高度/8等等。
我需要将这些矩形放入一个大小为x*宽度y*高度的大矩形中，使得没有矩形重叠，矩形在填充中随机分布，并且任何一个矩形都至少要接触另一个矩形。我尝试了一个相当基本的贪心算法，但它失败了。
你能给我一些关于如何解决这个问题的建议吗？
谢谢！
编辑：您可以有多个相同尺寸的矩形 这不是作业。我正在尝试创建类似于ted.com上的效果。
“随机”是指可能存在满足约束条件的矩形多次填充方式。该算法不应在每次运行时产生相同的填充形式。
这是作业吗？如果是，请将其标记为作业。 - Ed Heal
1
你需要提供更多的细节。你手头上有每种矩形尺寸的一个（例如，1个单位边长，0.5个单位边长等），还是你可以随意使用任意数量的矩形？此外，请定义“随机”。 - El Ronnoco
你可以窃取Windows 8“Metro”代码 :-) - spraff
1
听起来非常类似于我之前回答的一个问题：https://dev59.com/4lvUa4cB1Zd3GeqPsVOq#7439585 - Merlyn Morgan-Graham
5个回答
4
这听起来像是一个矩形装箱问题。链接中有一个算法。该代码会尽可能紧密地排列矩形。您说您希望矩形被随机分布，我猜想这意味着不是所有相同大小的矩形都在一起，而是所有矩形都分散开来填满大矩形。也许上面链接中的代码是得到一些想法的好起点。
2
您可以使用空间索引或四叉树来将二维平面细分。其思想是将二维问题简化为一维问题。一旦您获得了空间索引（或空间填充曲线），并且您可以将二维离散化为一维，您就可以使用一维来搜索相似性或按长度从低到高或反向排序。如果您有此顺序，那么您可以将索引计算回二维表示，并以最有效的方式将它们打包在容器中。有许多方法可以制作空间索引。其中一些最好但最难制作的是希尔伯特曲线。另一个是z-curve或morton-curve。它与zizag-curve不同，因为它将平面划分为4个正方形（而不是矩形）。
编辑：这里是一个Jquery插件的链接：http://www.fbtools.com/jquery/treemap/这里是世界人口：http://www.fbtools.com/jquery/treemap/population.html 编辑：http://people.csail.mit.edu/konak/papers/socg_2008-circular_partitions_with_applications_to_visualization_and_embeddings.html 编辑：http://lip.sourceforge.net/ctreemap.html
1
在每个步骤中，您将新矩形的表面分成4份。SUM(1/4n for n in [0,inf]) = 4/3。因此，您最好的选择是将您的矩形放入一个表面为4/3（高度*宽度）的矩形中（这是下限）。@mloskot算法提供了一个可能的解决方案，该方案将位于表面为3/2（高度*宽度）的矩形中：以下是说明：

enter image description here

我不明白你怎么能做得更好。

0

假设您只有每种尺寸的一个矩形，您可以尝试复制纸张尺寸的排列顺序。将矩形按大小从大到小排序，然后：

  1. 取第一个矩形并将其放置在目标平面的角落。
  2. 取下一个矩形（确保它比前一个矩形小）
  3. 旋转约90度
  4. 放置，使得
    • 其较短的一侧与上一个更大的邻居的较长一侧相邻
    • 其较长的一侧与目标平面的边缘或相同大小的邻居的边缘相邻
  5. 重复步骤2-4

我意识到描述可能不清楚，因此这里有一张图片展示解决方案 - 它应该有助于理解：

enter image description here

在您的示例中，每步将表面分成两半（A1，A2...），但在所需的算法中是四分之一... 因此这里有些错误。 - Ricky Bobby
A 纸张的工作原理是因为其边长比为 1:√2，其他纸张尺寸无法实现这样的包装方式。（我经常想知道为什么 A 系列在国际上不更普遍一些...） - spraff
@Ricky Bobby，说得好，我在阅读问题时错过了那些细节。 - mloskot
@spraff 我的意思不是要将示例与问题一一对应。我只是想提供一些跟随的思路。 - mloskot
0
2
你可以有多个相同大小的矩形。 - silviupop
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接