5

我需要解决以下问题：我有多个大小的矩形：宽度高度，宽度/2高度/2，宽度/4高度/4，宽度/8高度/8 ...等

我需要将这些矩形打包在一个大小为 x*width y*height 的大矩形中，这样没有矩形重叠，矩形随机分布在包装中，任何矩形至少应该接触另一个矩形。我尝试了一个相当基本的贪心算法，但它失败了。

你能给我一些关于如何解决这个问题的建议吗？

谢谢！

编辑：您可以有多个每个尺寸的矩形

这不是家庭作业。我正在尝试创建类似于ted.com上的效果的效果

随机是指可能存在多个满足约束的矩形包装。该算法不应在每次运行时产生相同的包装。

4

5 回答 5

4

这听起来像一个矩形包装问题。那里有一个算法的链接。该代码尽可能紧密地打包矩形。您说您希望矩形随机分布，我猜这意味着并非所有大小相同的矩形都彼此相邻，并且所有矩形都展开以填充大矩形。也许上面链接中的代码是获得一些想法的一个很好的起点。

于 2011-09-28T21:12:48.450 回答
2

您可以使用空间索引或四叉树来细分 2d 平面。这个想法是将二维问题简化为一维问题。获得空间索引（或空间填充曲线）并且可以将 2d 离散化为 1d 后，您可以使用 1d 来搜索相似性或从低到高或相反的排序，例如按长度。如果您收到此订单，则可以将索引计算回二维表示，并以最有效的方式将它们打包到您的容器中。制作空间索引的方法有很多。一些最好但很难制作的是希尔伯特曲线。另一种是 z 曲线或 morton 曲线。它与 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

于 2011-09-28T21:43:09.953 回答
1

在每一步中，您都将新矩形的表面除以 4。

SUM(1/4 n for n in [0,inf]) = 4/3**

所以你能做的最好的就是把你的矩形放在一个表面为 4/3（高度*宽度）的矩形中

（这是一个下限）

@mloskot 算法给出了一个可能的解决方案，它将位于表面 3/2*(height*width) 的矩形中：这是一个插图：

在此处输入图像描述

我看不出你怎么能做得更好。

于 2011-09-28T09:31:43.240 回答
0

这很像MIP 映射

于 2011-09-28T09:51:23.310 回答
0

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

  1. 取第一个矩形并将其放在目标平面的角上。
  2. 取下一个矩形（断言它小于前一个矩形）
  3. 旋转约 90 度
  4. 这样放置
    • 它的较短尺寸与最后一个较大邻居的较长尺寸相邻
    • 并且它的长边与目标平面的边缘或相同大小的邻居的边缘相邻
  5. 重复 2 - 4

我意识到描述可能不清楚，所以这里是展示解决方案的图片 - 它应该有助于掌握它：

在此处输入图像描述

于 2011-09-28T09:21:04.063 回答