包装矩形算法

Question

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

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

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

谢谢！

编辑：你可以在每个大小

这不是功课不止一个矩形。我试图创建一个效果类似于ted.com

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

Answer 1

您可以使用空间索引或四叉树细分2d平面。这个想法是将2d问题简化为1d问题。一旦获得了空间索引（或空间填充曲线），并且可以将2d离散化为1d，则可以使用1d来搜索相似度，或者按照从低到高的顺序进行排序，或者按照长度进行排序。如果你得到这个订单，你可以计算这个索引回到第二个代表，并以最有效的方式将它们打包在你的容器中。有很多方法可以创建空间索引。希尔伯特曲线是一些最好但很难做出的。另一个是z曲线或morton曲线。它与zizag曲线不同，因为它将平面细分为4个正方形（不是矩形）。

编辑：这里是一个链接，一个jQuery的插件：http://www.fbtools.com/jquery/treemap/ 这里有世界poplulation：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

Answer 2

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

1. 取第一个矩形并将其放置在目标平面的拐角处。
2. 拍摄下一张长方形（断言它比以前的长方形小）
3. 旋转约90度
4. 的地方，以便
   • 它的尺寸较短的邻近最后的大国邻居的尺寸较长的
   • 和其较长的一侧与目标平面的边缘相邻或相邻的边缘相同 尺寸
5. 重复2 - 4

我认识的描述可能是不清楚，所以这里的画面呈现解决方案 - 它应有助于掌握它：

Answer 3

在每一步你把你的新的表面rectange by 4。

SUM（1/4用于n [0，INF）= 4/3 **

所以你能做的最好是适合你的矩形表面 4/3的矩形（高度×宽）

（这是一个下界）

@mloskot算法给出了一个可能的解决方案，这将是在表面的矩形3/2 *（高度*宽度）：在这里，是示：

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

Answer 4

这是很多像MIP-mapping

Answer 5

这听起来像一个rectangle packing problem。有一个链接到algorithm。该代码尽可能紧密地包装矩形。你说你想要矩形分布随机，我猜这意味着并不是所有矩形都是相邻的一个大小，所有的矩形都分布在大矩形中。也许上面链接的代码将是获得一些想法的好起点。