3.2.2.1.设置为该点的父节点;(当前节点的父节点)(一个子节点对应多个父节点)

如果使用流程图绘制工具,可能需要了解如何计算节点之间的连接线:

在页面模板部分,您可以提供一个容器:

本节主要用于创建两个可拖动矩形图元和一个连接图元。当然,连接器当前没有顶点数据:

其效果如下:

接下来,我们可以绘制这条连接线,只要我们在拖动图形时实时计算连接线的顶点,然后将它们更新为多段线元素。

整个画布上的所有点实际上都是可能的点,但我们的连接线是最短的可能路径,因此没有必要考虑所有点。我们可以根据一定的规则缩小范围,然后计算最优路线。

首先,起点和终点必须至关重要。下图是一个示例。假设我们想将左上角的矩形顶部的中间位置连接到右下角的矩形顶端的中间位置:

接下来,我们设定了两个原则:

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的循环,直到找到终点,或终点为空且无结果;

根据上述过程,我们创建了一个类:

代码有点长,但逻辑非常简单。该方法基本上恢复了以前的算法过程。其他方法是一些辅助工具。只有一种方法尚未实现,这是算法的核心。

算法的节点优先级由两部分确定:

表示从起点开始的节点成本。

它表示从节点到端点的成本。当然,这一成本只是估计的。

此外,它表示节点的综合成本,即优先级。成本越低,优先级越高。修改方法并将其分解为两种方法:

计算非常简单。其所有祖先节点的成本可以累积:

曼哈顿距离用于计算。两点之间的曼哈顿距离是指两点之间的水平距离和垂直距离的总距离:

对于我们的计算,即从当前节点到终点的曼哈顿距离:

接下来,实例化一个类并使用它计算最短路径:

可以看出,由回溯算法计算的超长路径将不会出现。

通过最后一节,我们基本上可以找到最短路径,但会有几个问题。在本节中,我们将尝试对其进行优化。

如上图所示,垂直部分的连接线明显太靠近元件。虽然它与图元不重叠,但已突破边界框。更好的连接点应该是右边的两个。下图中的情况类似:

解决方案也非常简单。之前,我们实现了一种方法来确定线段是通过起始元素还是与结束元素重叠。我们修改了比较条件,并将比较对象从元素本身更改为元素的边界框:

其效果如下:

目前,如果两个元素彼此太接近,我们无法计算满足要求的点。自然,没有直线:

解决方案也非常简单。当第一次路线计算没有结果时,我们假设距离非常近,然后在松散模式下再次计算。所谓的松散模式是取消对其是否穿过或与元素相交的判断,即跳过此方法。此外,实际起点和终点应添加到点列表中进行计算。计算的起点和终点将不再使用伪起点和伪终点,而是使用真实起点和终点。否则,将发生以下情况:

首先,修改该方法,将路径计算分离为一种方法以供重用:

3.2.2.1.设置为该点的父节点;(当前节点的父节点)(一个子节点对应多个父节点) 热门话题

然后修改该方法以添加参数。当参数为时,实际起点和终点将添加到点列表中:

最后,修改了计算点周围点的方法,以消除对点是否穿过或与元素相交的检测:

最终效果如下:

路径规划的A*算法


当起点和终点相反时:

[新闻网]

发表评论

Copyright 2002-2022 by 北京晨峰机电网(琼ICP备2022001899号-3).All Rights Reserved.