关于javascript:如何生成稳定的动态-treemap矩形树图关键技术揭晓

本文作者：好奇

前言

前段时间，网易云音乐上线了一个基于熟人社交投票玩法的 h5 流动，该流动根据投票数权重值来划分格子块，并通过格子块之间无缝挤压动效极大地减少了趣味性。本文将着重介绍如何基于 treemap（矩形树图）来实现一个稳固的动静格子块挤压成果以及在这其中遇到的一些问题。

矩形树图摸索

输出一组 18 个随机大小数值，如何在一张固定大小 canvas 画布上，让这组数据权重值映射在二维立体上并渲染出 18 个不同大小的格子？在视觉上可能产生显著可辨别的边界，让人一眼就能读出，哪几个格子的组成是最大的，哪几个格子组成仿佛是微不足道的？在前端工程化实际中，联想到 webpack 打包编译的场景，应用 webpack-bundle-analyzer 插件将生成一个蕴含所有打包文件的可视化矩形树图。尝试应用矩形树图兴许是一个思路，如下图所示：
​

​

算法的稳定性

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

常见的矩形树图

许多数据集实质上是分层的，一个好的档次可视化有利于疾速地多尺度辨别：对单个元素的宏观层面察看和对整体数据集的宏观层面察看。矩形树图实用于展现具备层级关系的数据，可能直观地体现同级之间的比拟。

以 d3-hierarchy 实现为例：

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

依据每个指定节点的子节点 value 值，对输出 x0, y0, x1, y1 坐标计算出的矩形区域，依照程度方向进行宰割。从给定矩形的左边缘 (x0) 坐标开始，宰割的子元素按顺序排列。

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

依据每个指定节点的子节点 value 值，对输出 x0, y0, x1, y1 坐标计算出的矩形区域，依照垂直方向进行宰割。从给定矩形的上边缘 (y0) 坐标开始，宰割的子元素按顺序排列。

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

如果指定节点的深度值为奇数，则执行 treemapSlice 否则执行 treemapDice。

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

示例图：

treemapSquarify

这种正方化（squarified）树图布局会尽可能的应用指定的纵横比（ratio）来切分矩形，使生成的矩形尽量靠近正方形，领有更佳的均匀长宽比。

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
    }
}

示例图：

具体矩形树图成果可查看 demo

总结

均匀长宽比是指生成的矩形长宽的比值，越佳的均匀长宽比，矩形越靠近正方形，用户观感的体验也越好。节点有序性是指输出数据权重值发生变化时，树图节点地位的变动水平。有序的节点，树图的稳定性也更加优良。

能够发现，treemapSquarify 领有更优良的均匀长宽比。绝对的，在首次布局时 treemapResquarify 也同样领有不错的均匀长宽比，在后续数据权重值发生变化时，因为节点的有序个性，treemapResquarify 也将有很好的稳定性。

让矩形树图更活泼

先来个 demo

基于 treemapSquarify 树图思路，开始一组 demo 测试。输出一组随机的带 value 值数据的入参：

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

执行 treemapSquarify 计算，对生成的后果进行转化解决，可失去一组带地位坐标和宽高大小的数据列表，如下所示：

[
    {
      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'},
    }
    ...
]

能够看到，输出的数据是一组随机的数组，通过 treemapSquarify 计算后，失去一组蕴含 x、y 坐标，width、height 大小的数据。基于这组初始输出数据，咱们给数据加一个偏移量。通过加一个工夫 time 自增量，利用三角函数个性，把偏移量限定在初始数据的肯定范畴内，就能失去一组初始数据偏移后的后果数据。通过一直来回扭转输出数据的偏移范畴，便能够继续地生成多组初始数据偏移后的后果数据。如下所示：

// 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, // 画布高
 })
}

依据取得的多组数据偏移返回的后果，在 canvas 画布上把 x、y 坐标和 width、height 大小绘制进去：

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

在浏览器 requestAnimationFrame 重绘办法中，因为初始输出数据在工夫自增下一直扭转偏移量，从而一直地生成一系列的后果数据，渲染动画如下：

格子重排

如上文所述，输出一组数据值，采纳 treemapSquarify 计算生成格子坐标和宽高，利用工夫自增使动画继续地“挤压”起来，这看起来很完满。试着更换几组不同的输出数据源，验证在各类输出场景下的渲染成果，其中一组如下所示：

请认真看，格子块在完满地“挤压”了短暂工夫后，呈现了跳动的景象。在理论的输出数据源测试中，发现格子呈现跳动的概率比拟高。这实际上是格子块产生了地位重排。如果咱们把初始数据生成的格子块在画布按标号 1-18 排序，发现最后在地位 3 的格子块，通过自增偏移变动后，再次计算生成的该格子块地位曾经变成了第 5。如果输出数据源差别较大时，这类地位的偏移将会更加重大。所以间接的表象就是，画布上的格子动画在不间断跳动，稳定性十分差，用户的观感体验也会不好。
​

重排的起因

如上文所述，treemapSquarify 使得生成的矩形尽量靠近正方形，领有很好的均匀长宽比。实际上，它并不会在一开始就同时思考所有层级该如何划分，这能防止带来很大的计算量。
其思维次要是：

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

以数据集 [3，2，6，4，1，2，6] 为例，排序后的序列为 [6, 6, 4, 3, 2, 2, 1]。
步骤 ①，格子块长度 4，宽度 1.5，故长宽比 4/1.5 = 2.6..
步骤 ②，格子块长度 3，宽度 2，故长宽比 3/2 = 1.5
… 以此类推，采纳策略是抉择均匀长宽比值更低的抉择

因而，如果对输出数据进行肯定的偏移时，treemapSquarify 的计算是贪婪的，它只会采纳以后最佳的长宽比抉择，故当偏移量超过某个边界值时必然会呈现输入的格子块地位不统一的状况，从而呈现重排的景象。

解决重排

其实，在上文总结矩形树图时就有提到，treemapResquarify 因为在首次布局时采纳的是 treemapSquarify，因而也同样领有很好均匀长宽比。当数据权重值发生变化时，因为 treemapResquarify 独有的节点有序个性，将具备良好的稳定性。因而，咱们采纳 treemapResquarify 算法来对输出值生成后果，如下所示：

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

依据输出值，失去 leavseResult 转换输入后果。此时，即使是对输出值做肯定的偏移，输入后果的地位也是稳固的。

// 生成 treemap 后果
generateTreeMap(voteTree: Array<number>) {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,
  }));
}

因为理论输出的偏移量并不会偏离初始数据很大，输入后果地位偏移的影响也绝对不会很大。

在采纳 treemapResquarify 来解决重排问题前，也尝试过一些其余的思路。比方，记录首次生成的计算结果，在执行输出数据自增偏移时，尝试去查看是否有格子“跳变”，如果查看到格子“跳变”的边界时，则尝试从以后格子的周边“借”一点格子空间，并阻止格子跳变，从而强制防止重排问题。但并不能很好解决这个问题，在某些输出数据反差较大时会呈现显著动画卡顿。

转场动画

除了上述已知票数的后果挤压动画，咱们还做了很多转场动画。细分的话能够分为 6 个场景，为了保障动画的流畅性，这 6 个场景都做在一张 canvas 画布里。以收场动画为例，格子块按程序逐步鼓起来再逐步放大到红色格子块状态，如下图所示

实现原理是，在肯定的工夫范畴内，从状态 A 过渡到状态 B。则把这段时间作为 BezierEasing 办法的自增变量输入一个贝塞尔动画值，每一帧都依据这个动画值扭转状态 A 的 x，y 坐标和 width，height 值，逐渐趋势状态 B，外围代码如下所示：

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);
  }
}

如下图所示，是一个已知的挤压后果页转场到红色格子块的抉择状态。实现的原理也是相似的，在肯定的工夫范畴内，通过扭转格子的坐标地位和大小，从挤压状态逐渐过渡到红色格子块状态。还有更多动画状态的变动，比方从一个“未抉择”的格子块状态变成“已抉择”状态；格子块选满当前，从“选满”状态过渡到后果挤压状态等，这里就不再详述了。

让排列错落有致

极其场景下的边界解决，永远是一个令人辣手的事件。
​

极其场景显示问题

能够设想，最高票数和最低票数相差很大的状况，就会呈现排版齐全凌乱的状况。
如下图所示，最高票数仅仅是 20 票，最低票数 0 票，就呈现了小的票数格子块空间被挤压到快“呼吸”不过去的状况。

如果辨别再显著一点，最高票数 140 票，最小票数 0 票，将变得更加凌乱，如下图所示：

因而，须要对输出数据源进行一个正当的转换，将超出最大倍数比的状况进行分状况解决，转化在一个正当的区间内。
最大倍数比分成 3 个阶段解决，别离是 10 倍，30 倍，30 倍以上区间。实际上，就是把一个不可预知的随机范畴转换成一个可控的正当区间内。

  // 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;
};

除了格子块的排版分区间解决，格子块外部的“表情”、“标签词”、“票数”也可能存在相互挤压、相互遮挡的状况。下图所示的是最早针对标签词列举的解决计划，理论须要解决场景远比这个多的多。包含的边界条件有：标签词主动横排，主动竖排解决，字体大小自适应，多个字不同解决，两两之间格子间遮挡解决等。列举可能呈现的任何一种边界状况，解决它！

排版太规整

如下图所示，动画看起来并没有什么问题。然而最高票数相比最低票数曾经超过 10 倍，咱们认为，动画的排版太“平均规整”了，以至于可能让人无奈一眼有所区别。为了谋求更加显著可辨别的排版，让格子块之间足够错乱有致，减少一些“凌乱之美”的气质。通过对初始输出数据源分组解决，可能比拟好地优化这个问题。

最后定义的 18 个输出数据源是并列在一个层级的。咱们构想，有没有可能把数据分组，则当数据映射到二维立体时，格子之间也被划分成多个模块展现，是不是就会更加错乱有致。如下代码所示，咱们把初始的票数值全副定为 1 票，定义多个 group 分组层级，理论的体现成果的确更加“凌乱”了。

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

带一点可恶尖角

一开始，咱们设计的挤压格子块带有一点尖角，如下图所示，在格子块边缘设计有可恶的尖角。然而咱们发现，在有些场景下尖角之间会存在相互遮挡甚至碰到格子表情的状况。因为须要针对性做边界解决，最初因为工夫关系被拿掉了。

其余问题

其实，除了上述列举一些问题以外，还遇到诸多大大小小的问题。
​
比方，对挤压动效截屏并转成图片分享进来是很重要的一个点。当咱们在对 canvas 画布进行截屏分享时，截屏的动作是基于 html2canvas 库的能力，但截屏进去的图片常常偶现空白，尝试在 canvas 绘制图片时对图片链接增加 crossOrigin=”anonymous” 属性发现解决了问题。起初又发现，在微信长按保留图片时，在局部安卓机型上仍然存在偶现截图图片空白的问题，最初通过在 canvas 绘制图片时把输出图片链接转成 base64 地址最终解决了该问题。
总之，想要实现一个可恶而”完满“地挤压成果，可能会遇到各种各样的问题，无他，解决它！

小结

最初，用海报一句话结尾：
它值得推敲，有点货色，少年感永不过期。

有趣味的同学能够在网易音乐 App 搜寻“泡泡”，体验一下。
​

参考资料

• ​Treemaps for space-constrained visualization of hierarchies
• Squarified Treemaps​
• d3-hierarchy
• d3-treemap-demo

本文公布自 网易云音乐大前端团队，文章未经受权禁止任何模式的转载。咱们长年招收前端、iOS、Android，如果你筹备换工作，又恰好喜爱云音乐，那就退出咱们 grp.music-fe(at)corp.netease.com！