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

Question

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

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

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

Answer 1

您可以区分两种情况：

要么这条线通过另一条线进入一个图形。在这种情况下，最简单的方法是用它们的方程（它们看起来像 ）来表示你的线（包括障碍物的边界a*x + b*y +c = 0）。然后决定两条线是否相交是一件很简单的事情：

• 两条线 ax+by+c=0 和 dx+ey+f=0 相交当且仅当它们不平行，即当且仅当 a*eb*d != 0

• 然后你必须检查这两条线的交点是否在你实际考虑的线段内。交点有坐标：

  • y = ( cd - af ) / (ae - db)
  • x = ( bf - ec ) / (ae - db)
• 剩下的唯一任务是检查这些 x 和 y 是否属于段（如果它们在定义段的区间内），然后对定义障碍的所有段重复此操作。

如果你有圆圈，它会变得更棘手（这就是为什么你通常只将多边形视为障碍物），但基本上它是相同的想法： - 你有一条线 ax+by+c=0 和一个圆圈 (xa)^2 + (yb)^2 = r^2（圆心 (a,b) 和半径 r）。然后您必须确定它们是否相交、相交点以及它是否属于您考虑的线段。我会把计算留给你。

如果您对在有障碍物的两点之间寻找路径的不同方法感兴趣，您可以使用其他算法，尽管这些算法不会为您提供最短路径，但仅提供路径：

• http://en.wikipedia.org/wiki/Sweep_line_algorithm
• http://en.wikipedia.org/wiki/Voronoi_diagram

与您正在构建的可见性图相比，这些算法的兴趣在于，这两个在您的任何维度上都有效：如果您想将算法升级到维度，您的算法将具有更高的复杂性（需要更多时间才能找到一条路径）然后这两个并不会产生最短路径。

Answer 2

考虑到您迄今为止所做的简单算法：

1. 对于每个形状，将所有顶点存储在一个数组（或列表）中，以便它们出现在形状上（顺时针或逆时针没有区别）。这使您可以轻松地迭代任何给定对象的边缘，因为在这种情况下边缘是(P ₁ , P ₂ ) , (P ₂ , P ₃ ) , ... (P _N , P ₁ )其中N是数字的顶点。
2. 对于您要检查的每条线是否与任何对象碰撞，请遍历您表示的所有边，以及您要检查的线是否与任何边缘相交 - 线与给定对象碰撞。

检查线与边缘的交叉是一个几何问题。如果我们正在检查的线的边界点是P ₁ =(x ₁ ,y ₁ )和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)的值后，您应该检查它是否位于两条线（我们正在检查的线和边缘）的边界点之间的部分上。如果这是真的，那么您的线条会相互交叉。

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