我有一张(地理) map ，由描绘陆地的多边形和试图从 A 地到达 B 地而不撞到任何陆地的船组成。最好，它应该遵循最短的可用路径。
我有一个大部分时间都有效的算法，但它相当笨拙且效率低下。非常感谢对我可以使用的算法的任何提示或引用。
最佳答案
创建图表:
- 为每个多边形的每个顶点、起点和终点创建一个节点。
- 如果有一条直线从一个节点到另一个节点，不经过任何障碍物，则在两个节点之间创建一条边。
使用 A* 算法 ( http://en.wikipedia.org/wiki/A_star ) 在结果图中找到最短路径。将距离估计为直线距离。
您可以使用任何类型的障碍物，只要您能够确定一组“有趣的”点:它们是每对障碍物的所有切线的接触点(凸多边形的几乎所有顶点都是 '有趣的'。)和所有两次接触相同(非凸)障碍物的线。
关于通过充满多边形的空间路由的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11217038/