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

Question

我想解析以蓝色显示的以下多边形,从多边形中删除导致凹陷的所有点.

目前,我一直试图做的是:

• 从多边形中取出每个点
• 测试该点以查看它是否属于由该组的其余部分创建的多边形
• 如果为true则删除该点
• 如果错误保持重点

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

我想知道的是:

1. 有没有办法测试,看看我正在处理的多边形是否恰好有这些情况之一(IE:连续3个故障点？)
   或
2. 有没有更简单的方法来创建凸多边形？

谢谢.

Answer 1

我想也许你正在寻找凸壳？

想到的第一个算法是QuickHull.最初,取最左边和最右边的点l和r.他们必须在船体上.

构造对船体的第一个猜测是两个外表面,一个从l到r,一个从r到l.所以你有一个体积为零的多边形.

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

从那时起,任何面孔都有任何积分:

• 从脸上找到最远点
• 删除此边缘并将其替换为两条边,一条从原始起点到最远点,一条从最远点到原始终点
• 在旧面前的所有点,将那些放在前面的第一个新面孔的前面,放在前面的第二个面前,然后放入保留对现在内部人员的任何引用

最后你将拥有凸壳.