G2Plot:一个基于配置、体验优雅、面向数据分析的统计图表库,帮助开发者以最小成本绘制高质量统计图表,诞生于阿里经济体 BI 产品真实场景的业务诉求。
简介
在展示具有层级关系的数据时,除了树状图,还有一种特殊的图形——矩形树图。矩形树图将树状结构转化成了平面矩形,这种结构除了可以展示层级关系外,还很适合展示数据的权重关系。
举例,下图(左)展示了某公司当年销售数据,点击矩形块(办公用品),下钻到子分支数据(下图右)。在同一级别的节点中,按照各自的权重(销量)将坐标系分割成若干矩形块,并区分颜色增强分类的对比度。
![屏幕快照 2021-02-02 17.19.55.png]()
![屏幕快照 2021-02-02 17.20.02.png]()
本文主要介绍在实现"在同一级别的节点中,按照各自的权重,将坐标系分割成若干矩形块"这一布局功能所用到的算法,以及在 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] 为例:
![屏幕快照 2021-02-01 18.13.20.png]()
每次分割的生成的图形为:
![屏幕快照 2021-02-01 20.19.19.png]()
伪代码如下:
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 所指定的矩形区域按指定节点的每个子节点的权重水平分割. 子节点按顺序排列即可。
示意图如下:
![屏幕快照 2021-02-01 22.21.19.png]()
依次来评判 TreemapDice 算法
- 纵横比: 很高,所有的数据均是单向切割,效果很差
- 有序性:有序,子节点按顺序排列
- 稳定性:稳定。当某个节点权重改变时,由于整体为纵向布局,改变内容较少
TreemapSlice 算法类似于 TreemapDice, 区别是进行横向分割
![屏幕快照 2021-02-01 22.25.35.png]()
无论是TreemapSlice 还是 TreemapDice,他们的纵横比都很差,尤其是在嵌套树图中。TreemapSliceDice 改善了这种做法,即如果指定的节点深度为奇数, 则使用 TreemapSlice 算法; 否则使用 TreemapDice 算法。图示如下。
![屏幕快照 2021-02-02 10.29.13.png]()
TreemapSliceDice 在层级为 1 的树图中,TreemapSliceDice 的表现和 TreemapSlice 的表现是一致的。而在嵌套树图,改善了其纵横比。
以上具体代码可参考 slice 算法,dice 算法,sliceDice 算法
3. TreemapSquarify & TreemapResquarify
TreemapSquarify 是一种优先保证纵横比的算法,它使得分割出的矩形尽可能的接近正方形,同时利用贪婪算法优化了效率。
TreemapSquarify 是一个递归过程,每次从矩形最短边开始填充,当节点被一个个添加时,要么添加到当前行,要么在剩余的矩形行中开启一个新行,这个取决于何种操作使其纵横比最小。
一个经典例子:4*6 矩形,数据为 [6, 6, 4, 3, 2, 2, 1] , 它的分割过程和在 G2Plot 中的渲染效果如下
![屏幕快照 2021-02-02 15.36.17.png]()
![屏幕快照 2021-02-02 17.25.53.png]()
如图所示,每次从最短边开始依次填充,在填充到[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)
- 可分配矩形的总面积为
w*h ,节点列可分配面积为 w*h*s/S ,当前节点可分配面积为 w*h*r/S,当前节点宽为 h*s/S (在上述 case 中,即可分配矩形面积为 24. [6, 6, 4] 所占面积为 16, 节点 4 所分配面积为 4, 宽为 4)
- 根据前提条件:填充最短边。可得当前节点的长为
w*r/s (上述 case,节点 4 的长为 1)
- 纵横比 = 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
参考文献