如何在二维平面上实现寻找最短路径的程序？

如果在二维平面上存在各种可能的二维形状（圆形、四边形、三角形、不规则形状等）的障碍物，那么如何实现一个机制来寻找绕过这些障碍物的最短路径？我考虑使用Visual C++，因为它提供了许多用于绘制此类图形的图形类。

我已经取得了相当大的进展

1) 首先，我将使用A*搜索（A星）来寻找成本最低的路径

2) 将考虑与直线路径偏差最小的路径作为最佳路径。（不过我不是很确定）

3) 绕过一个图形的最短路径，例如从起点开始，是从该点到以下位置的一条线：

a) 在多边形/四边形的情况下，是最远的顶点b) 在圆形或弧形的情况下，是圆周上的一个点，使得绘制的线与圆相切c) （对于不规则图形，我不确定）

enter image description here

回到第2点——通过比较从这些线到对象各自侧面的最远点的垂线，可以确定两条或多条路径之间最小的偏移量。（希望我已经表达清楚了）。

那么，如何绘制与直线路径垂直的线？ enter image description here

x1,x2,y1,y2,k和l是已知的。我们只需要找到a,b。

直线路径的斜率 * 其垂线的斜率 = -1

=> (y2-y1)/(x2-x1) * (b-l)/(1-k) = -1因此，b = [(x1-x2)/(y2-y1) * (a-k)] + l

我想象通过使用勾股定理，我们可以找到另一个关于坐标的方程。通过这种方式可以找到每条线的长度：dx = x1-x2 dy = y1-y2 dist = sqrt(dxdx + dydy)

然后通过解这两个方程，我们可以找到a,b的正确值。

我再也想不出什么了——有什么想法或建议吗？

回答：

你是否可以对所有形状使用多边形（即直线段）近似？这将大大简化算法的实现。

假设这是可行的：如果你想使用A*，你需要一个可能路径的图形表示。这个图的节点是以下组合：

然后，这个图中的边仅在以下情况下存在于每对节点之间

图中每条边的长度就是它所代表的两个顶点之间的（欧几里得）距离，最短路径总是这些边的子集（我想），你可以通过对这个图应用A*来找到它。

[1] – 为了减少顶点数量，你可以将所有凹形形状变为凸形（除非这会导致起点或终点位于这样的形状内部，那么应该保持凹形）。

[2] – 你可以使用多种数据结构来加速这些查询，例如kD树或四叉树，或者可能结合使用扫描线算法（如http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm）和双连通边列表。

学技术