algorithm - 如何检测一条线是否与另一个图形重合？

Question

我正在尝试编写一个程序来找到两点之间的最短路径。

我想到的是将起点连接到每个形状的所有顶点。这些点中的每一个都将连接到所有其他点 - 从而形成一种树。在圆形的情况下 - 线将达到与圆或弧形成切线的点(因为这是围绕对象的最短路径)。然而，那些穿过其他物体的线被处理掉了。其余路径进行 *A** 搜索。

但是现在我该如何让程序识别穿过其他图形的线呢？我使用的是 Visual C++，所以我可以通过将某些坐标传递给相应的函数(例如 LineTo(21,23))在客户区绘制形状。它如何知道一条线何时进入另一个图形？

Answer 1

考虑到您到目前为止所做的事情的直接算法:

1. 对于每个形状，将所有顶点按照它们出现在形状上的顺序存储在一个数组(或列表)中(顺时针或逆时针没有区别)。这使您可以轻松地遍历任何给定对象的边缘，因为在这种情况下边缘是 (P₁, P₂), >(P₂, P₃), ... (P_N, P₁) 其中 N 是顶点数。
2. 对于您要检查的每条线是否与任何对象发生碰撞，遍历您已标记的所有边，以及您正在检查的线是否穿过任何边 - 线与给定对象发生碰撞。

检查线与边的交叉是一个几何问题。如果我们正在检查的线的边界点是 P₁=(x₁,y₁) 和 < strong>P₂=(x₂,y₂)，边的边界点为P₃=(x₃,y₃) 和P₄=(x₄,y₄) 那么你应该求解线性方程组:

(x₂ - x₁) y + (y₁ - y₂) x = x₁ y₂ - x₂ y₁ ,
(x₄ - x₃) y + (y₃ - y₄) x = x₃ y₄ - x₄ y₃ .

获得(x, y) 的值后，您应该检查它是否位于两条线(我们正在检查的线和边缘)的边界点之间的部分。如果那是真的，那么您的线条会相互交叉。

注意:您可以通过在检查碰撞时不遍历每个对象的边缘，而只遍历在线路径中的那些对象来缩短运行时间。例如，这可以通过计算包含每个对象的最小矩形来完成，并检查您的线是否穿过矩形，如果不通过则取消对象进一步检查。