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

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)]（前三点是共线的：我不希望算法能够处理这个问题。）

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-增量算法

Answer 2

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

• 将上壳点和下壳点存储在以 X 坐标为键的搜索树中。
• 当一个新点到达时，找到覆盖其 X 值的上下线段（搜索树）。
• 如果新点位于两条线之间，则它不在船体上。放弃。
• 否则，将该点插入上壳或下壳（以具有较近线段的为准）。
• 如果插入点将相邻点变成内角，那么它们不在船体上。放弃。
• 处理边缘情况，如新的最左边点、垂直点等。
• 继续，直到处理所需的点数。

Answer 3

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

鉴于至少有 3 个点且前 3 个点不共线：

1. 在前 3 个点的三角形中找到一个点 P。

2. 按相对于 P 的角度（逆时针）对 3 个点进行排序。（这个排序列表将是凸包）

3. 虽然我们不在列表的末尾，但在排序列表中找到下一个点的位置。

4. 如果插入点会使多边形凹入，转到6。（这可以通过检查新的相邻两圈和当前圈来检查）

5. 插入点并转到 3。

6. 完毕。

您必须在此处处理的主要边缘情况是当插入位于列表的末端之一时，因为列表实际上是圆形的。处理此问题的一种简单方法是在每个点以它的角度和角度插入它 +- 2pi。

Answer 4

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