本文使用「署名 4.0 国际 (CC BY 4.0)」 许可协议，欢迎转载、或重新修改使用，但需要注明来源。

前文回顾：图形编辑器基础模块以及常见图形算法图形编辑器

一、拓扑图核心元素

二、Topology 架构设计

先简单了解下 byai/topology 是如何使用的。

import { Topology } from '@byai/topology';
const data = {
    lines: [
        {
            start: '1585466878859-0',
            end: '1585466718867',
            color: '#b71522',
        },
    ],
    nodes: [
        {
            id: '1585466878859',
            name: '窄节点',
            content: '这是一个窄节点',
            branches: ['锚点1'],
            position: {
                x: 19726.906692504883,
                y: 19512.21832561493,
            },
        },
        {
            id: '1585466718867',
            name: '宽节点',
            content: '这是一个宽节点',
            branches: ['锚点1', '锚点2', '锚点3'],
            position: {
                x: 19629.79557800293,
                y: 20050.197512626648,
            },
        },
    ],
}
// anchorDecorator: (options: { anchorId?: string }) => (item: ReactNode) => ReactNode;
renderTreeNode = (data: ITopologyNode, { anchorDecorator }: IWrapperOptions) => {
    const {
        name = '',
        content = '',
        branches = [],
    } = data;
    return (
        <div className="topology-node">
            <div className="node-header">{name}div>
            <p className="node-content">{content}p>
            {branches.length > 0 && (
                <div className="flow-node-branches-wrapper">
                    {branches.map(
                        (item: string, index: number) => anchorDecorator({
                            anchorId: `${index}`,
                        })(<div className="flow-node-branch">{item}div>),
                    )}
                div>
            )}
        div>
    );
};
<Topology
    data={data}
    autoLayout
    onChange={this.onChange}
    onSelect={this.handleSelect}
    renderTreeNode={this.renderTreeNode}
    readOnly={readonly}
    getInstance={(ins: any) => { this.topology = ins; }}
/>

MVC、 MVP 、MVVM 架构设计

…

现有设计：

Byai/Topology 是基于 React 框架实现的图编辑引擎，架构设计上没有完全遵循 MVVM 设计，更多的是 Functional Component Design（功能组件设计），通过组件化思想，将功能拆分成独立组件，利用 React 生命周期做视图更新。 这种设计方式可能较为简单和直观，但同时也存在一些不足之处，随着功能越来越复杂，会对代码可维护性和扩展性有一定挑战。

MVVM 架构：

各个模块之间通过事件解耦。Graph 提供对外 API 能力，API 调用或者 UI 交互都会体现在 Model 层数据的修改，Model 层数据修改后通知 View 层进行视图更新。提供 Registry 能力，将所有可扩展内容注册到注册中心，这些内容可插拔、可自定义，自由极高，可扩展性强。

参考：/antvis/X6/t…

三、功能以及代码分析定位中心

Viewport

在图形学里面，视口代表了一个可看见的多边形区域（通常来说是矩形）。在浏览器范畴里，它代表的是浏览器中网站可见内容的部分。视口外的内容在被滚动进来前都是不可见的。

视口当前可见的部分叫做可视视口（visual viewport）。可视视口可能会比布局视口（layout viewport）更小，因为当用户缩小浏览器缩放比例时，布局视口不变，而可视视口变小了。

getBoundingClientRect

返回一个 DOMRect 对象，其提供了元素的大小及其相对于视口的位置。

x， y：表示元素左上角距离视窗的坐标

width， height：表示元素的宽和高

top：元素上边框距离视窗顶部的的距离

bottom：元素下边框距离视窗顶部的的距离

left：元素左边框距离视窗左边的的距离

right：元素右边框距离视窗左部的的距离

scrollTop、scrollLeft

scrollTop：获取或设置元素滚动条到元素顶部的距离。

scrollLeft：获取或设置元素滚动条到元素左边的距离。

实现代码

const getNodeSize = (dom: string | HTMLElement) => {
    if (['string', 'number'].indexOf(typeof dom) > -1) {
        dom = document.getElementById(`dom-map-${dom}`) as HTMLElement;
    }
    if (!dom) {
        return {
            width: 0,
            height: 0,
            left: 0,
            top: 0,
        } as ClientRect;
    }
    return (dom as HTMLElement).getBoundingClientRect();
};
const computeMaxAndMin = (nodes: ITopologyNode[]) => {
    if (!nodes.length || nodes.find(item => !item.position || [item.position.x, item.position.y].includes(undefined))) {
        return null;
    }
    let minX = Infinity;
    let maxX = -Infinity;
    let minY = Infinity;
    let maxY = -Infinity;
    nodes.forEach(({ position, id }) => {
        const nodeSize = getNodeSize(id);
        const { x, y } = position;
        minX = Math.min(minX, x);
        maxX = Math.max(maxX, x + nodeSize.width);
        minY = Math.min(minY, y);
        maxY = Math.max(maxY, y + nodeSize.height);
    });
    return {
        minX,
        maxX,
        minY,
        maxY
    };
};
const computeContentCenter = (nodes: ITopologyNode[]) => {
    if (!computeMaxAndMin(nodes)) return null;
    const {
        minX, maxX, minY, maxY
    } = computeMaxAndMin(nodes);
    return {
        x: (minX + maxX) / 2,
        y: (minY + maxY) / 2,
    };
};
const scrollCanvasToCenter = () => {
    if (!this.$wrapper || !this.$canvas) {
        return;
    }
    const canvasSize = getNodeSize(this.$canvas);
    const wrapperSize = getNodeSize(this.$wrapper);
    const contentCenter = computeContentCenter(this.props.data.nodes);
    const canvasCenter = {
        x: canvasSize.width / 2,
        y: canvasSize.height / 2
    };
    const defaultScrollTop = (canvasSize.height - wrapperSize.height) / 2;
    const defaultScrollLeft = (canvasSize.width - wrapperSize.width) / 2;
    if (!contentCenter) {
        this.$wrapper.scrollTop = defaultScrollTop;
        this.$wrapper.scrollLeft = defaultScrollLeft;
    } else {
        this.$wrapper.scrollTop = defaultScrollTop + (contentCenter.y - canvasCenter.y);
        this.$wrapper.scrollLeft = defaultScrollLeft + (contentCenter.x - canvasCenter.x);
    }
};

进阶：画布缩放之后如何计算呢？

核心：计算缩放之后节点中心坐标（运用缩放、平移矩阵），改写 computeMaxAndMin 方法

const computeCanvasPoHelper = ( $wrapper: HTMLDivElement) => {
    // 缩放的容器
    const canvas = document.querySelector('.topology-canvas');
    const { width, height } = canvas.getBoundingClientRect();
    const zoom = parseInt(document.querySelector('.topology-tools-percent').innerHTML) / 100;
    // 缩放后画布的中心点,还是需要用缩放前的比例计算中心点
    const centerX = width / zoom / 2;
    const centerY = height / zoom / 2;
    return {
        centerX,
        centerY,
        zoom,
    };
};
export const computeMaxAndMin = (nodes: ITopologyNode[], $wrapper) => {
    if (!nodes.length || nodes.find(item => !item.position || [item.position.x, item.position.y].includes(undefined))) {
        return null;
    }
    let minX = Infinity;
    let maxX = -Infinity;
    let minY = Infinity;
    let maxY = -Infinity;
    const {
        centerX, centerY, zoom
    } = computeCanvasPoHelper( $wrapper);
    nodes.forEach(({ position, id }) => {
        const nodeSize = getNodeSize(id);
        const { x, y } = position;
        minX = Math.min(minX, (x - centerX) * zoom + centerX);
        maxX = Math.max(maxX, (x - centerX) * zoom + centerX + nodeSize.width * zoom);
        minY = Math.min(minY, (y - centerY) * zoom + centerY);
        maxY = Math.max(maxY, (y - centerY) * zoom + centerY + nodeSize.height * zoom);
    });
    return {
        minX,
        maxX,
        minY,
        maxY
    };
};

框选

包围体

在计算机图形学与计算几何领域，一组物体的包围体就是将物体组合完全包容起来的一个封闭空间。将复杂物体封装在简单的包围体中，就可以提高几何运算的效率。通常简单的物体比较容易检查相互之间的重叠。一组物体的包围体也是包含一个物体及周围相关环境的封闭空间，因此可以用它来表示一个非空、有限的单一物体。

应用场景

在光线跟踪中，包围体用于光线相交检验，在许多渲染算法中，它又用于视体的检验。如果光线或者视体与包围体没有交叉，那么就不会与包围体内的物体相交。通过这样的相交检验，就可以生成需要显示的物体列表。在碰撞检测中，如果两个包围体没有相交，那么所包含的物体也就不会碰撞。

常见类型

R 树（R-tree）

假设有一张地图，上面有几百万个节点，要快速找某个位置半径 2 公里的所有学校的信息。

低效的做法是遍历这几百万的节点的位置，判断距离是否小于 2 公里。

但如果用上索引技术，比如 R 树，我们就能利用索引去空间换时间，快速拿到特定范围的节点超集，比如几千个。

接着只需要遍历这几千个节点去判断符合条件的节点就可以了，而不需要完完整整遍历所有的节点。

一种空间索引技术，能够是从大量的节点中，快速找到特定范围的元素集合，而不用一个不落地遍历所有节点。

R 树的叶子节点是数据节点，保存有图形信息和它的最小包围矩形（MBR）。

R 树会将距离相近的数据节点收集起来，并放到同一个父节点下。这个父节点是索引节点，不会保存图形信息，但会记录子节点的合并的包围盒数据，父节点如果多了，也会把它们收集起来，放到一个新的父节点下。

{
  minX: 20,
  minY: 40,
  maxX: 30,
  maxY: 50,
  // 保存图形数据，比如图形对象 id，或图形对象本身
  data: {}
};

/mourner/rbu…

R 数检索的过程如下：

提供一个选区矩形，从根节点开始，往下递归查找判断选取矩形是否和当前节点矩形相交。

若不相交，其下的节点也不会相交，该节点对应的子树就不需要继续递归了；若相交且为数据节点（叶子节点），将其放到 result 数组；若是包含关系，其下的所有数据节点放到 result 数组；若相交但并不包含，则遍历其下的子节点，重复前面的操作。

直到可能相交的节点遍历完结束，然后返回 result 数组。

矩形包含检测

interface Bbox {
  minX: number;
  minY: number;
  maxX: number;
  maxY: number;
}
var rect1 = {x: 5, y: 5, width: 50, height: 50}
var rect2 = {x: 20, y: 10, width: 10, height: 10}
maxX = x + width;
maxY = y + height;
function isRectContain2(rect1: IBox2, rect2: IBox2) {
  return (
    rect1.minX <= rect2.minX &&
    rect1.minY <= rect2.minY &&
    rect1.maxX >= rect2.maxX &&
    rect1.maxY >= rect2.maxY
  );
}

计算最小外接矩形

function getRectsBBox(...rects: IRect[]): IBox {
  const minX = Math.min(...rects.map((rect) => rect.x));
  const minY = Math.min(...rects.map((rect) => rect.y));
  const maxX = Math.max(...rects.map((rect) => rect.x + rect.width));
  const maxY = Math.max(...rects.map((rect) => rect.y + rect.height));
  return {
    x: minX,
    y: minY,
    width: maxX - minX,
    height: maxY - minY,
  };
}

树形布局和 Dagre 布局（可先初步阅读，待补充）

/phenomLi/Bl…

/p/346059370

/post/710148…

四、未来方向节点转换节点编组标尺性能优化MVVM 架构dnd 升级