我正在尝试编写一个程序来找到两点之间的最短路径。
我想到的是将起点连接到每个形状的所有顶点。这些点中的每一个都将连接到所有其他点 - 从而形成一种树。在圆形的情况下 - 线将达到与圆或弧形成切线的点(因为这是围绕对象的最短路径)。然而,那些穿过其他物体的线被处理掉了。其余路径进行 *A** 搜索。
但是现在我该如何让程序识别穿过其他图形的线呢?我使用的是 Visual C++,所以我可以通过将某些坐标传递给相应的函数(例如 LineTo(21,23)
)在客户区绘制形状。它如何知道一条线何时进入另一个图形?
最佳答案
考虑到您到目前为止所做的事情的直接算法:
- 对于每个形状,将所有顶点按照它们出现在形状上的顺序存储在一个数组(或列表)中(顺时针或逆时针没有区别)。这使您可以轻松地遍历任何给定对象的边缘,因为在这种情况下边缘是 (P1, P2), >(P2, P3), ... (PN, P1) 其中 N 是顶点数。
- 对于您要检查的每条线是否与任何对象发生碰撞,遍历您已标记的所有边,以及您正在检查的线是否穿过任何边 - 线与给定对象发生碰撞。
检查线与边的交叉是一个几何问题。如果我们正在检查的线的边界点是 P1=(x1,y1) 和 < strong>P2=(x2,y2),边的边界点为P3=(x3,y3) 和P4=(x4,y4) 那么你应该求解线性方程组:
(x2 - x1) y + (y1 - y2) x = x1 y2 - x2 y1 ,
(x4 - x3) y + (y3 - y4) x = x3 y4 - x4 y3 .
获得(x, y) 的值后,您应该检查它是否位于两条线(我们正在检查的线和边缘)的边界点之间的部分。如果那是真的,那么您的线条会相互交叉。
注意:您可以通过在检查碰撞时不遍历每个对象的边缘,而只遍历在线路径中的那些对象来缩短运行时间。例如,这可以通过计算包含每个对象的最小矩形来完成,并检查您的线是否穿过矩形,如果不通过则取消对象进一步检查。
关于algorithm - 如何检测一条线是否与另一个图形重合?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13304575/