如果使用了流程图绘制工具，您可能会想知道如何计算节点之间的连接线：
在页面模板部分，您可以提供一个容器：
此部分主要用于创建两个可拖动矩形元素和一个连接元素。当然，连接器目前没有顶点数据：
其效果如下：
接下来，我们可以绘制这条连接线，只要我们在拖动图形时实时计算连接线的顶点，然后将它们更新为多段线元素。
整个画布上的所有点实际上都是可能的点，但我们的连接线是尽可能短的路径，因此不必考虑所有点。我们可以根据一定的规则缩小范围，然后计算最优路线。
首先，起点和终点必须至关重要。下图是一个示例。假设我们想将左上角的矩形顶部的中间位置连接到右下角的矩形顶端的中间位置：
接下来，我们设定了两个原则：
1.连接线应尽可能不与图纸边缘重叠
2.连接线应尽可能不穿过元件
我们为什么要尽力呢 因为当两个元素过于接近或重叠时，这些是不可避免的。
结合上述两个原则，我们可以指定在元素周围的特定距离内不允许任何线通过，这相当于在元素外部设置矩形边界框：
穿过起点和终点并垂直于起点和终点边缘的直线与边界框的交点必须穿过，这两点是唯一可以与起点和终点直接连接的点。因此，我们可以将这两点视为“起点”和“终点”，这样我们可以在计算过程中少计算两点：
要计算矩形移动事件中的点，首先缓存矩形的位置和大小信息，然后定义起点和终点的坐标，最后定义一个数组来存储所有可能的点：
由于起点和终点可以在矩形的任何方向上，我们编写了一个方法来获得伪起点和伪终点，并将它们添加到数组中：
伪起点和伪终点将形成一个矩形。起点元素的矩形和边框可以形成更大的矩形。矩形的四个角是连接线可能穿过的点：
将这些点添加到数组中，将重复一个点和伪端点，但这并不重要。最后我们可以再次删除它们：
从图中可以看出，相关线要么从右侧连接，要么从左侧连接。
类似地，由伪起点和伪终点形成的矩形也将与端点元素的边界框形成更大的矩形。该矩形的四个顶点也可以穿过。当端点元素高于起点元素时，它将通过：
上述点基本上可以满足起点和终点在元素上方的情况，但对于以下起点在元素上方、终点在元素左侧的情况，则不能满足：
显然，如果存在以下几点：
这实际上是穿过起点和终点并垂直于起点和终点所在侧的两条线的交点。为了找到交点，我们可以先根据两点计算线性方程，然后建立两个方程来计算交点。然而，我们的线路是水平和垂直的，所以没有必要这么麻烦。这两条线要么平行，要么一条水平，一条垂直。很容易列出所有情况：
使用此方法，我们可以将此交点添加到阵列中：
此处计算的点可以满足大多数条件，但还有另一种情况无法满足。当起点和终点相对时：
因此，当先前计算的点不存在时，我们计算通过伪起点和伪终点的垂直线和水平线的交点：
您可以在这里找到您可以通过的几乎所有点。有：
接下来，重复数据消除和导出相关数据：
如果我们不考虑效率和最短距离，我们可以直接使用广度优先搜索或回溯算法，即从起点开始，逐个尝试起点周围的点，然后逐个尝试下一点周围的所有点。如果我们遇到终点，那幺终点，连接我们通过的点就是一条路径。接下来，我们尝试。
在开始算法之前，我们需要了解如何找到点周围的点。如果它在网格中，则非常简单。点周围的点是坐标加或减，但这些点之间的距离不确定，因此我们只能根据坐标进行搜索。例如，要找到点右侧最近的点，我们可以根据点的坐标进行搜索，以查看是否有具有相同坐标的点，如果是，则找到最近的点。当然，还需要检测找到的点和目标点之间的线是否会穿过起始元素和结束元素。如果是，也应跳过这一点：
接下来是该方法的实现：
该方法用于确定线段是穿过起始图元还是与终止图元重叠。这也是一个简单的比较逻辑：
计算坐标点后更新线元素。记住添加我们的实际开始和结束坐标：
其效果如下：
可以看出，确实计算了连接线路径，但它显然不是最短路径。此外，回溯算法是一种暴力算法，可能存在点太多的性能问题。
以前，我们使用回溯算法查找一条关联线路径，但在许多情况下，计算的路径不是最短的。接下来，我们使用该算法来寻找最短路径。
该算法在某种程度上类似于回溯算法，但它不会盲目地逐个遍历点周围的点。相反，它将找到最有可能的点，并首先尝试它们。完整的算法过程描述如下：
1.创建两个数组以存储要遍历的点和已遍历的点；
2.将起点放在第一个位置；
3.如果不为空，则选择优先级最高的点，假设：
3.1.如果是终点，则结束循环，从开始，并找到父节点，即最短路径；
3.2.如果不是终点，则：
3.2.1.从中删除并添加到；
3.2.2.遍历周围点：
3.2.2.1.如果该点位于，则跳过该点；
3.2.2.3.如果该点不在中，则：
3.2.2.1.设置为该点的父节点；
计算该点的成本。成本越高，优先级越低，反之亦然；
3.3.3-3.3.将此点添加到；
3.2.3.继续3的循环，直到找到终点，或者终点为空，并且没有结果；
根据上述过程，我们创建了一个类：
代码有点长，但逻辑非常简单。该方法基本上是恢复以前的算法过程。其他方法是一些辅助工具。只有一种方法尚未实现，这是算法的核心。
算法的节点优先级由两部分确定：
表示从起点开始的节点成本。
它表示从节点到终点的成本。当然，这一成本只是估计的。
此外，它表示节点的综合成本，即优先级。成本越低，优先级越高。修改该方法并将其分解为两种方法：
其计算非常简单。其所有祖先节点的成本可以累积：
曼哈顿距离用于计算。两点的曼哈顿距离是指两点的水平距离和垂直距离的总距离：
对于我们的计算，即从当前节点到终点的曼哈顿距离：
接下来，实例化一个类并使用它计算最短路径：
可以看出，由回溯算法计算的超长路径将不会出现。
通过最后一节，我们基本上可以找到最短路径，但会有几个问题。在本节中，我们将尝试对其进行优化。
如上图所示，垂直部分的连接线明显太靠近元件。虽然它与图元不重叠，但已突破边界框。更好的连接点应该是右边的两个。下图中的情况类似：
解决方案也非常简单。之前，我们实现了一种方法来确定线段是穿过起始元素还是与终止元素重叠。我们修改了比较条件，并将比较对象从元素本身更改为元素的边界框：
其效果如下：
目前，如果两个元素太接近，我们无法计算出满足要求的点，自然没有直线：
解决方案也非常简单。当第一次路线计算没有结果时，我们假设距离非常近，然后在松散模式下再次计算。所谓的松散模式是取消对其是否穿过或与元素相交的判断，即跳过此方法。此外，应将真实起点和终点添加到点列表中进行计算，计算出的起点和终点将不再使用伪起点和伪终点，而是使用真实起点和端点，否则将出现以下情况：
首先，修改该方法，将路径计算分离为一种方法，以便于重用：
然后修改该方法以添加参数。当参数为时，实际起点和终点将添加到点列表中：
最后，修改计算点周围点的方法，以消除对点是否穿过或与元素相交的检测：
最终效果如下：
路径规划的A*算法
发表评论