用voronoi搜索路径

Question

我的大学项目已经到了死胡同，我找不到解决的办法。问题是：

给出了半径为r的圆形机器人(绿色圆)，我需要找到一条到达终点的路径(任何路径都不是最佳路径)，即蓝点。。

图像在下面

• 障碍物是红色的多边形，周围的青色线代表Minkowski和。
• 黑点代表voronoi图。
• 周围的蓝色盒子是外面的边框。

所以首先，我认为我应该找到更接近开始点(机器人)和voronoi图点的终点。这些点在图像中显示(青色点)。

然后我想用一些算法之王，比如A*，寻找沿着voronoi点在上面发现的青色点的路径，这样我就可以找到最安全的路径了。

问题是，我没有办法知道哪个是voronoi图中每个点的近邻。因为正如你在图表的某些部分所看到的，有很大的差距。

​

​

那你有什么建议？

谢谢您抽时间见我。

Answer 1

1. 创建一个表示地图的黑白图像。一开始应该是黑色的。
2. 把你的障碍变成白色。
3. 使用圆形过滤器放大你的圆形机器人大小的图像。
4. 找到从A到B的最短路径，该路径只遍历黑色像素。

​

​

Answer 2

问题是，我没有办法知道哪个是Voronoi图中每个点的近邻。因为正如你在图表的某些部分所看到的，有很大的差距。

也许有更好的解决方案，但这里有一个简单的算法，您可以尝试：

1. 查找(或手动设置)“连通”点之间的最长距离，D。
2. 在Voronoi图的每一对点之间建立一个距离表，其中的距离小于或等于D。
3. 连接所有点，从较短的距离开始，除非路径短于D之间已经存在(以避免不必要的小环和切角)。
4. 找到离你的机器人最近的点，离你的目的地最近的地方。
5. 在步骤3中构建的图上运行最短路径算法。