G6 Minimap 原理解析 - 《图可视化知多少》

前言
Minimap 目的
概念解释
问题
方案
- 逻辑方面
- 性能优化
结语

前言

本文将详细介绍 G6 中 Minimap 的设计、计算、优化原理。将会涉及到大量计算逻辑，看到数学就脑壳疼的小伙伴们可以选择性省略🌝。

Minimap 目的

主要用于大规模图的导航，大部分情况下不需要 Minimap 展示和原图一样详细的信息。

概念解释

主图与 Minimap

主画布 Main Canvas 大小为实例化图时设置的 width 与 height；
主图包围盒 Main Graph BBox 是当前主图最小的包围盒，它可能与 Main Canvas 长宽比不同，也可能会超出 Main Canvas；
Minimap Canvas 大小为实例化 Minimap 插件时指定的 size，可能与 Main Cavans 长宽比不同；
Minimap Graph BBox 是 Main Graph BBox 等比缩放。

图形与图形分组

图形的类型有 circle、text、rect、path……[详见 G6 各图形属性]，而图形分组是用于管理和组合这些图形的容器。类似 SVG 中 g 与其他图形标签的关系。
在 G6 中，图上的图形和图形分组的关系如下图：

上图中，相邻层方块代表直接包含关系；
主图画布有一个根图形分组 Root Group，它包含了 Nodes Group、Edges Group Combos Group、Delegates Group ，分别包含了节点、边、combos、delegates；
Delegates Group 中主要存放图上的临时图形，例如拖动节点/分组时的虚拟代表框：

Nodes Group 中的 Node Group 包含了一个节点中的所有图形，可能有 circle、text、rect 等。Edges Group、Combos Group 也是类似的。

矩阵

每个图形、图形分组都有自己的变换矩阵，用于控制自身的平移、缩放、旋转（旋转在 G6 中较少见）。可以通过 element.getMatrix() 获得自身的矩阵。在没有任何平移、缩放、旋转时，该矩阵的初始值为 null ，也可以使用一个单位矩阵表示没有任何矩阵操作。
在 G6 中，Nodes Group 中的每一个 Node Group 都有一个矩阵控制该节点在画布上的具体位置，而一个节点中的具体图形（circle、text 等）的 x 与 y 均以其 Node Group 为参考建立子坐标系，与整个节点的坐标不直接相关。Combos Group 与 Nodes Group 原理相同。
与节点不同的是， Edges Group 中的每一个 Edge Group 则没有使用矩阵来控制边的位置，边的起始、结束位置均由 Edge Group 中的 path 图形自己定义。

包围盒 Bounding Box（BBox）

包围盒是指包围一个图形或一组图形的一个最小矩形，使用下面对象描述：

{
  minX: number,
  minY: number,
  maxX: number,
  maxY: number,
  centerX: number,
  centerY: number,
  width: number,
  height: number
}

若要使用好 bbox，我们需要区分 getBBox 与 getCanvasBBox ：

element.getBBox()：获取 element 的包围盒，该包围盒与该元素及其子元素的矩阵均无关；
element.getCanvasBBox()：获取 element 考虑自身矩阵以及子元素矩阵变换后的包围盒，即当前图形相对于画布的包围盒。

如下一个 circle 图形从 a 的形态通过矩阵平移、放大为 A 形态。由于 a 没有经过矩阵变化，其矩阵为 null，a.getCanvasBBox() 与 a.getBBox() 返回值相等。A.getCanvasBBox() 返回经过了矩阵操作后的包围盒，A.getBBox() 忽略矩阵，即与 a.getBBox() 相等。

下图展示了一个图形分组的情况。

在形态 g 中：a 图形未经任何矩阵变换；而这里的 b 图形的 x 与 y 均为零，即其本身位置是 (0, 0)，通过矩阵平移到了 (35, 15)；g 本身没有任何矩阵变换。getBBox 是得到的是不受任何矩阵影响的包围盒。而 getCanvasBBox 则是考虑了 b 的矩阵的影响；
变换到 G 形态：a 图形通过矩阵放大得到 A，b -> B 矩阵不变，g 通过施加在该分组上的矩阵进行平移得到新的位置。同样，getBBox 得到的是不受任何矩阵影响的包围盒，因此与 g.getBBox() 相等。而 g.getCanvasBBox 则是考虑了 A、B、G 上的矩阵的影响。

问题

两个画布将会导致渲染消耗倍增；
从主画布复制图形到 minimap 上需要注意缩放比例；
使用 View Port 定位当前主图显示部分逻辑稍复杂。

方案

逻辑方面

Minimap 有三种类型：

default：与主图所有图形保持一致，即绘制主图上所有的图形，包括复杂节点/边中的所有图形；
keyShape：仅绘制主图上节点/边的 keyShape；
delegate：使用一个正方形代替一个主图节点，边仅绘制 keyShape。

这三种类型的 Minimap 在复制主图图形时逻辑各异，而后两者的性能将会更好。要了解复制逻辑，首先我们需要知道

1. 复制逻辑

defualt：直接将主图的 Root Group 清除矩阵（可能有平移、缩放）后复制到 Minimap Canvas 上。
keyShape：该模式下，Minimap Canvas 上只有一个图形分组 Root Group，所有节点/边的 keyShape 直接添加到 Root Group 中。

首先复制边的 keyShape 到 Minimap Canvas 中：

// 遍历 Edges Group 中的元素
EdgesGroup.children.forEach(nodeGroup => {
  // 在该边的组中，拿到这个边的 keyShape
  const keyShape = nodeGroup.findKeyShape(); 
  // 复制到一个新的对象中
  const cKeyShape = clone(keyShape);
     // 将 cKeyShape 增加到 minimap 的 Root Group 中
  minimap.rootGroup.children.push(cKeyShape);
});

然后复制节点的 keyShape 到 Minimap Canvas 中：由于在主图中，节点的位置是由其父分组的矩阵控制的，而 keyShape 中的节点没有独立的父分组。因此我们需要把主图的节点位置写入 minimap 中对应的 keyShape 上。伪代码如下：

// 遍历 Nodes Group 中的元素
NodesGroup.children.forEach(nodeGroup => {
  // 在该节点的组中，拿到这个节点的 keyShape
  const keyShape = nodeGroup.findKeyShape(); 
  // 复制到一个新的对象中
  const cKeyShape = clone(keyShape);
  // 获取 nodeGroup 的 canvasBBox，考虑矩阵影响，才能得到正确的节点位置
  const canvasBBox = nodeGroup.getCanvasBBox();
  // 为 cKeyShape 指定位置
  cKeyShape.attr({
    x: canvasBBox.centerX,
    y: canvasBBox.centerY
  });
     // 将 cKeyShape 增加到 minimap 的 Root Group 中
  minimap.rootGroup.children.push(cKeyShape);
});

delegate：与 keyShape 模式相同，该模式下，Minimap Canvas 上只有一个图形分组 Root Group，所有节点/边的 keyShape 直接添加到 Root Group 中。

复制边的逻辑与 keyShape 的模式相同。
目前，delegate 使用代表每个节点长、宽、位置的一个矩形，伪代码如下：

// 遍历 Nodes Group 中的元素
NodesGroup.children.forEach(nodeGroup => {
  // 获取 nodeGroup 的 canvasBBox，考虑矩阵影响，才能得到正确的节点大小和位置
  const canvasBBox = nodeGroup.getCanvasBBox();
  const delegateShapeAttrs = {
    x: canvasBBox.minX,
    y: canvasBBox.minY,
    width: canvasBBox.width,
    height: canvasBBox.height
  }
     // 增加 delegate 到 minimap 的 Root Group 中
  minimap.rootGroup.addShape('rect', {
    attrs: delegateShapeAttrs
  });
});

2. Minimap Canvas 缩放平移逻辑

从复制逻辑中得到的 Minimap Root Group 长宽与 Main Graph Root Group 相同，我们需要将其进行缩放适配到 Minimap Canvas 的大小。一般来说 Minimap Canvas 比主图画布小，但有以下几个问题需要谨慎考虑：

大多数情况下，Minimap Canvas、Main Graph Root Group、Main Graph Canvas 三者的长宽比不同；
Main Graph Root Group 可能超出 Main Graph Canvas 范围。

通过上面复制逻辑的操作后，我们得到的 Minimap 内容是这样的：

需要通过操作 Minimap Root Group 的矩阵 mMatrix 将其进行缩放和平移。

Step 1: 将 Minimap Graph Group 根据其 canvasBBox 平移到 Minimap Canvas 左上角: ```javascript const canvasBBox = MinimapGraphGroup.getCanvasBBox(); // 获得 Minimap Graph Group 的 CanvasBBox let mMatrix = [ 1, 0, 0, 0, 1, 0, 0, 0, 1 ]; // 初始化矩阵为单位矩阵

// 平移到左上角 transform(mMatrix, [ [‘t’, canvasBBox.minX, canvasBBox.minY], ]);

此时，我们得到如下结果：<br />![image.png](https://cdn.nlark.com/yuque/0/2020/png/156681/1587726050940-c4e9bd49-2051-4697-9799-c7e13a57ed6e.png#align=left&display=inline&height=248&margin=%5Bobject%20Object%5D&name=image.png&originHeight=459&originWidth=506&size=79961&status=done&style=none&width=273)
- **Step 2**: 将 Minimap Graph Group 缩放到合适到大小以适配 Minimap Canvas，缩放因子 ratio 为：
```javascript
const ratio = Math.min(width(Minimap Canvas) / canvasBBox.width,
                      height(Minimap Canvas) / canvasBBox.height);

使用 ratio 进行缩放：

transform(mMatrix, [
  ['s', ratio, ratio], 
]);

此时，我们得到如下结果：

Step 3: 将 Minimap Graph Group 平移到 Minimap Canvas 的中心
```
const dx = (width(Minimap Canvas) - CanvasBBox.width * ratio) / 2;
const dy = (height(Minimap Canvas) - CanvasBBox.height * ratio) / 2;
transform(mMatrix, [
['t', dx, dy], 
]);
```
最后，得到如下结果：

至此，Minimap Canvas 绘制完成，主画布的平移、缩放都不影响 Minimap Canvas。但局部节点/边样式、位置的改变需要 Minimap Canvas 随之更新。

3. 主图联动 View Port 逻辑

View Port 用于定位 Minimap Canvas 中显示在主图中对应的部分。需要注意以下问题：

View Port 的长宽比始终与主图画布 Main Canvas 长宽比一致；
用户在主图上缩放、拖拽画布会影响 View Port 的位置和大小；
用户也可以通过拖拽 View Port 来导航主图。

在主图缩放、拖拽画布时更新 View Port 的位置和大小主要分为以下几步：

Step 1: 计算 View Port 宽高 viewPort.width, viewPort.height，首先我们需要得到主图画布坐标的相对宽高。下图展示了什么是相对宽高，当主图被平移放缩时，图坐标系也将会跟着平移缩放：

因此，我们使用主图的视口左上角坐标 (0, 0) 和右下角坐标 (mainCanvas.width, mainCanvas.height) （mainCanvas.width 和 mainCanvas.height 是实例化图时指定的 Main Canvas 大小），可以计算出画布的相对坐标 topLeft 和 bottomRight，从而计算出相对宽高：

// 根据主图画布视口的左上角位置和右下角位置获得对应的画布坐标 topLeft 和 bottomRight
const topLeft = graph.getPointByCanvas(0, 0);
const bottomRight = graph.getPointByCanvas(mainCanvas.width, mainCanvas.height)
// 相对宽高
const width = bottomRight.x - topLeft.x;
const height = bottomRight.y - topLeft.y;

Step 2: 计算 View Port 相对于 Minimap DOM 容器的位置 (left, top)。

首先我们考虑未缩放，仅平移。这里需要分为四种情况讨论：
第一，主图 canvasBBox 左侧超过主画布左侧：

则 View Port 的 left 值为 dx - mainGraphRootGroup.getCanvasBBox().minX * ratio 。

第二，主图 canvasBBox 右侧超过主画布右侧：

则 View Port 的 left 值为:

const mainGraphBBox = mainGraphRootGroup.getCanvasBBox();
const a = (mainGraphBBox.width - mainGraphBBox.maxX + mainCanvas.width) * ratio;
const left = -(width - a - dx);

第三，主图 canvasBBox 上侧超过主画布上侧。与第一种情况类似，只是更换成 y 轴上的对比；
第四，主图 canvasBBox 下侧超过主画布下侧。与第二种情况类似，只是更换成 y 轴上的对比。

而下面几种情况只需要将上面四种情况的 x 轴与 y 轴互相组合合即可，x 与 y 轴不相互影响：

最后，当主图被缩放后，将会影响 Main Graph Root Group 的大小。因此若图有缩放，还需要将 ratio /= zoom 。

4. View Port 联动主图逻辑

目前仅提供了 View Port 的拖拽，从而联动平移主图功能。拖拽 View Port 的移动范围有限制，不能将其拖出 Minimap Canvas 上下左右边界。
View Port 的监听放在了该 DOM 上，在拖动过程中，通过下面代码控制主图的平移：

// previousX previousY 为拖拽过程中的上一次鼠标位置
const dx = previousX - e.clientX;
const dy = previousY - e.clientY;
const zoom = graph.getZoom(); 主图当前的缩放因子
// ratio 为上文中将主图缩放到 Minimap Canvas 的缩放系数
graph.translate((dx * zoom) / ratio, (dy * zoom) / ratio);
previousX = e.clientX;
previousY = e.clientY;

5. 边界情况处理

为了防止用户暴力无限拖拽画布，在内置交互 drag-canvas 中做了限制，最多只能拖拽到 Main Graph Root Group 上下左右多一屏。这并不会影响用户的使用，若用户希望新增节点或拖拽节点到距离当前 Main Graph Root Group 很远的地方也不影响，因为增加了节点之后 Main Graph Root Group 的范围也随之更新，画布可拖拽的范围也会更大。
因此，在画布拖拽到极限位置的时候，ViewPort 也不会完全超出 Minimap Canvas，多少会剩余一部分在 Minmap Canvas 上。Minimap Canvas 容器被设置了 overflow: hide ，所以 View Port 超出 Minimap Canvas 的部分会被隐藏。
当用户通过拖拽主图画布使得 View Port 有部分超出 Minimap Canvas 时，再点击 View Port，将会跳回到 View Port 完全在 Minimap Canvas 内部，原本超出的边缘顶到 Minimap Canvas 边缘的情况。帮助用户快速定位回主图内容上。

性能优化

1. 提供 delegate 或 keyShape 模式

默认的 default 模式将主图所有图形复制到 Minimap 中将会造成绘制和更新的压力。因此在 Minimap 最早的版本中就提供了 delegate 和 keyShape 模式。其中，delegate 是性能最好的模式。

2. 减少 Minimap Canvas 重绘

上文提到，主图在缩放和平移时，Minimap Canvas 是不需要重绘的。

在旧版 Minimap 中，监听了主图的 beforepaint，即主图每次重绘更新都会触发 Minimap Canvas 的重绘。并且原来的实现方式是在重绘时完全清空 Minimap 上的元素，重新创建和添加一遍，这是非常消耗性能的。

3.4.5 版本中 Minimap 监听 afterrender，afterlayout，afteradditem，afterupdateitem，afterremoveitem 这五个时机，触发 Minimap Canvas 的画布重新绘制，并且是差量地修改，代替原来的清空后重新添加。也就是说，只有主图上元素有增删、位置改变、重新布局时才会更新 Minimap Canvas。而 beforepaint 只会触发 View Port 大小和位置的更新。

3. debounce

上面提到的 Minimap Canvas 重绘机制仍然无法避免有些情况下的频繁刷新，例如：

在主图初次渲染时，会逐个 additem，此时 afteradditem 将会频繁被触发；
force layout 中，每次迭代都会触发主图的重新渲染，从而频繁触发 Minimap 重绘，然而 Minimap 在主图未稳定时不断更新是没有意义的。

因此，在 3.4.5 版本中，使用了 debounce 来将短时间内频繁触发重绘 Minimap Canvas 合并成一次执行。大大减少了重绘造成的性能消耗。

结语

Minimap 在 G6 1.x 时期便已经存在，其性能与准确性一直被用户吐槽。经过此次翻新改造，相信 Minimap 可以为用户高效准确地提供导航功能。也许它还有更多的性能、功能优化空间，欢迎社区的小伙伴一起讨论和共建。