使用 voronoi 寻路
Pathfinding with voronoi
我的大学项目进入了死胡同，我找不到解决的办法。问题是：
给定一个半径为r的圆形机器人（绿色圆圈）
我需要找到一条通往蓝点终点的路径（任何不是最佳路径）。
下图
障碍物是红色的多边形，周围是青色的线
代表闵可夫斯基和。
黑点代表维诺图
- 周围的蓝色框是外边框
所以首先我应该找到距离 voronoi 图点的起点（机器人）和终点更近的点。这些点显示在图像中（青色点）。
然后我想用像 A* 这样的算法之王来搜索上面找到的青色点沿着 voronoi 点的路径，这样我会找到最安全的路径。
问题是我无法知道哪些是 voronoi 图中每个点的邻居。因为正如您在图表的某些部分中看到的那样，存在很大的差距。
那么你有什么建议？
感谢您的宝贵时间。
The problem is that I don't have a way of knowing which are the neighbors of each point in the Voronoi diagram. Because as you can see in the some parts of the diagram there are big gaps.
可能有更好的解决方案，但这里有一个您可以尝试的简单算法：
寻找（或手动设置）"connected"点之间的最长距离，D。
计算 Voronoi 图每对点之间的距离 table，该距离小于或等于 D。
连接所有以较短距离开始的点，除非它们之间已经存在比 D 短的路径（以避免不必要的小循环和切角）。
找到离你的机器人最近的点和离你的目的地最近的点。
运行 您在步骤 3 中构建的图上的最短路径算法。
- 创建代表您的地图的黑白图像。它应该以全黑开始。
- 将障碍物渲染成白色。
- 使用圆形过滤器将图像放大为圆形机器人的大小。
- 找到从 A 到 B 的仅穿过黑色像素的最短路径。
我的大学项目进入了死胡同，我找不到解决的办法。问题是：
给定一个半径为r的圆形机器人（绿色圆圈） 我需要找到一条通往蓝点终点的路径（任何不是最佳路径）。
下图
障碍物是红色的多边形，周围是青色的线 代表闵可夫斯基和。
黑点代表维诺图
- 周围的蓝色框是外边框
所以首先我应该找到距离 voronoi 图点的起点（机器人）和终点更近的点。这些点显示在图像中（青色点）。
然后我想用像 A* 这样的算法之王来搜索上面找到的青色点沿着 voronoi 点的路径，这样我会找到最安全的路径。
问题是我无法知道哪些是 voronoi 图中每个点的邻居。因为正如您在图表的某些部分中看到的那样，存在很大的差距。
那么你有什么建议？
感谢您的宝贵时间。
The problem is that I don't have a way of knowing which are the neighbors of each point in the Voronoi diagram. Because as you can see in the some parts of the diagram there are big gaps.
可能有更好的解决方案，但这里有一个您可以尝试的简单算法：
寻找（或手动设置）"connected"点之间的最长距离，D。
计算 Voronoi 图每对点之间的距离 table，该距离小于或等于 D。
连接所有以较短距离开始的点，除非它们之间已经存在比 D 短的路径（以避免不必要的小循环和切角）。
找到离你的机器人最近的点和离你的目的地最近的点。
运行 您在步骤 3 中构建的图上的最短路径算法。
- 创建代表您的地图的黑白图像。它应该以全黑开始。
- 将障碍物渲染成白色。
- 使用圆形过滤器将图像放大为圆形机器人的大小。
- 找到从 A 到 B 的仅穿过黑色像素的最短路径。