如何实现一个程序来查找二维平面中的最短路径？

如果在二维平面上没有。所有可能的二维形状（圆形、四边形、三角形、不规则形状...）的障碍物，那么如何实现一种机制来找到障碍物周围的最短路径？我正在考虑使用 Visual C++，因为它提供了许多图形类来绘制此类图形。

我已经走了很远

1）首先我将使用 A* 搜索（A-star）来找到成本最低的路径

2) 与直线路径位移最小的路径将被视为最佳路径。 （虽然不太确定）

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

a) the farthest vertex in case of a polygon/quadrilateral
b) a point on the circumference such that the line drawn would be tangential to the circle, in case of a circle or arc
c) (not sure about irregular figures)

现在回到 2) 点——两条或更多条路径之间的最小位移可以通过比较这些线与物体各自侧面最远点的垂线来确定。 （希望我已经让自己明白了）。

So then- how do we draw perpendiculars to the straight path?

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

直线斜率 * 垂线斜率 = -1

=> (y2-y1)/(x2-x1) * (b-l)/(1-k) = -1
hence, b = [(x1-x2)/(y2-y1) * (a-k)] + l

我想象通过使用毕达哥拉斯定理，我们可以根据坐标找到另一个方程。每条线的长度可以通过以下方式找到： dx = x1-x2 dy = y1-y2 距离 = sqrt(dxdx + dydy)

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

我想不出更多的东西了——有什么想法或建议吗？

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

假设这确实是可能的：如果你想使用 A* 那么你需要一个图形表示 您可以采取的可能路径。该图的节点是以下各项的组合：

• 所有形状的所有顶点[1]，以及
• 起点和终点
• {起点和终点之间的直线段}与所有形状之间的所有交点。

那么，只有当以下情况时，该图中的边才位于每对节点之间：

• 它们对应的两个顶点之间存在一条直线
• 不与任何形状相交[2]。

图中每条边的长度就是它所代表的两个顶点之间的（欧几里德）距离，并且最短路径始终是这些边的子集（我认为），您可以通过将 A* 应用于该图来找到它。

[1] - 要减少顶点数量，您可以使所有凹形变为凸形（除非这会导致开始 或者终点位于这样的形状内，则应保持凹形）。

[2] - 您可以使用各种数据结构来加速这些查询，例如 kD 或四叉树，或者可以使用扫描线算法（例如http://en.wikipedia.org/wiki/Bentley%E2%80%93 奥特曼算法 http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm）与双连接边列表相结合。