将一个矩形划分为给定区域的近距离

Question

我有一组 n 正数和尺寸的矩形 X 和 y 我需要分区 n 较小的矩形：

• 每个较小矩形的表面积与给定集中的相应数字成正比
• 大矩形的所有空间都被占据，较小的矩形之间没有剩余的空间
• 每个小矩形应尽可能接近正方形
• 执行时间应该很小

我需要有关此的指示。您知道网络上描述的算法吗？您有任何想法（伪代码很好）吗？

谢谢。

Answer 1

您描述的听起来像个 Treemap:

Treemaps作为一组嵌套矩形显示层次结构（树结构化）数据。树的每个分支都有一个矩形，然后用代表子分支的较小矩形铺设瓷砖。叶节点的矩形具有与数据的指定维度成正比的区域。

Wikipedia页面链接到 Ben Shneiderman的页面, ，它提供了一个不错的概述并链接到Java实现：

然后，当我在教师休息室感到困惑时，我有了AHA！当您穿越水平时，将屏幕分配到交替的水平和垂直方向的矩形经验。这种递归算法似乎很有吸引力，但是我花了几天的时间说服自己，它总是有效并编写六行算法。

Wikipedia也要 Mark Bruls，Kees Huizing和Jarke J. Van Wijk的“ Superified Treemaps” （PDF）提出一种可能的算法：

我们如何将矩形递归地将矩形切成矩形，从而使它们的方面比例（例如Max（高度/宽度，宽度/高度））接近1？所有可能的镶嵌的数量都非常大。这个问题属于NP-HARD问题的类别。但是，对于我们的应用程序，我们不需要最佳解决方案，需要在短时间内计算出一个好的解决方案。

您没有在问题上提及任何递归，因此您的情况可能只是Treemap的一级；但是，由于该算法一次在一个级别上起作用，因此这应该没有问题。

Answer 2

我一直在研究类似的事情。我将简单性优先于获得尽可能相似的纵横比。从理论上讲，这应该起作用。在纸上测试了1到10之间的某些值。

n =创建的矩数总数，q = max（宽度，高度） / min（宽度，高度），r = n / q

如果q> n/2，请沿其最长的一侧将n部分分为n部分。如果q <= n/2，则将其沿最短侧划分为r（圆形int）部分。然后将子端沿最短一侧分为N/R（圆形的int）部分。从下一个子区域的结果中减去圆形值。重复所有子层或直到创建所需的RECT数为止。