包装矩形算法

Question

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

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

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

谢谢!

编辑:每种尺寸可以有多个矩形

这不是功课.我正在尝试创建一个类似于ted.com效果的效果

随机意味着可能存在多个满足约束条件的矩形包装.该算法在每次运行时不应产生相同的包装.

Answer 1

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