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

Question

我想解构以下多边形的蓝色显示，删除所有的点从多边形，造成凹。

​

​

目前，我试图做的是：

• 把每个点从多边形中取出来
• 测试点，看看它是否在集合的其余部分创建的多边形内。
• 如果为真，移除点
• 如果假的话，保持原点

这在大多数情况下是可行的，但在前一种情况下，(2,3)和(2,4)的点都不会被移除。在这两种情况下，其中一个点将被移除，但另一个点将不取决于传递数组的顺序。

我想知道的是：

1. 是否有什么方法来测试我所处理的多边形是否碰巧有这样的情况(IE:连续3个故障点？) 或
2. 是否有一种更有效的方法来创建凸多边形？

谢谢。

Answer 1

我想也许你是在找凸壳

想到的第一个算法是QuickHull。一开始，取最左和最右边的点，l和r，它们必须在船体上。

在船体上先猜一猜，这是两个向外的面，一个是从l到r，另一个是从r到l，所以你有一个体积为零的多边形。

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

从那时起，任何一张脸前面都有点：

• 找出离脸最远的地方
• 删除此边缘，并将其替换为两条边，一条从原始起点到最远点，另一条从最远点到原始终点。
• 在旧脸前面的所有点中，把前面的第一个新面孔放在前面，把第二个前面的放在前面，不要保留对现在在里面的新面孔的任何引用。

最后你会有凸起的外壳。

Answer 2

为什么不简单地计算点的凸包呢？

这是一个研究得很好的问题，许多算法在书和网上。“扫角”的方法特别常见，例如。

http://courses.csail.mit.edu/6.854/06/scribe/s25-rasmu-sweepline.pdf

Answer 3

你正在寻找的是所谓的“凸壳”的发现。请参阅在维基百科，以获得该问题的算法。“礼品包装”算法易于实现。当yout发现船体时，只需移除所有不是船体一部分的点。