7

我有一组N个正数，以及一个尺寸为X和Y的矩形，我需要将其划分为N个较小的矩形，这样：

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

我需要这方面的指示。你知道网上描述的这种算法吗？你有什么想法（伪代码很好）？

谢谢。

4

2 回答 2

9

你所描述的听起来像一个树图：

树形图将分层（树结构）数据显示为一组嵌套矩形。树的每个分支都有一个矩形，然后用代表子分支的较小矩形平铺。叶节点的矩形的面积与数据上的指定维度成比例。

该 Wikipedia 页面链接到Ben Shneiderman 的页面，该页面提供了很好的概述和 Java 实现的链接：

然后，当我在教员休息室对此感到困惑时，我得到了啊哈！当您穿过关卡时，体验将屏幕分成水平和垂直方向交替的矩形。这个递归算法看起来很有吸引力，但我花了几天时间才说服自己它总是有效的，并编写了一个六行算法。

维基百科还引用了 Mark Bruls、Kees Huizing 和 Jarke J. van Wijk 的“Squarified Treemaps”（PDF），其中提出了一种可能的算法：

我们如何将一个矩形递归地细分为矩形，以使它们的纵横比（例如 max(height/width, width/height)）尽可能接近 1？所有可能的镶嵌的数量非常大。这个问题属于 NP-hard 问题的范畴。然而，对于我们的应用，我们不需要最优解，需要一个可以在短时间内计算的好的解。

您没有在问题中提及任何递归，因此您的情况可能只是树形图的一个级别；但是由于算法一次只在一个级别上工作，所以这应该没问题。

于 2010-03-28T15:20:54.193 回答
1

我一直在做类似的事情。我优先考虑简单性而不是获得尽可能相似的纵横比。这应该（理论上）有效。在纸上测试了一些介于 1 和 10 之间的 N 值。

N = 要创建的矩形总数，Q = max(width, height) / min(width, height)，R = N / Q

如果 Q > N/2，将矩形沿最长边分成 N 个部分。如果 Q <= N/2，则将矩形沿其最短边拆分为 R（圆角整数）部分。然后沿其最短边将子矩形拆分为 N/R（向下舍入 int）部分。从下一个 subrects 除法的结果中减去四舍五入的值。对所有子矩形重复或直到创建所需数量的矩形。

于 2010-06-16T22:34:55.130 回答