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

Question

相关:Polygon Decomposition - Removing Concave Points to Form Convex Polygons

我正在寻找一种算法来执行以下操作:

输入是一个二维点数组(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

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

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

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

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

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

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

5. 插入点并转到 3。

6. 完成。

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