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

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

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

• 将每个点从多边形中取出
• 测试该点以查看它是否落在由该集合的其余部分创建的多边形内
• 如果为 true 则删除该点
• 如果为假，请保留要点

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

我想知道的是：

1. 有没有某种方法可以测试我正在处理的多边形是否恰好有这些情况之一（即：连续 3 个故障点？）
   or
2. 有没有更有效的方法来创建凸多边形？

谢谢。

我想也许你正在寻找凸包 http://en.wikipedia.org/wiki/Convex_hull?

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

构建对船体的第一个猜测，该船体有两个向外的面，一个从 l 到 r，一个从 r 到 l。所以你有一个体积为零的多边形。

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

从那时起，虽然任何面前面都有任何点：

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

最后你将得到凸包。