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

Question

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

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

我想知道是否有某种算法可以将具有障碍物的较大区域分割成具有尽可能少的连接凸多边形数量的图形？

Answer 1

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