从零开始画自己的DAG作业依赖图(四)--节点连线优化版程序员

概述
上个版本简单的连线在一些复杂场景，尤其层级比较多，连线跨层级比较多的情况下，会出现线条会穿过矩形的情况，这一讲就是在这个基础上，去优化这个连线。
场景分析
在下面几种情况下，简单版本的画法已经没法办规避障碍节点了。

文章图片

这种情况,由于简单版本，我们只在整条路径上添加了2个拐点，这种画法，当出现上述情况，线条就会被B挡住，实际的需求，我们要规避这种节点，绕开。
应该是下面这种情况:
【从零开始画自己的DAG作业依赖图(四)--节点连线优化版】
文章图片

再复杂一点的场景如下

文章图片

这时候有2个节点挡住了。我们要做的就是按照图示，绕开节点。
思路分析

文章图片

观察分析，我们要想绕开，一些障碍节点，我们先要知道哪些节点会挡住，才可以绕开。有两个已经明确数据是，每一层的节点的坐标我们是知道，起点p1, 终点是p6。我们可以模拟这个过程：

如果p1 所在直线没有被最近的下一层挡住，也就是图中D,E,F节点挡住的话，那就说明，起点可以先画到p2
画到p2 之后，继续判断第三层节点，由于B节点会挡住从p2 往下画的竖线，所以绕开B节点，由于P6终点再p2 左侧，所以，在B的左侧找一个空白的地方，即p3
现在画到p3了，这时候起点编程p3了，问题转换成画p1的场景了
一直循环，直到到终点这一层，把这个路径上的所有的折点记录下来，就是我们的路径

具体实现

function drawLine(startX, startY, endX, endY, color, sourceNodeName, targetNodeName, endLayer, startLayer, lineNodes) { var points = []; //保存路径上的折点 var sx =startX; var ex = endX; for (var layer = startLayer + 1; layer < endLayer; layer++) { //判断当前这一层有没有节点挡住 var coverRectIndex = -1; for(var i = 0; i < lineNodes[layer].length; i++){ if(lineNodes[layer][i].x < sx && (sx - lineNodes[layer][i].x) < config.rect.width){ coverRectIndex = i; break; } } if(coverRectIndex === -1){ //如果没有挡住，检查下一层 continue; }else{ //如果有挡住，则需要根据起点和目标节点相对位置，决定往左边绕还是后边绕var midY = lineNodes[layer][coverRectIndex].y - 40; // 计算是左边的空隙还是右边的空隙 var midX = lineNodes[layer][coverRectIndex].x; midX += sx > ex? -(config.rect.space / 2 + config.rect.width) : (config.rect.space / 2 + config.rect.width); while (true) { var flag = false; if (nodeLines[layer]) { for (var i = 0; i < nodeLines[layer].length; i++) { var line = nodeLines[layer][i]; if (line.startY === midY) { if (checkCross(sx, midX, line.startX, line.endX)) { flag = true; } } if (flag) break; } } else { nodeLines[layer] = []; } if (!flag) break; midY -= lineDis; } if (sx !== midX) { nodeLines[layer].push({ startX: sx, startY: midY, endX: midX, endY: midY }) } // 存储路径上点 points.push({ x: sx, y: midY }); points.push({ x: midX, y: midY }); sx = midX; } }//单独处理最后一层的场景 var midY = lineNodes[endLayer][0].y - 40; while (true) { var flag = false; if (nodeLines[endLayer]) { for (var i = 0; i < nodeLines[endLayer].length; i++) { var line = nodeLines[endLayer][i]; if (line.startY === midY) { if (checkCross(sx, ex, line.startX, line.endX)) { flag = true; } } if (flag) break; } } else { nodeLines[endLayer] = []; } if (!flag) break; midY -= lineDis; } if (sx !== ex) { nodeLines[layer].push({ startX: sx, startY: midY, endX: ex, endY: midY }) } points.push({ x: sx, y: midY }); points.push({ x: ex, y: midY }); return points; }

总结
这里是在原来的基础上进行优化的，实现了规避障碍节点的功能。一开始，我想到是 A*算法去搜索，但是像素点太多，算法复杂度Hold不住，后面卡在缩点的环节上，经过同事的指点，才实现了当前的这种优化，还是要多学习，多总结！