algorithm - 在小于 O(n^2) 的时间内找到 "complete"凸包

Question

我在谷歌上搜索这个问题并不是很成功，因为大多数凸包讨论都假设你想要一个最小的边界框，并且对于如何将这个最小的外壳边界填充为“完整”的外壳非常模糊。这里的“完整”仅仅意味着位于最小凸包边缘上的任何点都被添加到凸包中。

为了清楚起见，这里有一个非常简单的示例。假设 2D 空间中有 n=9 个顶点。为了简单起见，我将把它们索引为 0 到 8。

[0] = (0; 0)
[1] = (0; 1)
[2] = (0; 2)
[3] = (1; 0)
[4] = (1; 1)
[5] = (1; 2)
[6] = (2; 0)
[7] = (2; 1)
[8] = (2; 2)

我们可以用格雷厄姆扫描在 O(nlogn) 中找到最小边界框。 还有其他算法可以在 O(nlogh) 中完成此任务，但让我们先简单点。最小的外壳是 [0, 2, 6, 8] (或 [0, 8, 6 , 2]；这并不重要)。 “完整”外壳将是除 [4] 之外的所有顶点。我应该如何对最小外壳进行后处理以实现“完整”外壳而不将复杂性增加到 O(n^2)？

显然，更改 GS 算法以包含共线点(>0 到 >=0 或 <0 到 <= 0)是行不通的。我必须使用其他算法吗？

哦，还有一件事:对于这个问题，请假设 h ~= n，这样 O(n * h) 实际上就是 O(n^2)。

---

因为人们拒绝相信我提供的示例会导致 GS 在将顶点乘积比较更改为包含零时失败。下面是反例的解释:

1. 通过任何方式找到一个角点(如果你按照wiki所说的那样做，这并不重要，即最低的Y，然后是最低的X，或者先最低的X，然后最低的Y，或者倒置顺序)

2. 向凸包添加角

3. 按极角对剩余点进行排序(再次强调，无论是在 Ox 轴还是 Oy 轴上完成，只要正确调整所有操作即可)

这些点对将具有相等的极角:[1, 2]、[3, 6]、[4, 8]。如果你允许它们任意排列，这肯定会杀死 GS，因为你可能会尝试 0 6 3 7，之后 GS 将从凸包中永久删除 3 作为无效顶点(同样适用于 [ 1, 2] 对)。

正如我所见，典型的极角相等决胜局是根据它们与角点的距离对它们进行排序。但是，如果您决定先订购距离较远的点，则 GS 将必须采用 0 6 3 7，这将 3 标记为非船体点。 另一方面，如果您对距离角点更近的点进行排序，您将采用 [...] 5 1 2 0，这将导致 GS 将 2 标记为非船体点。

问题是，我们能否通过精心设计的极角排序策略或后处理来解决这个问题。

Answer 1

这是一个 O(log h) 时间算法，给定一个具有按排序顺序排列的 h 个顶点的凸包和一个查询点，测试查询点是否位于该凸包上。从船体开始，通过计算其三个顶点的平均值来计算内部的一个点。将此点称为原点。将平面划分为由从原点穿过外壳顶点的射线界定的楔形。使用二分搜索和方向测试来确定查询点属于哪个楔形。测试它是否位于该楔子的船体部分上。

如果您已经实现了格雷厄姆扫描，那么只需更改测试即可保留共线点，但您需要确定相对于与其他两个船体点不共线的原点的角度。这样的点可以通过取三个不共线的输入点的平均值来获得。