# 如何生成稳定的动态 treemap（矩形树图）关键技术揭晓

## 算法的稳定性

treemap（矩形树图）最早由美国计算机科学家 Ben Shneiderman 在 1992 年提出。为了应对常见的硬盘已满问题，Ben Shneiderman 创新性地提出生成目录树结构可视化的想法。这种展现形式甚至在后来的矩形艺术领域也有了一席之地。

### 常见的矩形树图

#### treemapBinary

``````  function partition(i, j, value, x0, y0, x1, y1) {
while (k < hi) {
var mid = k + hi >>> 1;
if (sums[mid] < valueTarget) k = mid + 1;
else hi = mid;
}

if ((valueTarget - sums[k - 1]) < (sums[k] - valueTarget) && i + 1 < k) --k;

var valueLeft = sums[k] - valueOffset,
valueRight = value - valueLeft;
// 宽矩形
if ((x1 - x0) > (y1 - y0)) {
var xk = value ? (x0 * valueRight + x1 * valueLeft) / value : x1;
partition(i, k, valueLeft, x0, y0, xk, y1);
partition(k, j, valueRight, xk, y0, x1, y1);
} else {
// 高矩形
var yk = value ? (y0 * valueRight + y1 * valueLeft) / value : y1;
partition(i, k, valueLeft, x0, y0, x1, yk);
partition(k, j, valueRight, x0, yk, x1, y1);
}
}
}``````

#### treemapDice

``````export default function (parent, x0, y0, x1, y1) {
var nodes = parent.children,
node,
i = -1,
n = nodes.length,
k = parent.value && (x1 - x0) / parent.value

// 按顺序水平分割排列
while (++i < n) {
;(node = nodes[i]), (node.y0 = y0), (node.y1 = y1)
;(node.x0 = x0), (node.x1 = x0 += node.value * k)
}
}``````

#### treemapSlice

``````export default function (parent, x0, y0, x1, y1) {
var nodes = parent.children,
node,
i = -1,
n = nodes.length,
k = parent.value && (x1 - x0) / parent.value

// 按顺序垂直分割排列
while (++i < n) {
;(node = nodes[i]), (node.y0 = y0), (node.y1 = y1)
;(node.x0 = x0), (node.x1 = x0 += node.value * k)
}
}``````

#### treemapSliceDice

``````export default function (parent, x0, y0, x1, y1) {
// 节点深度判定
;(parent.depth & 1 ? slice : dice)(parent, x0, y0, x1, y1)
}``````

#### treemapSquarify

``````export function squarifyRatio(ratio, parent, x0, y0, x1, y1) {
while (i0 < n) {
// Find the next non-empty node.
do sumValue = nodes[i1++].value
minValue = maxValue = sumValue
alpha = Math.max(dy / dx, dx / dy) / (value * ratio)
beta = sumValue * sumValue * alpha
minRatio = Math.max(maxValue / beta, beta / minValue)

// Keep adding nodes while the aspect ratio maintains or improves.
for (; i1 < n; ++i1) {
sumValue += nodeValue = nodes[i1].value
if (nodeValue < minValue) minValue = nodeValue
if (nodeValue > maxValue) maxValue = nodeValue
beta = sumValue * sumValue * alpha
newRatio = Math.max(maxValue / beta, beta / minValue)
if (newRatio > minRatio) {
sumValue -= nodeValue
break
}
minRatio = newRatio
}
}
}``````

#### treemapResquarify

treemapResquarify 首次布局采用 squarified 树图方式，保证具有较好的平均长宽比。后续即便是数据变化也只改变节点的大小，而不会改变节点的相对位置。这种布局方式在树图的动画表现上效果将会更好，因为避免了节点变动导致布局不稳定性，而这种不稳定可能会分散了人的注意力。

``````function resquarify(parent, x0, y0, x1, y1) {
if ((rows = parent._squarify) && rows.ratio === ratio) {
var rows,
row,
nodes,
i,
j = -1,
n,
m = rows.length,
value = parent.value
// 后续布局，只改变节点的大小，而不会改变相对位置
while (++j < m) {
;(row = rows[j]), (nodes = row.children)
for (i = row.value = 0, n = nodes.length; i < n; ++i) row.value += nodes[i].value
if (row.dice)
treemapDice(row, x0, y0, x1, value ? (y0 += ((y1 - y0) * row.value) / value) : y1)
else treemapSlice(row, x0, y0, value ? (x0 += ((x1 - x0) * row.value) / value) : x1, y1)
value -= row.value
}
} else {
// 首次布局采用 squarify 算法
parent._squarify = rows = squarifyRatio(ratio, parent, x0, y0, x1, y1)
rows.ratio = ratio
}
}``````

#### 总结

treemapBinary 良好 部分有序 一般
treemapSlice 很差 有序 优秀
treemapDice 很差 有序 优秀
treemapResquarify 良好 有序 优秀
treemapSquarify 优秀 部分有序 一般

## 让矩形树图更生动

#### 先来个 demo

``````[
{ value: 10, color: 'red' },
{ value: 7,  color: 'black' },
{ value: 4,  color: 'blue' },
...
]``````

``````[
{
x: 0,
y: 0,
width: 330.56,
height: 352.94,
data: { value: 10, color: 'red' },
},
{
x: 0,
y: 352.94,
width: 330.56,
height: 247.06,
data: { value: 7, color: 'black' },
},
{
x: 330.56,
y: 0,
width: 295.56,
height: 157.89,
data: { value: 4, color: 'blue' },
}
...
]``````

``````// requestAnimationFrame 循环动画
const builtGraphCanvas = () => {
// 主逻辑
treeMapAniLoop();
requestAnimationFrame(builtGraphCanvas);
};
builtGraphCanvas();

// 主逻辑
treeMapAniLoop() {
// 通过 time 自增，
time += 0.02
for (let i = 0; i < dataInput.length; i++) {
// 利用三角函数限制范围，来回改变输入
const increment = i % 2 == 0 ? Math.sin(time + i) : Math.cos(time + i)
// 赋值偏移量，改变初始数据范围
dataInput[i].value =
vote[i] + 0.2 * vote[vote.length - 1] * increment * increment
}

// treemapSquarify 算法生成结果
const result = getTreemap({
data: dataInput,      // 带偏移量的数据输入
width: canvasWidth,   // 画布宽
height: canvasHeight, // 画布高
})
}

``````

``````treeMapAniLoop() {
// 绘制 canvas 矩形
drawStrokeRoundRect() {
cxt.translate(x, y);
cxt.beginPath(0);
cxt.arc(width - radius, height - radius, radius, 0, Math.PI / 2);
...
cxt.fill();
cxt.stroke();
}
}
``````

#### 重排的原因

• 将子节点按顺序从大到小进行排列；
• 当一个节点开始填充时，存在 2 种选择：直接添加到当前行，或者固定当前行，在剩余的矩形空间中开始一个新行；
• 最终选择哪种，取决于哪种选择将带来更佳平均长宽比，长宽比越低，越能改善当前布局

...以此类推，采用策略是选择平均长宽比值更低的选择

#### 解决重排

``````this.treeMap = d3
.treemap()
.size([size.canvasWidth - size.arrowSize * 2, size.canvasHeight - size.arrowSize * 2])
.round(true)
// 期望最佳长宽比 ratio = 1
.tile(d3.treemapResquarify.ratio(1))``````

``````// 生成 treemap 结果
generateTreeMap(voteTree: Array) {
this.root.sum(function(d) {
if (d.hasOwnProperty('idx')) {
return treeData[d.idx - 1];
}
return d.value;
});

this.treeMap(this.root);
const leavesResult = this.root.leaves();

// 转换输出结构
this.result = leavesResult.map(i => ({
x: i.x0 + arrowSize,
y: i.y0 + arrowSize,
width: i.x1 - i.x0,
height: i.y1 - i.y0,
value: i.value,
}));
}``````

#### 转场动画

``````e2(t) {
return BezierEasing(0.25, 0.1, 0.25, 1.0)(t);
}
// 开场动画
if (this.time0 > 1 + timeOffset * result.length) {
this.time4 += 1.5 * aniSpeed;
const easing = this.e2(this.time4);
const resultA = this.cloneDeep(this.result);
// 转换动画，A 状态转换到 0 票白色状态
this.setTagByResult(resultA, this.initialZeroResult, easing);
}

//传入的两组 result 及补间参数 easing ，输出混合的 result。
setTagByResult(resultA, resultB, easing) {
const result = this.result;
for (let i = 0; i < result.length; i++) {
result[i].x = resultA[i].x + easing * (resultB[i].x - resultA[i].x);
result[i].y = resultA[i].y + easing * (resultB[i].y - resultA[i].y);

result[i].width =
resultA[i].width + easing * (resultB[i].width - resultA[i].width);
result[i].height =
resultA[i].height + easing * (resultB[i].height - resultA[i].height);
}
}``````

## 让排列错落有致

#### 极端场景显示问题

``````  // x=1-2区间，由双曲正切函数调整，输出增长率快到缓慢
const reviseMethod = i => Math.tanh(i / 20) * 26;
const computeVote = (vote: number, quota: number) => {
// 基底100 + 倍数 * 每倍的份额
return base + (vote / minVote - 1) * quota;
};

const stage1 = 10;
const stage2 = 30;
// 10倍区间
const ceilStage1 = 600;
// 30倍区间
const ceilStage2 = 1000;
// 30倍以上区间
const ceilStage3 = 1300;

let quota;
// 最大最小倍数比
const curMultiple = maxVote / minVote;
const data = voteList.map(i => {
let finalVote;

// 不同阶段处理方案
if (curMultiple <= stage1 + 1) {
quota = (ceilStage1 - base) / stage1;
const reviseValue = reviseMethod(i);
finalVote = computeVote(reviseValue, quota);
} else if (curMultiple <= stage2 + 1) {
quota = (ceilStage2 - base) / stage2;
finalVote = computeVote(i, quota);
} else {
// 需要隐藏部分票数，隐藏部分尖角等
quota = ceilStage3 / curMultiple;
finalVote = computeVote(i, quota);
}

return finalVote;
});
return data;
};``````

#### 排版太规整

``````// 初始带组的数据
export const dataGroupTree = {
name: 'allGroup',
children: [
{
name: 'group1',
children: [
{
idx: 1,
value: 1,
},
...
],
},
{
name: 'group2',
children: [
...
],
},
{
name: 'group3',
children: [
...
],
},
],
};``````