computational-geometry - 使用 Delaunay 和 Dijkstra 进行机器人运动规划

Question

我正在尝试开发一种基于 delaunay 三角剖分、费马点、改进的 dijkstra 算法的算法来实现机器人运动规划。目前我已经介绍了德劳内三角剖分和费马点。我已经开始使用 Dijkstra 使用斐波那契堆。目前我正在研究多边形物体。假设如果我想包括现实生活中的弯曲障碍，我该怎么做？有没有办法将弯曲障碍物近似为多边形障碍物？此外，如果要纳入一个基于动态变化环境的项目，需要哪些基本思想，比如应该涵盖哪些内容？

Answer 1

您可以使用Douglas-Peucker 算法逼近 2d 曲线，或减少折线的顶点数。