algorithm - 如何将大面积分割成凸多边形的算法

Question

我正在将 A* 寻路算法实现到基于网格的引擎中，但我想在多边形区域中创建节点，而不仅仅是使用网格点。

该区域将有障碍物，不应移动。

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

Answer 1

他们有很多。通常，您正在处理三角测量算法。您删除了穿过障碍物的线，并可能对其进行最短路径算法。我不确定为什么你想要最少数量的连接凸多边形，但这同样可以做到。答案只是点的凸包。根据定义，一个多边形是那里的最小数字。