实现带动画切换效果的树形图（组织架构图），附性能分析

Apr 19, 2023 · Yin灏

想直接看源码或者上手体验一下效果的可以在codesandbox中进行操作

背景

公司内部需要开发一个目标制定-分配-执行的项目（OKR），其中有一个需求是需要以卡片树的形式展示任务的分配和执行情况，并能进行一些交互（收藏任务、@相关人员、展开子任务等）操作。

树形图（常用于组织架构图、因果关系图、思维导图），虽然 Echarts 已经有实现Examples - Apache ECharts，但是其布局实现和交互能力并不能很好的满足现有需求，故现在考虑自行实现布局算法和页面绘制。

注：本文中的实例代码仅仅作为参考查看，不能直接运行（缺少属性和方法），具体的代码和效果可以在codesandbox中进行查看

布局算法

第一次绘制

首先需要明确的是：

坐标计算顺序如图所示
我们需要简化坐标关系，每一个节点占据的位置固定为 1（如：A 初始坐标– [0, 0]，则对应的子节点 AA 初始坐标 –[1, 0]）
每一个子节点的初始位置由父节点控制，没有父节点，则位置初始化为[0，0]
每一个节点有可能初始位置会被占据（如 AB 和 ABA 节点，初始应该是紧贴 AA 往下一格，但是被 AAB 挤下来了一些）
当一个节点的子节点全部被绘制完成后，这个节点的最终位置可能需要更新（如 AC 节点初始应该紧贴 AB 节点，但是由于其子节点 ACA 和 ACB 的缘故，AC 的位置需要往下移动一些距离）

那么算法就很简单了，我们使用回溯算法，先深度优先到底节点，处理好初始坐标。然后回溯到上层节点，并更新上层节点的最终位置

以下是简要的代码

注：x 和 y 坐标使用 mainAxis 和 subAxis 进行标识，方便进行[从上到下]和[从左到右]两种布局方式

class TreeGraph {
  /**
   * 逐层回溯，计算每个节点的坐标
   *
   * @private
   * @param node - 当前节点
   * @param level - 当前层级
   * @returns {number | void} 返回上层新的 y 坐标
   */
  traverse(node: Node, level = 0) {
    const { levelStartNode, mainAxis, subAxis } = this;
    if (!levelStartNode[level]) {
      levelStartNode[level] = 0;
    }
    // 动画部分 [后面会涉及]
    node.oldPosition = node.oldPosition || node.position;

    // 当前节点位置已经被占据了，需要更新
    if (levelStartNode[level] > node.position[subAxis]) {
      node.position[subAxis] = levelStartNode[level];
    }
    if (node.children && node.children.length > 0) {
      if (!node.childrenHide) {
        const l = node.children.length;
        for (let i = 0; i < l; i++) {
          const child = node.children[i];
          child.position = {
            [mainAxis]: level + 1,
            // 初始值，如果是第一个子节点，需要根据父节点的位置计算，否则，直接使用上一个子节点的位置 + 1
            [subAxis]:
              i === 0
                ? this.getInitialFirstChildSubAxis(node)
                : node.children[i - 1].position[subAxis] + 1,
          };
          // 父子关联，方便后续使用
          child.parent = node;
          this.traverse(child, level + 1);
        }
        node.position[subAxis] = this.getUpdatedParentSubAxis(node);
      } else {
        // 隐藏的节点，需要重置子节点位置，以便下次展开时，能够正确计算动画 [下面会涉及]
        this.resetHideChildrenPosition(node);
      }
    }

    // 更新当前层级的最大值
    levelStartNode[level] = node.position[subAxis] + 1;

    // 动画部分 [后面会涉及]
    this.handleAnimation(node);

    // 记录最大的宽度和高度
    this.size.width = Math.max(this.size.width, node.position.x + 1);
    this.size.height = Math.max(this.size.height, node.position.y + 1);
  }
}

后续绘制，动画处理

当有一个节点进行隐藏时，由于绘制算法的第 5 条，其父节点会受到影响。又由于第 3 条，父节点变化又会导致所有子节点受到影响。所以我们选择从顶部重新再次计算所有坐标的位置。

注意看node.oldPosition = node.oldPosition || node.position;这行代码，我们在遍历计算坐标时，已经同时保存了这个节点的新旧坐标，即: oldPosition 和 position。所以我们只需要使用缓动工具处理两次的值即可，此处我使用的是 GSAP 这个库。

简要代码

class TreeGraph {
  /**
   * 正常来说 GSAP 动画应该在绘制层(DrawGraph)实现，但是我想将子节点切换动画和TreeGraph这个类关联上，所以在这儿实现的
   * 可以自行调整
   */
  handleAnimation(node: Node) {
    const oldPosition = node.oldPosition;
    // 终止之前的动画
    node.animation && node.animation.kill();
    node.animation = null;
    if (
      oldPosition &&
      (oldPosition.x !== node.position.x || oldPosition.y !== node.position.y)
    ) {
      node.animation = gsap.to(node.oldPosition, {
        ...node.position,
        duration: 0.2,
        onUpdate: () => {
          // 更新节点位置的回调，由绘制层实现
          node.animation?.onUpdate(node.oldPosition);
        },
      });
    }
  }
}

卡片绘制

第一次绘制

先使用上面的方法把坐标计算完成后，绘制类中遍历所有节点坐标，依次绘制出图形即可。

我这里使用的 Konva 进行绘制的，也可以使用 ZRender，fabric 等库进行实现。

简要代码

class DrawGraph {
  draw() {
    // 计算树形结构的坐标
    this.treeGraph.computeTreeDataCoordinates();
    // 设置舞台大小
    this.setStageSize();
    this.traverse(this.treeGraph.data);
    return this;
  }

  /**
   * 遍历树形结构，绘制节点
   *
   * @private
   * @param node
   */
  traverse(node: Node) {
    const { layer, lineLayer, options } = this;
    const { distance, padding, createCard, events } = options;
    // 由于坐标的是单位1，所以需要乘上间距
    const { x: dx, y: dy } = distance;
    const { oldPosition, children, parent } = node;
    // konva节点绘制
    const card = createCard(node, {
      x: oldPosition.x * dx + padding.left,
      y: oldPosition.y * dy + padding.top,
      childrenCloseable: node.children && node.children.length > 0,
      dir: options.dir,
    });
    const group = card.konvaNode;
    // 绑定事件，切换子节点的显示状态，触发动画
    card.on("click:toggle", () => {
      node.childrenHide = !node.childrenHide;
      this.animate();
    });

    // 其他事件
    if (events) {
      Object.keys(events).forEach((eventName) => {
        card.on(eventName, () => {
          events[eventName](node);
        });
      });
    }

    node.konvaNode = group;

    // 绘制连接线
    if (parent) {
      const points = this.getLinePoints(parent.konvaNode, node.konvaNode);
      const line = new Konva.Line({
        points: points,
        stroke: colors.gray[200],
        strokeWidth: 1,
      });
      lineLayer.add(line);
      node.line = line;
    }

    layer.add(group);
    children && children.forEach(this.traverse.bind(this));
  }
}

后续绘制，动画处理

同样的，我们再次计算出隐藏节点后的坐标信息，但是遍历后，我们不进行绘制，而是更新节点的显示和隐藏状态和根据animation返回的缓动节点位置来设置节点的位置信息。

当节点更新后，其对应的连接线也需要更新，除了顶层和底层节点，均有两类连接线需要更新

与父节点的连接线 - 1 条
与子节点的连接线 - 可能多条

需要注意的是，由于深度优先的递归，我们更新父节点连线(1 类)的时候，这条线可能已经被父节点作为子节点更新过了(2 类)。

所以我们这儿使用了一个 Set: updatedLines来避免重复更新。

注：更新线条时，节点的位置信息还没有绘制完成，此时通过 konva 获取的坐标信息不准确，所以我这里使用了 setTimeout 来在下一个 tick 中再绘制线条

class DrawGraph {
  animate() {
    // 再次计算树形结构的坐标
    this.treeGraph.computeTreeDataCoordinates();
    // 设置舞台大小
    this.setStageSize();
    const { treeGraph, options } = this;
    const { distance, padding } = options;
    // 由于坐标的是单位1，所以需要乘上间距
    const { x: dx, y: dy } = distance;
    // 避免重复绘制
    const updatedLines = new Set();
    const dfs = (node: Node, hide: boolean) => {
      const { children, parent, animation } = node;
      const group = node.konvaNode;
      const line = node.line;
      if (hide) {
        group.hide();
        line && line.hide();
      } else {
        group.show();
        line && line.show();
      }
      children &&
        children.forEach((child) => dfs(child, hide || node.childrenHide));
      if (animation) {
        animation.onUpdate = (e: { x: number; y: number }) => {
          group.setPosition({
            x: e.x * dx + padding.left,
            y: e.y * dy + padding.top,
          });

          // 在下一个tick绘制线条，避免线条绘制不齐
          setTimeout(() => {
            // 父线条
            if (line && !updatedLines.has(line)) {
              const points = this.getLinePoints(
                parent.konvaNode,
                node.konvaNode
              );
              line.points(points);
            }
            // 子线条
            if (children) {
              children.forEach((child) => {
                const childLine = child.line;
                if (childLine) {
                  const points = this.getLinePoints(
                    node.konvaNode,
                    child.konvaNode
                  );
                  childLine.points(points);
                  updatedLines.add(childLine);
                }
              });
            }
          }, 0);
        };
      }
    };
    dfs(treeGraph.data, false);
  }
}