geometry - 多边形分解——去除凹点形成凸多边形

Question

我想解构下面以蓝色显示的多边形，从多边形中移除所有导致凹陷的点。

目前，我一直在尝试做的是:

• 从多边形中取出每个点
• 测试点以查看它是否落在由其余集合创建的多边形内
• 如果为真，删除该点
• 如果错误，保持观点

这在大多数情况下都有效，但在之前的情况下，(2,3) 和 (2,4) 处的点不会同时被删除。在这两种情况下，其中一个点将被删除，但另一个点将不取决于传入数组的顺序。

我想知道的是:

1. 有什么方法可以测试我正在处理的多边形是否恰好有其中一种情况(即:连续 3 个故障点？)
   或
2. 是否有更有效的创建凸多边形的方法？

谢谢。

Answer 1

我想您可能正在寻找 convex hull ？

首先想到的算法是 QuickHull。最初，取最左边和最右边的点 l 和 r。它们一定在船体上。

首先猜测船体有两个向外的面，一个从 l 到 r，一个从 r 到 l。所以你有一个零体积的多边形。

将所有剩余的点分成lr前面的和rl前面的。

从那时起，当任何面前面都有任何点时:

• 找到离人脸最远的点
• 删除这条边，用两条边代替，一条从原起点到最远点，一条从最远点到原终点
• 在旧面孔前面的所有点中，将那些放在您添加的第一个新面孔前面的点放在它的前面集中，将第二个前面的那些放在它的前面集中不要保留对现在内部人员的任何引用

最后你会得到凸包。