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

Question

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

为了清楚起见，这里有一个非常简单的例子。假设我们在二维空间中有 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) 中使用 Graham 扫描找到最小边界框。 还有其他算法可以在 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 个顶点的凸包和一个查询点，测试查询点是否位于包上。从船体，通过平均三个顶点来计算内部的一个点。称此点为原点。将平面分成楔形，这些楔形由从原点通过船体顶点的光线界定。使用带方向测试的二分搜索来确定查询点属于哪个楔形。测试它是否位于该楔形的船体段上。

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