绘制出数万条节点、边的拓扑图

关于我使用svg + d3js 使浏览器支持绘制出数万级别的拓扑图。在我同事高性能笔记本上支持到了8w, 还可以正常操作。

针对拓扑图的需求一般要求都是数量级别能支持越多越好，但是由于浏览器性能问题，一般再没做啥优化，能支持到5000点差不多也就是极限了。那么接下来就一步一步聊聊我是怎么能支持到数万级别的。

优化一避免程序中出现两层循环的情况

避免出现两层循环嵌套的情况，比如：

示例一：

const data = [];
const data1 = [];

// forEach 、includes 两层嵌套循环 如果data是1w条数据、data1是1w  就等于 10000 * 10000次循环
data.forEach((item) => {
  if(data1.includes(item)) {
    // 
  }
});

像 filter、map、forEach、find、findIndex、includes、some、every、indexOf 等都是一次循环，切记一定要避免嵌套循环

示例二：使用MAP解决需要多层嵌套的场景

const data = [];
const data1 = [];

const dataMap = new Map();

data1.forEach((item) => {
  dataMap.set(item, true);
});

data.forEach((item) => {
  if(dataMap.has(item)) { // 使用Map 去判断
    // 
  }
});

优化二屏幕外节点边不去绘制

像地图、游戏里面的万人同屏的概念，其实都是处理当前视口的数据。就是用户看到的就那一块，屏幕外面的随着画布移动去逐步绘制，然后把不在视口内的都删除掉。

那肯定就需要一个算法，咱们需要分析一点就是以当前画布容器作为视口，也就是获取容器的宽度、高度作为矩形的边。

节点的基本数据结构如下：

interface NodeProps {
  id: string,
  x: number,
  y: number,
  [propName: string]: any,
}

节点都是有x、y坐标的，计算节点在不在当前视口内是：

//判断节点在不在屏幕上
export function verifyNodeInMainScreen(transform = {x: 0, y: 0, k: 1}, nodes = []) {
  const { offsetWidth, offsetHeight } = document.querySelector('#main'); // 我的画布容器
  const {  x: transX, y: transY, k: scale } = transform; // zoom值  左右移动（x、k）、缩放(k)
  const maxX = offsetWidth * 1.2; // 让视口稍微大点 优化界面能明显看到点新增、删除动作。
  const maxY = offsetHeight * 1.2;
  const minX = 0 - offsetWidth * 0.2;
  const minY = 0 - offsetHeight * 0.2;
  const screenNodes = nodes.filter(item => {
    const x = (item.x * scale + transX);
    const y = (item.y * scale + transY);
   
    if (x >= minX & x <= maxX & y >= minY & y <= maxY) {
      return item;
    }
  });
   
  return screenNodes;
}

算法:

p0等于矩形的左上角坐标下{x1,y1}, p1等于右下角坐标{x2, y2}。

在咱们的项目中因为运用到zoom，这些要在对节点的{x, y}经行缩放、平移，也就是：const x = x * scale + transX， const y = y * scale + transY。

判断一个点在矩形上是大于等于p0, 小于等于p1（x >= minX & x <= maxX & y >= minY & y <= maxY）。

矩形坐标获取：

p0{x1: 0, y1: 0} 也就是0初始值的位置
p1{x2: windth, y2: height }也就容器的width、height。

优化点： 让画布容器范围扩大1.2倍（maxX、maxY、minX、minY），有预加载的效果，不让用户明显感觉到会有节点再新增、删除的动作。

优化三屏幕外连线不去绘制

节点都判断了，那么topo的连线也要相应的做视口内是否绘制了。

咱们就以直线作为咱们的例子吧。俩点绘制出一条边数据结构是这个样的:

interface EdgeProps {
  id: string,
  source: string,
  target: string,
  [propName: string]: any,
}

source代表一个节点（原节点）节点ID，target（目标）代表一个节点ID，使之绘制成一条边（path: M L）。

问：那么怎么计算这条边在不在画布上呢？

答： 简单点就是判断source节点和target节点是不是都不在画布了！如果都不在了就证明该连线不在画布上了。代码如下：

//判断连线在不在屏幕上
export function verifyEdgeInMainScreen(transform = {x: 0, y: 0, k: 1}, edges = [], nodeMap = new Map()) {
  const { offsetWidth, offsetHeight } = document.querySelector('#main');
  const {  x: transX, y: transY, k: scale } = transform;
  const maxX = offsetWidth * 1.2;
  const maxY = offsetHeight * 1.2;
  const minX = 0 - offsetWidth * 0.2;
  const minY = 0 - offsetHeight * 0.2;
   
  const screenEdges = edges.filter(item => {
    const target = nodeMap.get(`node${item.target}`); // nodeMap 是我根据node${节点ID}生成的Map， 千万不要用数组去查！！！！ 转成MAP对象再去找
    const source = nodeMap.get(`node${item.source}`);
    const x1 = source.x * scale + transX;
    const y1 = source.y * scale + transY;
    const x2 = target.x * scale + transX;
    const y2 = target.y * scale + transY;
   
    if ((x1 >= minX & x1 <= maxX & y1 >= minY & y1 <= maxY) || (x2 >= minX & x2 <= maxX & y2 >= minY & y2 <= maxY)) {
      return item;
    }
  });
   
  return screenEdges;
}

算法同节点计算x >= minX & x <= maxX & y >= minY & y <= maxY不过是要计算俩个节点。
nodeMap 一定要是个Map，可不能直接用nodes.find()去查，每次去查会慢很多！！！

nodeMap 如下：

const nodeMap = new Map();
nodes.forEach((item) => {
  nodeMap.set(`node${item.id}`, item);
});

其实还会出现下面的情况就是：经过缩放会两个点都不在屏幕上了，但是连线还在，这种情况下连线就会被删除了。如下图：

问：怎么解决这种情况呢？
答：判断连线是否交错！以画布边框为4条边，判断4条边是否跟连线交错！！，这个还是看你们会不会需要吧！！由于多增加计算，肯定会对性能造成影响的，计算连线是否交错代码如下：

/*
* 如果线段A两个端点分别在B线段的两侧，同时B线段的两个端点也在线段A的两侧，则线段A和B相交。
* 主要通过向量叉积进行判读，叉积大于0，改点在向量顺时针方向，小于0，在逆时针方向，等于0，在直线上
* 线段A: a(x, y)、b(x, y) 线段B：c(x, y)、d(x, y)
* u => (c - a) x (b - a)
* v => (d - a) x (b - a)
* w => (a - c) x (d - c)
* z => (b - c) x (d - c)
*/
export const crossLine = (a, b, c, d) => {
  // 判读线段（a, b）和线段（c, d）是否相交
  const u = (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
  const v = (d.x - a.x) * (b.y - a.y) - (b.x - a.x) * (d.y - a.y);
  const w = (a.x - c.x) * (d.y - c.y) - (d.x - c.x) * (a.y - c.y);
  const z = (b.x - c.x) * (d.y - c.y) - (d.x - c.x) * (b.y - c.y);
  return u * v < 0 && w * z < 0;
};

加入连线交错判断的相关代码如下：

//判断连线在不在屏幕上
export function verifyEdgeInMainScreen(transform = {x: 0, y: 0, k: 1}, edges = [], nodeMap = new Map()) {
  const { offsetWidth, offsetHeight } = document.querySelector('#main');
  const {  x: transX, y: transY, k: scale } = transform;
  const maxX = offsetWidth * 1.2;
  const maxY = offsetHeight * 1.2;
  const minX = 0 - offsetWidth * 0.2;
  const minY = 0 - offsetHeight * 0.2;

  const lineSegmentGroup = [ 
    [{ x: minX, y: minY }, { x: minX, y: maxY }], // top
    [{ x: minX, y: minY }, { x: maxX, y: minY }], // left
    [{ x: maxX, y: minY }, { x: maxX, y: maxY }], // bottom
    [{ x: minX, y: maxY }, { x: maxX, y: maxY }], // right
  ];
   
  const screenEdges = edges.filter(item => {
    const target = nodeMap.get(`node${item.target}`); // nodeMap 是我根据node${节点ID}生成的Map， 千万不要用数组去查！！！！ 转成MAP对象再去找
    const source = nodeMap.get(`node${item.source}`);
    const x1 = source.x * scale + transX;
    const y1 = source.y * scale + transY;
    const x2 = target.x * scale + transX;
    const y2 = target.y * scale + transY;
   
    if ((x1 >= minX & x1 <= maxX & y1 >= minY & y1 <= maxY) || (x2 >= minX & x2 <= maxX & y2 >= minY & y2 <= maxY)) {
      return item;
    }

    if (lineSegmentGroup.some(([a1, a2]) => crossLine(a1, a2, { x: x1, y: y1 }, { x: x2, y: y2 }))) {
      return item;
    }

    return false;
  });
   
  return screenEdges;
}

lineSegmentGroup 是已画布的边计算出来的top、left、right、bottom。

优化四对Zoom进行优化

zoom 是画布移动、缩放一直再刷的，那么咱们计算在不在屏幕上的算法verifyNodeInMainScreen、verifyEdgeInMainScreen调用的过于频繁的话也会有性能压力的，这个时候咱们就需要加点节流了。

下面是zoom的一小段代码(对zoom不太了解的可以去看我另外一篇文章)：

let throttleTimer = null;

d3.zoom()
  .scaleExtent([this.zoomMin, this.zoomMax])
  .extent([
    [0, 0],
    [this.width, this.height],
  ])
  .on('zoom', function onZoom() {
     const transform = d3.zoomTransform(this);

     // 实现一个节流
     if(throttleTimer) return;

     throttleTimer = setTimeout(() => {
       // verifyNodeInMainScreen、verifyEdgeInMainScreen 调用
     }, 300)
  });

优化五对展现形态进行优化

咱们正常一个topo图展现可能会又几个部分组成节点：

圆也就是背景;
icon 也就是表示节点的类型；
节点下面的描述文字;
其他

连线：

连线
箭头
连线文字
其他

假如用户对性能有大要求，而且呢能接受再缩小到一定范围了展示一个简易的形态（如果接受不了就尝试说服他），其实再缩小到某种程度下，已经看不清节点的具体信息了, 简易形态也还好吧！！！

简易形态就是由下组成，绘制的元素少了自然性能就上去了：

节点：

圆也就是背景;

连线：

连线；

假如以zoom值0.5做为分界，大于等于0.5是完整形态，小于0.5是简易形态，如下：。

let throttleTimer = null;

d3.zoom()
  .scaleExtent([this.zoomMin, this.zoomMax])
  .extent([
    [0, 0],
    [this.width, this.height],
  ])
  .on('zoom', function onZoom() {
     const transform = d3.zoomTransform(this);
     
     if(transform.k < 0.5) {
       // 这个时候就绘制成简易形态
     } else {
       // 这个时候就绘制成完整形态
     }


     // 实现一个节流
     if(throttleTimer) return;
     throttleTimer = setTimeout(() => {
       // verifyNodeInMainScreen、verifyEdgeInMainScreen 调用
     }, 300)
  });

优化六数据分层

数据分层update、remove、add。绘制的时候只绘制add、删除只删除remove、修改只修改update。

算法如下：(详情拆解可以看我上篇文章:重写d3数据绑定算法)

import { isEqual } from 'lodash';

export function diffLayered(newData, lastData, key = 'id') {
  const newDataMap = new Map();
  const lastDataMap = new Map();
  const update = [];
  lastData.forEach((item) => lastDataMap.set(item[key], item));

  const add = newData.filter((item) => { // add
    newDataMap.set(item[key], item);
    const last = lastDataMap.get(item[key]);
    if (!last) {
      return item;
    }

    // update
    if (!isEqual(last, item)) { // 没有引入loadsh的 可以简单用JSON.stringify(last) !== JSON.stringify(item) 做对比
      update.push(item);
    }

    return false;
  });

  const remove = lastData.filter((item) => !newDataMap.get(item[key])); //remove

  return { add, remove, update };
}

还是以verifyNodeInMainScreen、verifyEdgeInMainScreen做优化如下：

let lastInScreenNodes = [];
let lastInScreenEdges = [];

d3.zoom()
  .scaleExtent([this.zoomMin, this.zoomMax])
  .extent([
    [0, 0],
    [this.width, this.height],
  ])
  .on('zoom', function onZoom() {
     const transform = d3.zoomTransform(this);
     
     if(transform.k < 0.5) {
       // 这个时候就绘制成简易形态
     } else {
       // 这个时候就绘制成完整形态
     }

     // 实现一个节流
     if(throttleTimer) return;
     throttleTimer = setTimeout(() => { 
      // 1、verifyNodeInMainScreen、verifyEdgeInMainScreen 调用 获取到当前再屏幕的节点、边
      const currentNodes = verifyNodeInMainScreen(); 
      const currentEdges = verifyEdgeInMainScreen();

      // 2、以当前再屏幕的节点、边 跟上一次再屏幕上的节点、边做对比，  找出需要add、update、remove 的数据。
      const diffNodes = diffByGraph(currentNodes, lastInScreenNodes);
      const diffEdges = diffByGraph(currentEdges, lastInScreenEdges);

      //  3、对diffNodes、diffEdges新增、删除、修改处理 调用尼的绘制相关方法
      
       // 4、记录这一次再屏幕上的节点、边
      lastInScreenNodes = cloneDeep(currentNodes);
      lastInScreenEdges = cloneDeep(currentEdges);
     }, 300)
  });

1、verifyNodeInMainScreen、verifyEdgeInMainScreen 调用获取到当前再屏幕的节点、边
2、以当前再屏幕的节点、边跟上一次再屏幕上的节点、边做对比，找出需要add、update、remove 的数据。
3、3、对diffNodes、diffEdges新增、删除、修改处理调用尼的绘制相关方法 4、记录这一次再屏幕上的节点、边

优化七分时

其实再咱们大数据2w个节点、边给到的时候直接去交给浏览器去绘制的话，会造成浏览器的暂时卡顿。这个时间卡顿的时间是尼的数据量决定的。

问：怎么解决这个情况呢？
答：咱们可以分批次把咱们的数据交给浏览器去绘制！！

分时函数！！ 详细可以去看我的这块文章分时函数

什么是分时函数呢？比如你需要新增1000个div到body, 这个时候直接绘制1000个div到body,其实浏览器是非常有压力的。但是如果把这个1000个div用50m分批绘制，一批200个（10m）, 那这个时候浏览器的压力就小了。这个就是分时，那分时函数当然就是咱们把逻辑封装成函数了

优化八节点拖拽

节点支持拖拽是每个topo图的基本功能了。那咱们就针对他进行优化！

咱们可以把drag 分为三个阶段：

darg start 开始拖拽前
dragging 拖拽中
darg end 拖拽结束

本身我的元素是圆、icon、文字 这3部分使用g标签包裹的，再拖拽的时候需要更改是圆、icon、文字对应的x、y位置

拖拽优化一: 把g标签替换成svg标签对元素进行包裹！！！换成后咱们再拖拽的时候只需要改变svg的x、y即可！！

关于g标签的简单介绍：

元素g是用来组合对象的容器。添加到g元素上的变换会应用到其所有的子元素上。添加到g元素的属性会被其所有的子元素继承。此外，g元素也可以用来定义复杂的对象，之后可以通过元素来引用它们。 g是能实现元素的属性继承: stroke、fill、stroke-width、transform…。 他设置x、y不生效！！

关于svg标签的简单介绍：

svg标签经常用作包括整个svg的容器。常用的属性有：x, y, width, height, version。在我们导出项目中的svg的时候需要给svg添加上命名空间，不然浏览器就会抛没有命名空间的错误了（代码如下：）

html

<svg width="160px" height="160px"  version="1.1" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"></svg>

拖拽优化二: darg start 开始拖拽前, 这个时候咱们需要把咱们需要改动的元素(nodes、edges)都提前获取到，存放一下。再拖拽的时候就可以直接更改x、y了, 不要再拖拽中阶段去获取要拖拽的节点、边，每次都获取会给你照成卡顿的

优化九创建文档碎片 `createDocumentFragment()`

createDocumentFragment 因为文档片段存在于内存中，并不在 DOM 树中，所以将子元素插入到文档片段时不会引起页面回流（对元素位置和几何上的计算）。因此，使用文档片段通常会带来更好的性能。

大致就是不会append 多次，先放再内存中，最后一次整体append到dom上！！ 能提升绘制效率1-3倍。

let groupNodes = d3.select('#groupNodes');
let groupFrag = document.createDocumentFragment();
let d3GroupFrag = d3.select(groupFrag);

/**
 * d3GroupFrag 正常append 内容
 */

groupNodes.node().append(groupFrag);

优化十保存视图优化

再有大数据由于修改位置、新增节点、删除节点等相关更改后，需要保存视图会很慢！！！这个交互是非常庞大的。

保存优化一：如果保存后就离开当前界面了，可以使用异步请求，发出保存命令（调用接口）。然后默认提示保存成功，让其离开，不照成他的界面UI卡顿，保存中

保存优化二：提前获取到需要的数据（比如拖拽对节点位置进行更改了，就把它记录再saveUpdate里面，删除saveRemove、新增saveAdd同理），不要再点击保存再计算是有那些更改的，再传给服务端的。）

优化十一 WebWorker

前端多线程 web worker，由于我们是需要前端进行数据统计的，会对节点、边上的属性字段有一些count、groupBy、sum等统计会用到。

但其实再经过大数据交互的时候，也会有部分卡顿，它其实更适合做单纯的计算，对字段统计来说你需要把大数据交给它，然后它再吐出来统计后的数据，这个交互的大数据也会照成卡顿。

这篇是我再项目实战做的总结：前端多线程Web Worker

优化十一 WASM (WebAssembly)

wasm 确实单纯计算是很快的我们也使用了。比如找出100000中找出所有质数，分别交给js和wasm去做计算，同样的算法逻辑。要快了3-5倍。

WebAssembly的相关介绍

但是针对我们做统计不是很合适，我们把10w数据塞到wasm中会直接照成界面卡顿，最后放弃！！！！

优化十二样式

我们是支持对节点、边进行样式修改的比如：

圆的背景支持更改
icon支持切换
支持更改圆的大小
支持更改连线的宽度
还支持条件规则配置（以什么字段不等于、等于、大于、小于、不包含、包含等相关规则）。

本身存储的是一条条规则对应的样式 condition 例如一个简单的（我们支持and or各种字段递归等情况）

const condition = {field: 'total', operator: '大于'， value: 100000 };

可能对应的是style是这个样的

const style = { radius: 5, color: 'red', bgColor: 'red', lineWidth: 10, icon: 'icon-10'};

那么再初始化画布的时候我需要获取所有规则条件condition 一个一个去解析最后赋值给nodes、edges样式，再大数据下这个过程的算法我们都优化了最后还是会要3-5s左右，这个时间影响的是界面绘制的时间，当然很重要！！！。

优化：做缓存，把已经解析过的规则做缓存。例如：

const styleMap =  {
 node: {
   // 以条件规则ID 作为KEY
    '条件规则ID': { icon: 'icon-10', ids: [
      // ids 存放的是node  符合的id
    ]}, 
 },
 edge: {
   // 以条件规则ID 作为KEY
    '条件规则ID': { lineWidth: 10, ids: [
      // ids 存放的是edge  符合的id
    ]}, 
 },
}

维护一份样式的缓存（再设置等时候去更新这份缓存），优先去这份缓存里面取样式，取不到再去condition中去解析各种规则！！！

优化十三本地缓存 indexDB

再我们请求接口获取数据的时候由于数据量过大10w，这个时候就是服务端已经做过各种缓存了依然会再获取到用时2-5s 左右。这不是我们期望看到的！！

我们使用indexDB做缓存也就是说只要尼的磁盘还有空间我们就会做本地缓存，我们缓存再20个视图左右(edges、nodes、styleMap)，维护一份这个数据，再新视图就把最早的视图给清理掉。用的是任务名称+视图ID做为key。再本地已经有该视图数据了, 我们就不会去请求服务端数据了。

成果：本地缓存取数据超级快10w数据500ms。

关于IndexBD的使用我用的是基于localforage去封装使用的如下：

import localforage from 'localforage';

interface BaseStorageProps {
  getItem<T>(key: string): Promise<T | null>;
  setItem<T>(key: string, value: T): Promise<T>;
  removeItem(key: string): Promise<void>;
  keys(): Promise<Array<string>>;
  clear(): Promise<void>;
  getInstance(name: string): BaseStorageProps;
}

class Storage implements BaseStorageProps {
  private store: LocalForage;

  constructor(name: string) {
    this.store = localforage.createInstance({
      name
    });
  }

  public getItem<T>(key: string): Promise<T | null> {
    return this.store.getItem(key);
  }

  public setItem<T>(key: string, value: T): Promise<T> {
    return this.store.setItem(key, value);
  }

  public removeItem(key: string): Promise<void> {
    return this.store.removeItem(key);
  }

  public keys(): Promise<string[]> {
    return this.store.keys();
  }

  public clear(): Promise<void> {
    return this.store.clear();
  }

  public getInstance(name: string): Storage {
    return new Storage(name);
  }
}

export { Storage };
export default new Storage('global-storage');

绘制出数万条节点、边的拓扑图 ​

优化一 避免程序中出现两层循环的情况 ​

优化二 屏幕外节点边不去绘制 ​

优化三 屏幕外连线不去绘制 ​

优化四 对Zoom进行优化 ​

优化五 对展现形态进行优化 ​

优化六 数据分层 ​

优化七 分时 ​

优化八 节点拖拽 ​

优化九 创建文档碎片 createDocumentFragment() ​

优化十 保存视图优化 ​

优化十一 WebWorker ​

优化十一 WASM (WebAssembly) ​

优化十二 样式 ​

优化十三 本地缓存 indexDB ​