algorithm - 用于通过填充有多边形的空间进行路由的算法

Question

我有一个（地理）地图，由多边形组成，描绘了土地和一艘试图从 A 到 B 而不撞到任何土地的船。最好，它应该遵循最短的可用路径。

我有一个大部分时间都有效的算法，但它相当笨拙且效率低下。非常感谢任何对我可以使用的算法的提示或引用。

Answer 1

创建图表：

• 为每个多边形的每个顶点、起点和终点创建一个节点。
• 如果从一个节点到另一个节点有一条直线，则在两个节点之间创建一条边，而不是穿过任何障碍物。

使用 A* 算法 ( http://en.wikipedia.org/wiki/A_star ) 在结果图中找到最短路径。将距离估计为直线距离。

您可以使用任何类型的障碍物，只要您能够确定“有趣”点的集合：它们是每对障碍物的所有切线的接触点（凸多边形的几乎所有顶点都是“有趣的”。 ) 以及所有两次接触相同（非凸）障碍物的线。