如何将大区域拆分为凸多边形的算法

Question

3

我正在将A*路径规划算法应用于基于网格的引擎中，但我希望在多边形区域内创建节点，而不仅仅使用网格点。

这个区域中会有障碍物，不能穿过。

我想知道是否有一些算法可以将具有障碍物的大区域分割成具有最小数量的连通凸多边形的图形？

- Max Tyler

我看到这个问题已经问了很长时间了，但我还是想试试运气。你能找到一些可行的解决方案/算法来解决这个问题吗？ - Dmitrii Naumov

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tatarize · Accepted Answer

有很多算法可用。通常你需要处理三角测量算法。你需要删除穿过障碍物的线路，然后可能对其进行最短路径算法。不过我不确定为什么你想要最少连接的凸多边形，但同样可以做到。答案就是这些点的凸包。一个多边形从定义上来说就是最少的。