algorithm - 平面数据集的平方树图算法？

Question

目前我使用切片和骰子方法：

• 获取值和标签列表
• 计算所有值的总和
• 通过将每个值除以总和来计算比率
• 对于每个列表项：
  • height=1用和画一个盒子width=ratio
  • 在盒子顶部绘制标签

Answer 1

让我按照我的理解重述你的问题。

您知道需要绘制并放入正方形的一堆矩形的区域，并且您希望使用没有极端高度/宽度比的矩形来执行此操作。每个矩形代表给定标签所采用的总值的一部分。问题是要弄清楚这些矩形的形状和位置应该是什么，以使它们完美契合，并且每个矩形都有所需的面积。

你不需要一个完美的答案。只有一个比当前的更好，它只是将正方形切成垂直条。

这是我的建议。泛化为在目标矩形中拟合矩形。（这让我们可以使用递归。）此外，我将假设标签已按区域排序，最大的在前。（排序是一个简单的添加步骤。）然后根据以下递归规则找出矩形的位置：

1. 如果列表中的第一个元素超过该区域的 1/3，则将目标矩形的长边拆分为第一个元素和其他所有元素，然后递归地将其他所有元素放入剩余部分。
2. 否则将您的列表分成两部分，区域的中位数进入第一个列表。将目标矩形一分为二，一个用于第一个列表，一个用于第二个。递归填充每个矩形。

对于大多数数据集，这应该为您的目的提供相当好的划分。它的计算速度应该相当快，并且只有最小的矩形才能具有比 3 比 1 更极端的比率。