由顶点数组组成凸多边形的最大前缀

Question

相关问题：多边形分解 - 移除凹点以形成凸多边形

我正在寻找一种算法，能够实现以下功能：

输入是一个二维点数组（P₀…P_N-1），数组长度N的大小不固定（3 ≤ N < ∞）。对于任意M ≤ N，可能存在由P₀…P_M-1这些点按某种顺序组成的凸多边形。

注意：边缘不一定是数组中相邻的点对。

最有效的算法是什么，以便找到最大的M，使得这个凸多边形存在？

我的当前算法非常低效。我首先测试M = 3，然后是M = 4，M = 5等等，计算出凸包，然后测试所有的P₀…P_M-1是否是凸包的顶点，如果不是，则退出循环并返回M-1。

示例 #1: [(-2,2), (2,2), (-2,-2), (-1,1)]

结果: 3 (因为前三个点形成了一个三角形，但添加P₃ = (-1,1)会使多边形变为非凸形)

示例 #2: [(-2,2), (2,2), (-2,-2), (1,-1)]

结果: 4 (因为可以从数组中的所有4个点构建一个凸四边形)

更新 示例 #3: [(-3,3), (3,3), (2,-1), (-3,-3), (3,-3), (-2,1)]
结果: 4.

这个例子说明仅仅取所有提供的点的凸包并找到一个前缀是它的子集是不够的。因为如果将(3,-3)加入其中，则前面的点(2,-1)就不在凸包上了。但必须拒绝(3,-3)，即使它位于所有六个点的凸包上，而(2,-1)则不在凸包上。

无效输入示例：

• [(-1,-1), (0,0)]（点数太少）
• [(-1,-1), (0,0), (1,1), (1, -1)]（前三个点共线：我不认为算法能够处理这种情况。）

- finnw

---

这与传统的凸包有何不同？我们想要具有最多顶点的凸包吗？ - biziclop

@biziclop，是的，我希望获得具有最大顶点数量的凸包。而且我希望可以比计算每个可能大小的凸包更有效地完成。 - finnw

正如biziclop所提到的：这只是找到一组点的凸包的问题。位于该凸包边缘上的点的数量就是您的大小。因此，使用Graham扫描或Quick-Hull算法的时间复杂度为O（n * log（n））。或者我漏掉了什么？ - Bart Kiers

@Bart Kiers，不完全正确。我只对作为数组前缀的外壳感兴趣。当我看到一个不能成为外壳一部分的点时，我必须停止扫描该数组。即使后续点可以成为（不同的）外壳的一部分，也必须被忽略。 - finnw

@Bart Kiers，我已经添加了第三个示例来说明这一点。 - finnw

Answer 1

我认为你需要增量凸包算法。以下是一些链接：

• http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/incrementCH.htm
• http://ww3.algorithmdesign.net/handouts/IncrementalHull.pdf
• http://www.fandm.edu/computer-science/professors-emeriti/anderson/jay-martin-anderson/research-and-development/portal-algorithm-visualization-in-computational-geometry/convex-hull-an-incremental-algorithm

- Raph Levien

Answer 2

您可以在O(m lg m)的时间内完成此操作。

• 将上凸壳和下凸壳点存储在以X坐标为关键字的搜索树中。
• 当一个新点到达时，找到覆盖其X值的上下线段（搜索树）。
• 如果新点位于两条线之间，则不在凸壳上。放弃。
• 否则，将点插入到上或下凸壳中（哪个更接近线段就放到哪个凸壳中）。
• 如果插入点使相邻点成为内部角，则它们不在凸壳上。放弃。
• 处理像新的最左点、垂直点等边缘情况。
• 继续处理所需数量的点。

- Craig Gidney

---

当你的回答出现时，我正在发布大致相同的回复。 - oosterwal

Answer 3

这个问题有一个非常简单的O(m log m)解决方案。

假设至少有3个点，且前3个点不共线：

1. 在前三个点组成的三角形中找到一个点P。 2. 按照相对于P的角度（逆时针）对这三个点进行排序。（排序后的列表将是凸包） 3. 当我们没有到达列表末尾时，找到下一个点在排序后的列表中的位置。 4. 如果插入该点会使多边形变为凹形，则跳转到步骤6。（这可以通过检查新的相邻两个拐点和当前拐点来检查） 5. 插入该点并跳转到步骤3。 6. 完成。

这里需要处理的主要特殊情况是插入点在列表的一端，因为列表实际上是循环的。一种简单的处理方法是对于每个点，在其角度处插入它以及其角度+-2pi。

- Chris Hopman

Answer 4

如果尝试一种二分搜索会怎样呢？每次整个前缀形成一个凸多边形时，将前缀的大小加倍。每次失败时，将前缀的大小缩小到当前大小和上一次大小之间的一半。

- mbeckish