我正在尝试在世界海洋上编制探路者。我之前在包含陆地和水细胞的细胞网格上使用了A *算法。但我认为更好的解决方案是拥有大陆，岛屿和多边形;计算两者之间空间的可见性网格（仅一次）;然后在可见性图表中包含原点和目的地;然后在结果图上求解A *。环顾四周，我找到了一本名为计算几何的书，它描述了一种计算可见性图的算法。但是，在尝试用C ++实现它之前 - 这听起来像个好主意吗？
据我所知，已经提出了许多不同的算法用于计算可见性图，具有不同的数值复杂性。在我看来，这是一个活跃的领域，而不是已经解决的好东西。所以在我看来这是一个真正的问题。如果您不这么认为，请告诉我原因！
编辑：我现在已经实现了一种算法，该算法首先在包含多边形的世界地图上计算可见性图，其中包含大约5,000个顶点。在第二步中，A *在可见性图上运行。在运行时间和内存方面，可能存在对地图详细程度的限制。目前，可见性图表在我的笔记本电脑上计算大约需要10分钟（我相信该算法非常有效;但我也相信我的代码效率不高，可能会显着加速）。计算可见性图后，A *非常快。非常感谢您给出的答案和评论！
规划图形而不是单元格分解是提高路径和运动规划算法性能的绝佳方法。然而，许多处理计算几何的算法都充满挑战（特别是当你不能犯错误时），并且通常最好依赖于该领域专家开发的可靠的计算几何库。
可能值得注意的是，过去15年中路径规划的大部分研究都集中在概率运动规划技术上，而不是过度复杂化您的解决方案。这些技术的两个最着名的例子是快速探索随机树（RRT）和概率路线图（PRM）。这些算法易于实现，有大量示例可用，并且几乎不需要深入了解几何知识即可开始使用。
我有完全相同的用例，最终实现了Lee的可见性图算法，该算法在O（n ^ 2 log n）时间内运行。如果有人有类似的用法，我把它变成了Python包：https://github.com/TaipanRex/pyvisgraph/
我还写了一些解释算法的博客文章：
https://taipanrex.github.io/2016/09/17/Distance-Tables-Part-1-Defining-the-Problem.html
https://taipanrex.github.io/2016/10/19/Distance-Tables-Part-2-Lees-Visibility-Graph-Algorithm.html
为了交互式地使用可见性图，我做了：https://github.com/TaipanRex/visgraph_simulator
为了使路径规划的可见性图算法具有时间和内存效率，可以利用一些几何属性来减少可见性图而不失去最优性（=总是找到真正最短的路径）。本文解释得很好：A thesis describing the general procedure and a few tweaks in chapter 4.4
还可以看看：
My python package for visibility based path planning
Open source C++ library for 2D floating-point visibility algorithms, path planning