关联线探究，如何连接流程图的两个节点 |
您所在的位置：网站首页 › js两点之间画线 › 关联线探究，如何连接流程图的两个节点 |
关联线探究，如何连接流程图的两个节点
|
如果你用过流程图绘制工具，那么可能会好奇节点之间的连接线是如何计算出来的：
不要走开，跟随本文一起来探究一下吧。 最终效果预览：https://wanglin2.github.io/AssociationLineDemo/ 基本结构先使用Vue3搭建一下页面的基本结构，为了简化canvas操作，我们使用konvajs库来绘制图形。 页面模板部分，提供一个容器即可： js部分，主要是使用konvajs来创建两个可拖拽的矩形元素及一个连接线元素，当然目前连接线并没有顶点数据： import { onMounted, ref } from "vue"; import Konva from "konva"; const container = ref(null); // 创建两个矩形、一个折线元素 let layer, rect1, rect2, line; // 矩形移动事件 const onDragMove = () => { // 获取矩形实时位置 console.log(rect1.x(), rect1.y(), rect2.x(), rect2.y()); }; // 初始化图形 const init = () => { const { width, height } = container.value.getBoundingClientRect(); // 创建舞台 let stage = new Konva.Stage({ container: container.value, width, height, }); // 创建图层 layer = new Konva.Layer(); // 创建两个矩形 rect1 = new Konva.Rect({ x: 400, y: 200, width: 100, height: 100, fill: "#fbfbfb", stroke: "black", strokeWidth: 4, draggable: true,// 图形允许拖拽 }); rect2 = new Konva.Rect({ x: 800, y: 600, width: 100, height: 100, fill: "#fbfbfb", stroke: "black", strokeWidth: 4, draggable: true, }); // 监听进行拖拽事件 rect1.on("dragmove", onDragMove); rect2.on("dragmove", onDragMove); // 矩形添加到图层 layer.add(rect1); layer.add(rect2); // 创建折线元素 line = new Konva.Line({ points: [],// 当前它的顶点数据是空的，所以你还看不见这个元素 stroke: "green", strokeWidth: 2, lineJoin: "round", }); // 折线添加到图层 layer.add(line); // 图层添加到舞台 stage.add(layer); // 绘制 layer.draw(); }; onMounted(() => { init(); });效果如下：
接下来我们只要在图形拖拽时实时计算出关联线的顶点然后更新到折线元素里就可以绘制出这条连接线。 计算出关联线最有可能经过的点整个画布上所有的点其实都是可能经过的点，但是我们的连接线是【横平竖直】的，且要尽可能是最短路线，所以考虑所有的点没有必要，我们可以按照一定规则缩小范围，然后再从中计算出最优路线。 首先起点和终点两个点肯定是必不可少的，以下图为例，假设我们要从左上角的矩形顶部中间位置连接到右下角的矩形顶部中间位置：
接下来我们定两个原则： 1.连接线尽量不能和图形的边重叠
2.连接线尽量不能穿过元素
为什么说尽量呢，因为当两个元素距离过近或有重叠的话这些都是无法避免的。 结合上面两个原则我们可以规定元素周围一定距离内都不允许线经过（当然除了连接起终点的线段），这样就相当于给元素外面套了个矩形的包围框：
经过起终点且垂直于起终点所在边的直线与包围框的交点一定是会经过的，并且这两个点是唯一能直接和起终点相连的点，所以我们可以把这两个点当做是“起点"和"终点”，这样在计算的时候可以少计算两个点：
在矩形移动事件里进行点的计算，首先缓存一下矩形的位置和尺寸信息，然后定义起点和终点的坐标，最后定义一个数组用来存放所有可能经过的点： // 矩形移动事件 const onDragMove = () => { computedProbablyPoints(); }; // 计算所有可能经过的点 let rect1X, rect1Y, rect1W, rect1H, rect2X, rect2Y, rect2W, rect2H; let startPoint = null, endPoint = null; const computedProbablyPoints = () => { // 保存矩形的尺寸、位置信息 rect1X = rect1.x(); rect1Y = rect1.y(); rect1W = rect1.width(); rect1H = rect1.height(); rect2X = rect2.x(); rect2Y = rect2.y(); rect2W = rect2.width(); rect2H = rect2.height(); // 起终点 startPoint = [rect1X + rect1W / 2, rect1Y]; endPoint = [rect2X + rect2W / 2, rect2Y]; // 保存所有可能经过的点 let points = []; }因为起终点可以在矩形的任一方向，所以我们写个方法来获取伪起点和伪终点，并将它们添加到数组里： const computedProbablyPoints = () => { // ... // 伪起点：经过起点且垂直于起点所在边的线与包围框线的交点 let fakeStartPoint = findStartNextOrEndPrePoint(rect1, startPoint); points.push(fakeStartPoint); // 伪终点：经过终点且垂直于终点所在边的线与包围框线的交点 let fakeEndPoint = findStartNextOrEndPrePoint(rect2, endPoint); points.push(fakeEndPoint); } // 找出起点的下一个点或终点的前一个点 const MIN_DISTANCE = 30; const findStartNextOrEndPrePoint = (rect, point) => { // 起点或终点在左边 if (point[0] === rect.x()) { return [rect.x() - MIN_DISTANCE, rect.y() + rect.height() / 2]; } else if (point[1] === rect.y()) { // 起点或终点在上边 return [rect.x() + rect.width() / 2, rect.y() - MIN_DISTANCE]; } else if (point[0] === rect.x() + rect.width()) { // 起点或终点在右边 return [ rect.x() + rect.width() + MIN_DISTANCE, rect.y() + rect.height() / 2, ]; } else if (point[1] === rect.y() + rect.height()) { // 起点或终点在下边 return [ rect.x() + rect.width() / 2, rect.y() + rect.height() + MIN_DISTANCE, ]; } };伪起点和伪终点会形成一个矩形，这个矩形和起点元素包围框可以组成一个更大的矩形，这个矩形的四个角是连接线有可能经过的点：
将这几个点添加到数组里，有一个点和伪终点重复了，不过没关系，我们最后再去重即可： const computedProbablyPoints = () => { // ... // 伪起点和伪终点形成的矩形 和 起点元素包围框 组成一个大矩形 的四个顶点 points.push( ...getBoundingBox([ // 伪起点终点 fakeStartPoint, fakeEndPoint, // 起点元素包围框 [rect1X - MIN_DISTANCE, rect1Y - MIN_DISTANCE], // 左上顶点 [rect1X + rect1W + MIN_DISTANCE, rect1Y + rect1H + MIN_DISTANCE], // 右下顶点 ]) ); } // 计算出给定点可以形成的最大的矩形的四个顶点 const getBoundingBox = (points) => { let boundingBoxXList = []; let boundingBoxYList = []; points.forEach((item) => { boundingBoxXList.push(item[0]); boundingBoxYList.push(item[1]); }); let minBoundingBoxX = Math.min(...boundingBoxXList); let minBoundingBoxY = Math.min(...boundingBoxYList); let maxBoundingBoxX = Math.max(...boundingBoxXList); let maxBoundingBoxY = Math.max(...boundingBoxYList); return [ [minBoundingBoxX, minBoundingBoxY], [maxBoundingBoxX, minBoundingBoxY], [minBoundingBoxX, maxBoundingBoxY], [maxBoundingBoxX, maxBoundingBoxY], ]; };
从图上可以看出来，关联线要么从右边连过去，要么从左边连过去。 同样，伪起点和伪终点形成的矩形也会和终点元素包围框形成一个更大的矩形，这个矩形的四个顶点也是有可能会经过的，这当终点元素位于起点元素上方时会经过：
以上这些点基本能满足起终点都在元素上方的情况，但是对于下面这种起点在上面终点在左边情况就不行了：
很明显看到如果存在下面这个点就可以了：
这其实就是前面所说的经过起终点且垂直于起终点所在边的两条线的交点，求交点可以先根据两个点计算出直线方程，再联立两个方程计算交点，但是我们的线都是横平竖直的，所以没必要这么麻烦，两条线要么是平行的，要么是一条水平一条垂直，很容易罗列完所有情况： // 计算两条线段的交点 const getIntersection = (seg1, seg2) => { // 两条垂直线不会相交 if (seg1[0][0] === seg1[1][0] && seg2[0][0] === seg2[1][0]) { return null; } // 两条水平线不会相交 if (seg1[0][1] === seg1[1][1] && seg2[0][1] === seg2[1][1]) { return null; } // seg1是水平线、seg2是垂直线 if (seg1[0][1] === seg1[1][1] && seg2[0][0] === seg2[1][0]) { return [seg2[0][0], seg1[0][1]]; } // seg1是垂直线、seg2是水平线 if (seg1[0][0] === seg1[1][0] && seg2[0][1] === seg2[1][1]) { return [seg1[0][0], seg2[0][1]]; } };有了这个方法我们就可以把这个交点添加到数组里： const computedProbablyPoints = () => { // ... // 经过起点且垂直于起点所在边的线 与 经过终点且垂直于终点所在边的线 的交点 let startEndPointVerticalLineIntersection = getIntersection([startPoint, fakeStartPoint], [endPoint, fakeEndPoint]); startEndPointVerticalLineIntersection && points.push(startEndPointVerticalLineIntersection); }
到这里计算出来的点能满足大部分情况了，但是还有一种情况满足不了，当起终点相对时：
所以当前面计算的startEndPointVerticalLineIntersection点不存在的时候我们就计算经过伪起点和伪终点的一条垂直线和一条水平线的交点（黄色的两个点）：
到这里可能经过的点就找的差不多了，一共有：
接下来进行去重以及导出相关的数据： const computedProbablyPoints = () => { // ... // 去重 points = removeDuplicatePoint(points); return { startPoint, endPoint, fakeStartPoint, fakeEndPoint, points, }; } // 去重 const removeDuplicatePoint = (points) => { let res = []; let cache = {}; points.forEach(([x, y]) => { if (cache[x + "-" + y]) { return; } else { cache[x + "-" + y] = true; res.push([x, y]); } }); return res; };
如果不考虑效率和最短距离，我们可以直接使用广度优先搜索或者说是回溯算法，也就是从起点开始，挨个尝试起点周边的点，到下一个点又挨个尝试下一个点周边所有的点，如果遇到终点，那么结束，把所经过的点连接起来就是一条路径，接下来我们尝试一下。 在开始算法之前需要先实现如何找出一个点周边的点，如果是在网格中，那么很简单，一个点周边的点就是x、y坐标加1或减1，但是我们这些点彼此之间的距离是不确定的，所以只能根据坐标进行搜索，比如要找一个点右边最近的点，那么根据该点的y坐标进行搜索，看有没有y坐标相同的点，有的话再找出其中最近的，当然，还要检测找出的这个点和目标点的连线是否会穿过起终点元素，是的话这个点也要跳过： // 找出一个点周边的点 const getNextPoints = (point, points) => { let [x, y] = point; let xSamePoints = []; let ySamePoints = []; // 找出x或y坐标相同的点 points.forEach((item) => { // 跳过目标点 if (checkIsSamePoint(point, item)) { return; } if (item[0] === x) { xSamePoints.push(item); } if (item[1] === y) { ySamePoints.push(item); } }); // 找出x方向最近的点 let xNextPoints = getNextPoint(x, y, ySamePoints, "x"); // 找出y方向最近的点 let yNextPoints = getNextPoint(x, y, xSamePoints, "y"); return [...xNextPoints, ...yNextPoints]; }; // 检测是否为同一个点 const checkIsSamePoint = (a, b) => { if (!a || !b) { return false; } return a[0] === b[0] && a[1] === b[1]; };接下来就是getNextPoint方法的实现： // 找出水平或垂直方向上最近的点 const getNextPoint = (x, y, list, dir) => { let index = dir === "x" ? 0 : 1;// 求水平方向上最近的点，那么它们y坐标都是相同的，要比较x坐标，反之亦然 let value = dir === "x" ? x : y; let nextLeftTopPoint = null; let nextRIghtBottomPoint = null; for (let i = 0; i continue; } // 左侧或上方最近的点 if (cur[index] if (cur[index] > nextLeftTopPoint[index]) { nextLeftTopPoint = cur; } } else { nextLeftTopPoint = cur; } } // 右侧或下方最近的点 if (cur[index] > value) { if (nextRIghtBottomPoint) { if (cur[index] nextRIghtBottomPoint = cur; } } } return [nextLeftTopPoint, nextRIghtBottomPoint].filter((point) => { return !!point; }); };checkLineThroughElements方法用来判断一条线段是否穿过或和起终点元素有重叠，也是一个简单的比较逻辑： // 检查两个点组成的线段是否穿过起终点元素 const checkLineThroughElements = (a, b) => { let rects = [rect1, rect2]; let minX = Math.min(a[0], b[0]); let maxX = Math.max(a[0], b[0]); let minY = Math.min(a[1], b[1]); let maxY = Math.max(a[1], b[1]); // 水平线 if (a[1] === b[1]) { for (let i = 0; i return true; } } } else if (a[0] === b[0]) { // 垂直线 for (let i = 0; i return true; } } } return false; };接下来就可以使用回溯算法来找出其中的一条路径，回溯算法很简单，因为不是本文的重点，所以就不详细介绍了，有兴趣的可以阅读回溯（DFS）算法解题套路框架。 计算出坐标点后再更新连线元素，记得要把我们真正的起点和终点坐标加上去： // 矩形移动事件 const onDragMove = () => { // 计算出所有可能的点 let { startPoint, endPoint, fakeStartPoint, fakeEndPoint, points } = computedProbablyPoints(); // 使用回溯算法找出其中一条路径 const routes = useDFS(fakeStartPoint, fakeEndPoint, points); // 更新连线元素 line.points( // 加上真正的起点和终点 (routes.length > 0 ? [startPoint, ...routes, endPoint] : []).reduce( (path, cur) => { path.push(cur[0], cur[1]); return path; }, [] ) ); }; // 使用回溯算法寻找路径 const useDFS = (startPoint, endPoint, points) => { let res = []; let used = {}; let track = (path, selects) => { for (let i = 0; i res = [...path, cur]; break; } let key = cur[0] + "-" + cur[1]; // 该点已经被选择过了 if (used[key]) { continue; } used[key] = true; track([...path, cur], getNextPoints(cur, points)); used[key] = false; } }; track([], [startPoint]); return res; };效果如下：
可以看到确实计算出了一条连接线路径，但是显然不是最短路径，并且回溯算法是一种暴力算法，点多了可能会存在性能问题。 使用A*算法结合曼哈顿路径计算最短路径前面我们使用回溯算法找出了其中一条关联线路径，但是很多情况下计算出来的路径都不是最短的，接下来我们就使用A*算法来找出最短路径。 A*算法和回溯算法有点相似，但是不是盲目的挨个遍历一个点周围的点，而是会从中找出最有可能的点优先进行尝试，完整的算法过程描述如下： 1.创建两个数组，openList存放待遍历的点，closeList存放已经遍历的点； 2.将起点放入openList中； 3.如果openList不为空，那么从中选取优先级最高的点，假设为n： 3.1.如果n为终点，那么结束循环，从n出发，依次向前找出父节点，也就是最短路径； 3.2.如果n不为终点，那么： 3.2.1.将n从openList中删除，添加到closeList中； 3.2.2.遍历n周围的点： 3.2.2.1.如果该点在closeList中，那么跳过该点； 3.2.2.2.如果该点也不在openList中，那么： 3.2.2.2.1.设置n为该点的父节点； 3.2.2.2.2.计算该点的代价，代价越高，优先级越低，反之越高； 3.3.3.3.3.将该点添加到openList； 3.2.3.继续3的循环过程，直到找到终点，或openList为空，没有结果； 根据以上过程，我们创建一个A*类： // A*算法类 class AStar { constructor() { this.startPoint = null; this.endPoint = null; this.pointList = []; // 存放待遍历的点 this.openList = []; // 存放已经遍历的点 this.closeList = []; } // 算法主流程 start(startPoint, endPoint, pointList) { this.startPoint = startPoint; this.endPoint = endPoint; this.pointList = pointList; this.openList = [ { point: this.startPoint, // 起点加入openList cost: 0, // 代价 parent: null, // 父节点 }, ]; this.closeList = []; while (this.openList.length) { // 在openList中找出优先级最高的点 let point = this.getBestPoint(); // point为终点，那么算法结束，输出最短路径 if (checkIsSamePoint(point.point, this.endPoint)) { return this.getRoutes(point); } else { // 将point从openList中删除 this.removeFromOpenList(point); // 将point添加到closeList中 this.closeList.push(point); // 遍历point周围的点 let nextPoints = getNextPoints(point.point, this.pointList); for (let i = 0; i continue; } else if (!this.checkIsInList(cur, this.openList)) { // 如果该点也不在openList中 let pointObj = { point: cur, parent: point,// 设置point为当前点的父节点 cost: 0, }; // 计算当前点的代价 this.computeCost(pointObj); // 添加到openList中 this.openList.push(pointObj); } } } } return [] } // 获取openList中优先级最高的点，也就是代价最小的点 getBestPoint() { let min = Infinity; let point = null; this.openList.forEach((item) => { if (item.cost let res = [point]; let par = point.parent; while (par) { res.unshift(par); par = par.parent; } return res.map((item) => { return item.point; }); } // 将点从openList中删除 removeFromOpenList(point) { let index = this.openList.findIndex((item) => { return checkIsSamePoint(point.point, item.point); }); this.openList.splice(index, 1); } // 检查点是否在列表中 checkIsInList(point, list) { return list.find((item) => { return checkIsSamePoint(item.point, point); }); } // 计算一个点的代价 computeCost(point) { // TODO } }代码有点长，但是逻辑很简单，start方法基本就是对前面的算法过程进行还原，其他就是一些辅助工具方法，只有一个computeCost方法暂时没有实现，这个方法也就是A*算法的核心。 A*算法的所说的节点优先级是由两部分决定的： f(n) = g(n) + h(n)g(n)代表节点n距离起点的代价。 f(n)代表节点n到终点的代价，当然这个代价只是预估的。 f(n)为g(n)加上h(n)，就代表节点n的综合代价，也就是优先级，代价越低，当然优先级越高，修改一下computeCost方法，拆解成两个方法： // 计算一个点的优先级 computePriority(point) { point.cost = this.computedGCost(point) + this.computedHCost(point); }g(n)的计算很简单，把它所有祖先节点的代价累加起来即可： // 计算代价g(n) computedGCost(point) { let res = 0; let par = point.parent; while (par) { res += par.cost; par = par.parent; } return res; }而h(n)的计算就会用到曼哈顿距离，两个点的曼哈顿距离指的就是这两个点的水平和垂直方向的距离加起来的总距离：
对于我们的计算，也就是当前节点到终点的曼哈顿距离： // 计算代价h(n) computedHCost(point) { return ( Math.abs(this.endPoint[0] - point.point[0]) + Math.abs(this.endPoint[1] - point.point[1]) ); }接下来实例化一个AStar类，然后使用它来计算最短路径： const aStar = new AStar(); const onDragMove = () => { let { startPoint, endPoint, fakeStartPoint, fakeEndPoint, points } = computedProbablyPoints(startPos.value, endPos.value); const routes = aStar.start(fakeStartPoint, fakeEndPoint, points); // 更新连线元素 // ... }
可以看到不会出现回溯算法计算出来的超长路径。 优化到上一节已经基本可以找出最短路径，但是会存在几个问题，本小节来试着优化一下。 1.连接线突破了包围框
如上图所示，垂直部分的连接线显然离元素过近，虽然还没有和元素重叠，但是已经突破了包围框，更好的连接点应该是右边两个，下图的情况也是类似的：
解决方法也很简单，前面我们实现了一个判断线段是否穿过或和起终点元素重叠的方法，我们修改一下比较条件，把比较对象由元素本身改成元素的包围框： export const checkLineThroughElements = (a, b) => { // ... // 水平线 if (a[1] === b[1]) { for (let i = 0; i return true; } } } else if (a[0] === b[0]) { // 垂直线 for (let i = 0; i return true; } } } return false; };效果如下：
目前我们的逻辑如果当两个元素太近了，那么是计算不出来符合要求的点的，自然就没有线了：
解决方法也很简单，当第一次路径计算没有结果时我们假设是因为距离很近导致的，然后我们再以宽松模式计算一次，所谓宽松模式就是去掉是否穿过或和元素有交叉的判断，也就是跳过checkLineThroughElements这个方法，另外真正的起点和终点也要加入点列表里参加计算，并且计算的起点和终点也不再使用伪起点和伪终点，而是使用真正的起点和终点，不然会出现如下的情况：
首先修改一下onDragMove方法，将路径计算单独提成一个方法，方便复用： const onDragMove = () => { // 计算点和路径提取成一个方法 let { startPoint, endPoint, routes } = computeRoutes(); // 如果没有计算出来路径，那么就以宽松模式再计算一次可能的点，也就是允许和元素交叉 if (routes.length path.push(cur[0], cur[1]); return path; }, [] ) ); }; // 计算路径 const computeRoutes = (easy) => { // 计算出所有可能的点 let { startPoint, endPoint, fakeStartPoint, fakeEndPoint, points } = computedProbablyPoints(startPos.value, endPos.value, easy); // 使用A*算法 let routes = = aStar.start( easy ? startPoint : fakeStartPoint,// 如果是宽松模式则使用真正的起点和终点 easy ? endPoint : fakeEndPoint, points ); return { startPoint, endPoint, routes, }; };然后修改一下computedProbablyPoints方法，增加一个easy参数，当该参数为true时就将真正的起点和终点加入点列表中： const computedProbablyPoints = (startPos, endPos, easy) => { // ... // 是否是宽松模式 easyMode = easy; // 保存所有可能经过的点 let points = []; // 宽松模式则把真正的起点和终点加入点列表中 if (easy) { points.push(startPoint, endPoint); } // ... }最后再修改一下计算一个点周边的点的方法，去掉是否穿过或和元素交叉的检测： const getNextPoint = (x, y, list, dir) => { // ... for (let i = 0; i continue; } } }最终效果如下：
本文尝试通过A*算法实现了寻找节点的关联线路径，原本以为难点在于算法，没想到在实现过程中发现最难之处在于找点，如果有更好的找点方式欢迎评论区留言。 源码地址：https://github.com/wanglin2/AssociationLineDemo。 参考文章路径规划之 A* 算法 LogicFlow 边的绘制与交互 |
【本文地址】