使用 d3.js 力导布局绘制资源拓扑图

更多文章，参见大搜车技术博客：blog.souche.com/

大搜车无线开发中心持续招聘中，前端，Nodejs，android 均有 HC，简历直接发到：sunxinyu@souche.com

最近公司业务服务老出bug，各路大佬盯着链路图找问题找的头昏眼花。某天大佬丢了一张图过来“我们做一个资源拓扑图吧，方便大家找bug”。

就是这个图，应该是马爸爸家的

好吧，来仔细瞧瞧这个需求咋整呢。一圈资源围着一个中心的一个应用，用曲线连接起来，曲线中段记有应用与资源间的调用信息。emmm 这个看起来很像女神在遛一群舔狗... 啊不，是 d3.js 力导向图！

d3.js 力导向图

d3.js 是著名的数据可视化基础工具，他提供了基本的将数据映射至网页元素的能力，同时封装了大量实用的数据操作函数与图形算法。其中力导向图（Force-Directed Graph）是 d3.js 提供的一种十分经典的绘图算法。通过在二维空间里配置节点和连线，在各种各样力的作用下，节点间相互碰撞和运动并在这个过程中不断地降低能量，最终达到一种能量很低的安定状态，形成一种稳定的力导向图。

d3.js 力导向图中默认提供了 5 种作用力（以最新的 5.x 为准）：

中心力（Centering）

中心力作用于所有的节点而不是某些单独节点，可以将所有的节点的中心一致的向指定的位置移动，而且这种移动不会修改速度也不会影响节点间的相对位置。

碰撞力（Collision）

碰撞力将每个节点视为一个具有一定半径的圆，这个力会阻止代表节点的这个圆相互重叠，即两个节点间会相互碰撞，可以通过设置 strength 设置这个碰撞力的强度。

弹簧力（Links）

当两个节点通过设置 link 连接到一起后，可以设置弹簧力，这个力将根据两个节点间的距离将两个节点拉近或推远，力的强度和这个距离成比例就和弹簧一样。

电荷力（Many-Body）

通过设置 strength 来模拟所有节点间的相互作用力，如果为正节点间就会相互吸引，可以用来模拟电荷吸引力，如果为负节点间就会相互排斥。这个力的大小也和节点间的距离有关。

定位力（Positioning）

这个力可以将节点沿着指定的维度推向一个指定位置，比如通过设置 forceX 和 forceY 就可以在 X轴 和 Y轴 方向推或者拉所有的节点，forceRadial 则可以形成一个圆环把所有的节点都往这个圆环上相应的位置推。

回到这个需求上，其实可以把应用、所有的资源与调用信息都看成节点，资源之间通过一个较弱的弹簧力与调用信息连接起来，同时如果应用与资源间的调用有来有往，则在这两个调用信息之间加上一个较强的弹簧力。

ok说干就干

// 所有代码基于 typescript，省略部分代码
 
type INode = d3.SimulationNodeDatum & {
  id: string
  label: string;
  isAppNode?: boolean;
};
 
type ILink = d3.SimulationLinkDatum<INode> & {
  strength: number;
};
 
const nodes: INode[] = [...];
const links: ILink[] = [...];
 
const container = d3.select('container');
 
const svg = container.select('svg')
  .attr('width', width)
  .attr('height', height);
 
const html = container.append('div')
  .attr('class', styles.HtmlContainer);
 
// 创建一个弹簧力，根据 link 的 strength 值决定强度
const linkForce = d3.forceLink<INode, ILink>(links) 
  .id(node => node.id)
  // 资源节点与信息节点间的 strength 小一点，信息节点间的 strength 大一点
  .strength(link => link.strength);
 
const simulation = d3.forceSimulation<INode, ILink>(nodes)
  .force('link', linkForce)
  // 在 y轴 方向上施加一个力把整个图形压扁一点
  .force('yt', d3.forceY().strength(() => 0.025)) 
  .force('yb', d3.forceY(height).strength(() => 0.025))
  // 节点间相互排斥的电磁力
  .force('charge', d3.forceManyBody<INode>().strength(-400))
  // 避免节点相互覆盖
  .force('collision', d3.forceCollide().radius(d => 4))
  .force('center', d3.forceCenter(width / 2, height / 2))
  .stop();
 
// 手动调用 tick 使布局达到稳定状态
for (let i = 0, n = Math.ceil(Math.log(simulation.alphaMin()) / Math.log(1 - simulation.alphaDecay())); i < n; ++i) {
  simulation.tick();
}
 
const nodeElements = svg.append('g')
  .selectAll('circle')
  .data(nodes)
  .enter().append('circle')
    .attr('r', 10)
    .attr('fill', getNodeColor);
 
const labelElements = svg.append('g')
  .selectAll('text')
  .data(nodes)
  .enter().append('text')
    .text(node => node.label)
    .attr('font-size', 15);
 
const pathElements = svg.append('g')
  .selectAll('line')
  .data(links)
  .enter().append('line')
    .attr('stroke-width', 1)
    .attr('stroke', '#E5E5E5');
 
const render = () => {
  nodeElements
    .attr('cx', node => node.x!)
    .attr('cy', node => node.y!);
  labelElements
    .attr('x', node => node.x!)
    .attr('y', node => node.y!);
  pathElements
    .attr('x1', link => link.source.x)
    .attr('y1', link => link.source.y)
    .attr('x2', link => link.target.x)
    .attr('y2', link => link.target.y);
}
 
render();
复制代码

效果如下：

ok 已经基本实现啦，那就这样啦，等后台同学实现一下接口就可以上线啦，日均UV两位数的产品要啥自行车，有的看就不错了（手动二哈）。

当然不行了，有这么一个都市传说，中台产品的好用与否与离职率高低成相关关系。本来需要打开资源拓扑图就是一件很?的事了，再看到这么一款体验极差的产品，感觉分分钟就要离职了。为了给我司年交易额两万亿的长远目标添砖加瓦，我们来看看有啥需要改进的地方。

至少字给我居中吧

注意到我们的字都是左下角定位到节点中心的，这是因为我们使用的是 svg 的 text 元素，默认情况下给 text 元素设置的 x 和 y 代表了 text 元素 baseLine 的起始位置。当然我们可以通过直接设置 dx 与 dy 设置一个偏移量来完成居中的问题，但考虑到 svg 元素相比普通的 html 元素毕竟还是有所限制，并不方便将来的扩展啥的，所以我们索性把所有的圆点与文字都换成 html 元素。

...
 
const nodeElements = html.append('div')
  .selectAll('div')
  .data(nodes.filter(node => node.isAppNode))
  .enter().append('div')
    // css modules
    .attr('class', styles.NodeItem)
    .html((node: INode) => {
      return `<p>${node.id}</p>`;
    });
 
const labelElements = html.append('div')
  .selectAll('div')
  .data(nodes.filter(node => !node.isAppNode))
  .enter().append('div')
    // css modules
    .attr('class', styles.LabelItem)
    .html(node => `
      <p>${node.label}</p>
      <p>Avada Kedavra!</p>
    `);
 
...
 
const render = () => {
  nodeElements
    .attr('style', (node) => {
      return `transform: translate3d(calc(${node.x}px - 50%), calc(${node.y}px - 50%), 0);`;
    });
 
  labelElements
    .attr('style', (node) => {
      return `transform: translate3d(calc(${node.x}px - 50%), calc(${node.y}px - 50%), 0);`;
    });
}
复制代码

效果如下：

字都居中了！

这个线怎么跟激光似的，一点也不像在遛舔狗

再来看看这个线，我们一开始是把所有代表弹簧力的线段当成直线就画上去了，但这样看起来很生硬效果很差。实际上我们需要的是一条自然的曲线把资源节点和应用节点连接起来，同时穿过信息节点，所以问题就变成了如何穿过三个点画一条曲线。

要画曲线自然要用到 svg 的 path 元素和他的 d 绘制指令，关于怎么用 path 画曲线，这里和MDN上都有很详细的教程。在具体实际项目应用中，一般来说贝塞尔曲线会比较难把控也比较难获得较好的效果，所以我们使用 A 指令来画这个弧线。

使用 A 指令画弧线，需要知道的元素有：x轴半径，y轴半径，弧形旋转角度，角度大小flag，弧线方向flag，弧形的终点。那在已知三个点坐标的情况下，怎么求出这些元素呢？是时候复习一波三角函数了。

已知 A、B、C 坐标（x_ay_a、x_by_b、x_cy_c），则可求得 a、b、c 长度（Math.sqrt((x₁-x₂)² - (y₁-y₂)²），再根据余弦定理可求得∠C，再根据正弦定理可得r，具体参看代码：

type IVisualLink = {
  id: string;
  start: number[];
  middle: number[];
  end: number[];
  arcPath: string;
  hasReverseVisualLink: boolean;
};
 
const visualLinks: IVisualLink[] = [...];
 
function dist(a: number[], b: number[]) {
  return Math.sqrt(
    Math.pow(a[0] - b[0], 2) +
    Math.pow(a[1] - b[1], 2));
}
 
...
 
const pathElements = svg.append('g')
  .selectAll('path')
  .data(visualLinks)
  .enter().append('path')
    .attr('fill', 'none')
    .attr('stroke-width', 1)
    .attr('stroke', '#E5E5E5');
 
...
 
const render = () => {
  ...
 
  nodes
    // 过滤出所有的信息节点
    .filter(node => !node.isAppNode)
    .forEach((node) => {
      ...
      // 根据信息节点的信息得到对应的 visualLink 对象 index
      const idx = findVisualLinkIndex(node)
      visualLinks[idx].start = [source.x!, source.y!];
      visualLinks[idx].middle = [node.x!, node.y!];
      visualLinks[idx].end = [target.x!, target.y!];
 
      const A = visualLinks[idx].start;
      const B = visualLinks[idx].end;
      const C = visualLinks[idx].middle;
 
      const a = dist(B, C);
      const b = dist(C, A);
      const c = dist(A, B);
 
      // 余弦定理求得∠C
      const angle = Math.acos((a * a + b * b - c * c) / (2 * a * b));
      // 正弦定理求得外接圆半径
      const r = _.round(c / Math.sin(angle) / 2, 4);
 
      // 角度大小flag，因为我们要的是条弧线而不是一个残缺的圆，所以恒为0
      const laf = 0;
 
      // 弧线方向flag，根据AB的斜率判断C在AB线的那一边，再确定弧线方向
      const saf = +((B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0]) < 0);
 
      const arcPath = ['M', A, 'A', r, r, 0, laf, saf, B].join(' ');
 
      visualLinks[idx].arcPath = arcPath;
    });
 
  pathElements
    .attr('d', (link) => {
      return link.arcPath;
    });
}
 
复制代码

效果如下：

这些线一对A都没有，分不清正反啊

应用与资源间的关系，是有方向的，大部分情况下是应用调用资源，也有情况会有双向的调用，除了文字意外，我们还需要加上箭头来表明是谁在调用谁。怎么加这个箭头呢？svg 的 path 元素有一个 marker-end 属性，通过设置这个属性可以可以将一个 svg 元素绘制到 path 元素最后的向量上。

 
// 在 svg 元素中添加一个 marker 元素
<svg>
  <marker
    id="arrow"
    viewBox="-10 -10 20 20"
    markerWidth="20"
    markerHeight="20"
    orient="auto"
  >
    <path
      d="M-6.75,-6.75 L 0,0 L -6.75,6.75"
      fill="none"
      stroke="#E5E5E5"
    />
  </marker>
</svg>
 
...
 
const pathElements = svg.append('g')
  .selectAll('path')
  .data(visualLinks)
  .enter().append('path')
    .attr('fill', 'none')
    // 设置 marker-end 属性
    .attr('marker-end', 'url(#arrow)')
    .attr('id', link => link.id)
    .attr('stroke-width', 1)
    .attr('stroke', '#E5E5E5');
 
...
复制代码

但直接这样写的话，效果会很差，为啥呢？因为我们 path 元素的起点与终点是节点的中心点，直接这样的话箭头都在节点上面，如图：

看到中间那朵菊花没

所以我们没法直接通过加这个属性来加上箭头，我们需要对 path 做一些处理，对 path 线段去头去尾。那怎么做呢？还好有巨佬已经实现了一种算法，算出两个 path 元素之间的交点，因此我们可以在算出原 arcPath 后，再算出这条弧线与节点外一个大一点的圆的交点，再把原 arcPath 的起点与终点移到这两个点上。

import intersect from 'path-intersection';
 
const render = () => {
  ...
 
  nodes
    // 过滤出所有的信息节点
    .filter(node => !node.isAppNode)
    .forEach((node) => {
      ...
      // 根据信息节点的信息得到对应的 visualLink 对象 index
      const idx = findVisualLinkIndex(node)
      visualLinks[idx].start = [source.x!, source.y!];
      visualLinks[idx].middle = [node.x!, node.y!];
      visualLinks[idx].end = [target.x!, target.y!];
 
      const A = visualLinks[idx].start;
      const B = visualLinks[idx].end;
      const C = visualLinks[idx].middle;
 
      const a = dist(B, C);
      const b = dist(C, A);
      const c = dist(A, B);
 
      // 余弦定理求得∠C
      const angle = Math.acos((a * a + b * b - c * c) / (2 * a * b));
      // 正弦定理求得外接圆半径
      const r = _.round(c / Math.sin(angle) / 2, 4);
 
      // 角度大小flag，因为我们要的是条弧线而不是一个残缺的圆，所以恒为0
      const laf = 0;
 
      // 弧线方向flag，根据AB的斜率判断C在AB线的那一边，再确定弧线方向
      const saf = +((B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0]) < 0);
 
      const origArcPath = ['M', A, 'A', r, r, 0, laf, saf, B].join(' ');
 
      const raidus = NODE_RADIUS;
      const startCirclePath = [
        'M', A,
        'm', [-raidus, 0],
        'a', raidus, raidus, 0, 1, 0, [raidus * 2, 0],
        'a', raidus, raidus, 0, 1, 0, [-raidus * 2, 0],
      ].join(' ');
      const endCirclePath = [
        'M', B,
        'm', [-raidus, 0],
        'a', raidus, raidus, 0, 1, 0, [raidus * 2, 0],
        'a', raidus, raidus, 0, 1, 0, [-raidus * 2, 0],
      ].join(' ');
 
      const startIntersection = intersect(origArcPath, startCirclePath)[0];
      const endIntersection = intersect(origArcPath, endCirclePath)[0];
 
      const arcPath = [
        'M', [startIntersection.x, startIntersection.y],
        'A', r, r, 0, laf, saf, [endIntersection.x, endIntersection.y],
      ].join(' ');
 
      visualLinks[idx].arcPath = arcPath;
    });
 
  pathElements
    .attr('d', (link) => {
      return link.arcPath;
    });
 
  ...
}
 
复制代码

效果已经很接近了！

字叠到一起啦，臣妾看不清啊

到这一步整体效果其实已经差不多了，但追求完美的我们怎么可能到此为止呢？仔细看看这个图，因为调用信息是一个方盒而不是原型的节点，如果应用和资源间有来有往，那这个字很容易叠到一起。可以尝试调整碰撞力（Collision）和弹簧力（Links）来让他们别叠到一起，不过试下来发现调整这两个系数很容易把整个图弄得乱七八糟的。那咋办呢？我们就要到此为止了吗？不妨换个思路，如果应用与资源间有来有往，则这个连接信息就不放到中间点，而是放到开始三分之一处。

说的挺好，我咋知道开始三分之一处在哪？

还好这种「复杂」的数学问题，前人已经帮我们探索的差不多了。svg 标准里定义了 SVGGeometryElement.getTotalLength 与 SVGGeometryElement.getPointAtLength 两个方法，通过这两个方法我们可以获得 path 路径的全长，和某一长度时点的位置。不过这两个方法都是附在 DOM 元素上的，直接调用有点麻烦，还好有 PureJS 的实现：

import { svgPathProperties } from 'svg-path-properties';
 
...
 
render = () => {
  ...
 
  labelElements
    .attr('style', (link) => {
      const properties = svgPathProperties(link.arcPath);
      const totalLength = properties.getTotalLength();
      const point = properties.getPointAtLength(
        link.hasReverseVisualLink ? totalLength / 3 : totalLength / 2,
      );
 
      return `transform: translate3d(calc(${point.x}px - 50%), calc(${point.y}px - 50%), 0);`;
    });
 
  ...
}
复制代码

最终效果：

还差一点

效果做到这已经差不多了，不过还有一些不完美的地方

• 各种力的系数，在数据不同时不能通用，还必须根据数据不同试出来一个相对通用的系数函数。
• 不能保证所有的节点都在方框内且不重叠

感觉这两个问题都算是力导布局的固有缺陷，可能那张图的实现根本和力导布局没啥关系呢?。不过我们使用力导布局也可以实现不错的效果，这种 edge case 可以慢慢来解决了就。

Fin