G2Plot：一个基于配置、体验优雅、面向数据分析的统计图表库，帮助开发者以最小成本绘制高质量统计图表，诞生于阿里经济体 BI 产品真实场景的业务诉求。

简介

在展示具有层级关系的数据时，除了树状图，还有一种特殊的图形——矩形树图。矩形树图将树状结构转化成了平面矩形，这种结构除了可以展示层级关系外，还很适合展示数据的权重关系。

举例，下图(左)展示了某公司当年销售数据，点击矩形块(办公用品)，下钻到子分支数据（下图右）。在同一级别的节点中，按照各自的权重（销量）将坐标系分割成若干矩形块，并区分颜色增强分类的对比度。

本文主要介绍在实现"在同一级别的节点中，按照各自的权重，将坐标系分割成若干矩形块"这一布局功能所用到的算法，以及在 G2 Plot 中如何应用。

在具体到每一种算法前，我们先来思考一下, 一个理想的矩形树图布局应该有怎么样的特性：

• 我们希望布局尽可能的接近正方形，因为细长条的形状不利于相互比较其权重大小，也不利于点击下钻等交互。定义纵横比为长边/短边，即纵横比越高，效果越差
• 我们希望树图是有序的，用户可以方便的进行连续阅读
• 我们希望树图尽可能稳定：当输入数据发生变化时，树图应尽快少改变。

接下来，我们从纵横比，有序性，稳定性三个方面出发，了解 G2 Plot 矩形树图的布局方式。

> Tip 1：G2 Plot 矩形树图布局算法基于 d3-hierarchy 。以下内容同样基于 d3-hierarchy 库。 > Tip2：用户在 G2Plot 中，可使用 hierarchyConfig 属性，更改预设算法

1. TreemapBinary

Treemap Binary 算法递归地将指定的 nodes 划分为一个近似平衡的二叉树，宽矩形进行水平分割和高矩形进行垂直分割。

基本思路是，每次以 sum/2 为目标，将 node 数组分割为两部分，重复该过程，直至子数组无法再分割。 以数据 [50, 10, 6, 20] 为例:

每次分割的生成的图形为:

伪代码如下：

TreemapBinary
   设置可视化空间的初始宽度和高度
   设置初始的分割起始位置和结束位置
   获取父节点的权重（大部分情况下，即子节点的权重之和）
   调用 Partition 函数
   
Partition（节点，位置，宽度，长度）
   IF(节点已是叶子节点)
     根据位置和宽度，长度信息，为节点赋值
     
   目标总值 = 节点权重 / 2；
   N(当前遍历节点下标) = 0;
   左子树 = 空数组;
   
   WHILE（左子树 < 目标总值）
   		左子树加入第 N 个子节点
      N + 1；
   
   剩余部分纳入右子树
   
   IF(宽度 > 长度)
   	左子树宽度 = (左子树权重 / 总权重) * 宽度
    右子树宽度 = (右子树权重 / 总权重) * 宽度
    Partition（左子树, 位置，左子树宽度，长度）
    Partition（右子树, 位置，右子树宽度，长度）
   ELSE
   	左子树长度 = (左子树权重 / 总权重) * 长度
    右子树长度 = (右子树权重 / 总权重) * 长度
    Partition（左子树, 位置，宽度，左子树长度）
    Partition（右子树, 位置，宽度，右子树长度）

我们来评判 TreemapBinary 算法

• 纵横比: TreemapBinary 没有刻意保证纵横比，但因为会在子树分割时根据当前纵横比判断是横向或者纵向，所以纵横比效果一般
• 有序性：TreemapBinary 的切割顺序依赖于二叉树的顺序
• 稳定性：稳定。对于一个近似平衡的二叉树，当改变某个子节点权重的时候，较少内容被改变

以上具体代码可参考 binary 算法

2. TreemapDice & TreemapSlice & TreemapSliceDice

TreemapDice 算法比较简单，将通过指定 x0, y0, x1, y1 所指定的矩形区域按指定节点的每个子节点的权重水平分割. 子节点按顺序排列即可。

示意图如下：

依次来评判 TreemapDice 算法

• 纵横比: 很高，所有的数据均是单向切割，效果很差
• 有序性：有序，子节点按顺序排列
• 稳定性：稳定。当某个节点权重改变时，由于整体为纵向布局，改变内容较少

TreemapSlice 算法类似于 TreemapDice, 区别是进行横向分割

无论是TreemapSlice 还是 TreemapDice，他们的纵横比都很差，尤其是在嵌套树图中。TreemapSliceDice 改善了这种做法，即如果指定的节点深度为奇数, 则使用 TreemapSlice 算法; 否则使用 TreemapDice 算法。图示如下。

TreemapSliceDice 在层级为 1 的树图中，TreemapSliceDice 的表现和 TreemapSlice 的表现是一致的。而在嵌套树图，改善了其纵横比。

以上具体代码可参考 slice 算法，dice 算法，sliceDice 算法

3. TreemapSquarify & TreemapResquarify

TreemapSquarify 是一种优先保证纵横比的算法，它使得分割出的矩形尽可能的接近正方形，同时利用贪婪算法优化了效率。

TreemapSquarify 是一个递归过程，每次从矩形最短边开始填充，当节点被一个个添加时，要么添加到当前行，要么在剩余的矩形行中开启一个新行，这个取决于何种操作使其纵横比最小。

一个经典例子：4*6 矩形，数据为 [6, 6, 4, 3, 2, 2, 1] , 它的分割过程和在 G2Plot 中的渲染效果如下

如图所示，每次从最短边开始依次填充，在填充到[6, 6, 4] 时，有两个选择，Step3 填充在了当前行，Step 4 开启了新行，比较最差纵横比 Step4 更优，因此舍弃 Step3，认为当前行只应包括[6, 6] ，对其进行布局。下次递归，从新的一行，即 [4] 和剩余矩形 开始。

接下来，我们需要确定如何计算某个节点的纵横比。

我们设定: 新增节点权重为 r ，当前节点列表的和为 s ，可分配矩形的最短边为 w , 最长边为 h , 总和为 S 。我们要求解的值，便是当前节点在同一行时，新增节点的纵横比。（以图示 Step 3 为例， 即 r = 4, s = 16, w = 4, h = 6, S = 24)

1. 可分配矩形的总面积为 w*h ，节点列可分配面积为 w*h*s/S ，当前节点可分配面积为 w*h*r/S，当前节点宽为 h*s/S （在上述 case 中，即可分配矩形面积为 24. [6, 6, 4] 所占面积为 16, 节点 4 所分配面积为 4, 宽为 4）
2. 根据前提条件：填充最短边。可得当前节点的长为 w*r/s (上述 case，节点 4 的长为 1)
3. 纵横比 = Max(长/宽，宽/长)。即 Max( (w*S*r)/(s*s*h) , (s*s*h/w*S*r) ) 。 (以上述 case，即 Max（0.25, 4）)

由于 s/(w*h) 在每次递归中都是一个定值。因此提取该系数，比较纵横比时，可仅比较。 Max( (w*w*r)/(s*s) , (s*s)/(w*w*r) )。

为提高效率，在运行 TreemapSquarify 前先行排序，因此一行节点中，仅需计算权重最大节点和权重最小节点的纵横比即可，设最大权重值为 max ，最小为 min , 即计算 Max( (w*w*max)/(s*s) , (s*s)/(w*w*min) )

在 d3.treemapSquarify 算法中，还可以设置期待纵横比的值。在上述例子中，我们期待纵横比尽可能接近 1，即尽可能为正方形。d3.treemapSquarify 默认纵横比为黄金分割比例，即尽可能接近 0.618。具体代码可参考 squarify 算法

现在我们来评价 TreemapSquarify 算法：

• 纵横比: 效果最佳
• 有序性：无序，算法最开始即进行了排序
• 稳定性: 一般，更改某个节点权重时，可能产生较大变更

TreemapResquarify 是在 TreemapSquarify 基础上进行了改造，即每次记录上一次使用 TreemapSquarify 生成的布局，若后续有数据更新，继续在上次生成布局的基础上直接 slice 或 dice，这样不更改节点相对位置，仅更改大小，提高了稳定性，但后续更新的布局不够理想，仅第一次布局应用了 TreemapSquarify。具体代码可参考 resquarify 算法

总结

具体解析了各个算法的区别后，我们根据评判标准重新比较下各个算法，可以得

纵横比: Slice&Dice > Binary > Squarify, 认为 Squarify 算法效果最好 有序性: Slice&Dice > Binary > Squarify 稳定性: Slice&Dice = Binary > Squarify

参考文献

• d3-hierarchy
• treemap-history
• Squarified Treemaps