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

Question

目前我使用切片和切 block 方法:

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

Answer 1

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

您知道需要绘制并适合正方形的一堆矩形的面积，并且您希望使用没有极端高/宽比的矩形来这样做。每个矩形代表给定标签占用的总值的一部分。问题是弄清楚这些矩形的形状和位置应该是怎样的，这样它们才能完美契合，并且每个矩形都有所需的面积。

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

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

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

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