如果终点元素高于起点元素,则通过以下内容:

如果使用流程图绘制工具,您可能想知道如何计算节点之间的连接线。

“页面模板”部分提供以下容器:。

此部分主要用于创建两个可拖动的矩形元素和一个连接元素。当然,连接器没有顶点数据。

其效果如下:。

然后,在拖动图形时,只需实时计算连接线的顶点并将其更新为多段线元素即可绘制该连接线。

整个画布上的每一个点实际上都是可能的一点,但是我们的连接线是尽可能短的路径,所以不需要考虑所有的点。可以根据一定的规则缩小范围,计算最佳路线。

首先,起点和终点必须重要。下图为示例:。假设您想将左上矩形顶部的中央位置连接到右下矩形顶部的中央位置。

如果终点元素高于起点元素,则通过以下内容: 热门话题

接下来,设置两个原则。

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*算法


如果起点和终点相对:

[直播竞答]

发表评论

Copyright 2002-2022 by 步涌热水器网(琼ICP备2022001899号-3).All Rights Reserved.