treemap · 面积编码

把权重铺满一块矩形

一组带权重的项（各部门人数、各文件大小、各品类销售额），如何在一块矩形里一眼看出占比？treemap 用面积编码数量：每项分到的矩形面积正比于权重，互不重叠、铺满整块。难点不在能不能铺满（切条即可），而在切成什么形状：细长条难以辨识，近正方形才好比较。

1 · 面积编码的动机

motivation · 面积编码

答案是用面积编码数量：每项分到的矩形面积正比于它的权重，且无重叠、铺满整块。

图 1-1 · 可直接调各项权重，看矩形如何随之重排，面积始终与权重成正比。

一个合格的 treemap 布局必须同时满足三条：其一，面积正比于权重，这是「用面积比大小」能成立的前提，比例一旦失真就会产生误导；其二，无重叠，每块矩形互不覆盖，否则面积无法读；其三，铺满，不留空隙；层级 treemap 的留白是刻意用来区分层级的，见层级嵌套一节。

满足这三条的布局有无穷多种，区别只在矩形的形状：同样的面积，可以切成细长条，也可以切成近正方形。形状直接决定可读性，这就是 slice-and-dice 与 squarify 两套算法的分野。

slice-and-dice · 切条

把权重映射成面积，最朴素的做法是沿单一方向把矩形按权重占比切成一排条。实现只有几行，缺点也很直接：权重悬殊时切出的是又细又长的条，面积虽对、却难以辨识与比较。

图 2-1 · 可单步逐条切分，右侧实时报出每条的长宽比。把某项权重调得很小，看长宽比如何爆炸。

沿固定方向切，每条的厚度正比于权重，而长度恒等于矩形的另一条边。当某项权重很小，它分到的厚度极薄，长度却仍是满边长，长宽比随之爆炸。经典的 slice-and-dice 会逐层交替横竖切（本节演示单层），但只要某层内权重悬殊，细长条就难以避免。

面积编码的本意是让人一眼比较大小，细长条破坏了这一点，而 squarify 解决的就是它：通过换行让每块尽量方正。

squarify · worst aspect ratio

Bruls、Huizing 与 van Wijk (2000) 的 squarify 换一种贪心策略：逐项累积成「行」，用 worst aspect ratio 判断何时该收尾换行，使每块矩形尽量接近正方形。

图 3-1 · 可单步观察累积与 flush 的决策过程：每加一项就重算 worst，一旦变差就收尾当前行、换到剩余区域的短边重开一行。

把一组面积 $\{a_1 \dots a_n\}$ 铺在长度为 $w$ 的短边上，这一行所有矩形里最差的那个长宽比记作 $worst$ 。设行内面积之和为 $s$ ，则

worst = \max\left(\frac{w^2 \max(a_i)}{s^2},\ \frac{s^2}{w^2 \min(a_i)}\right)

贪心准则是：把下一项加入当前行，若 $worst$ 不增大就继续累积；一旦会变差，就 flush 当前行（沿短边定型并从剩余区域挖走），再用新的短边开启下一行。

每次都沿较短的边铺行，是 squarify 接近正方形的关键，这与 slice-and-dice 固定方向恰好相反。它是贪心而非全局最优，但实践中已足够好，D3 的 treemapSquarify、各类磁盘占用可视化都用它。

nesting · 层级递归

真实数据大多是树：部门下有小组、小组下有人；目录下有子目录、子目录下有文件。treemap 的层级版很直接：内部节点的权重是其所有叶子的权重之和，先把它当一块矩形布局，再在这块矩形内部递归地对它的子节点布局。层与层之间留一点 padding 与表头来区分。

图 4-1 · 层级 treemap 的递归布局。可调上方两个滑块加大 padding 与表头，看留白增多、层级更清晰的同时叶子被挤得更小。

叶子节点自带权重，内部节点的权重由递归求和得到，这保证了「父块面积等于子块面积之和」，层级因此在面积上自洽：看一眼最外层就知道各大类占比，钻进去又能看到内部细分。

padding 与表头不是装饰：没有它们，父子矩形边界重合，根本看不出层级结构；但它们会占用面积，使叶子矩形之和略小于整块，这是层级可读性与面积保真度之间的取舍。每一层内部的布局仍由 squarify 完成，所以每块叶子也尽量方正。

Bruls, M., Huizing, K., & van Wijk, J. J. (2000). Squarified treemaps. In Data Visualization 2000. Springer, 33–42. squarify 的原始论文，含 worst aspect ratio 贪心换行的完整伪代码。
Shneiderman, B. (1992). Tree visualization with tree-maps: 2-d space-filling approach. ACM Transactions on Graphics, 11(1), 92–99. treemap 与 slice-and-dice 的提出。
Treemapping. Wikipedia. 各类 tiling 算法的总览与长宽比、稳定性权衡。https://en.wikipedia.org/wiki/Treemapping