4.2 凸包算法
(Hull Algorithms)

构建三维凸包的算法比二维算法复杂得多，因此本章的覆盖范围会有所侧重。我们将简单提一下包装礼物算法Gift Wrapping，然后从总体上概述分治算法Divide and Conquer。 本章的主体部分将深入详尽地探讨增量算法Incremental Algorithm。4.5 节将介绍该增量算法的随机化版本。

4.2.1 包装礼物算法(Gift Wrapping)

如前所述，包装礼物算法就是为了在任意维度上运行而被发明出来(Chand & Kapur 1970)。其三维版本是二维算法的直接推广。在算法的每一步中，都会构建出凸包的一个连通部分。 首先，从该部分凸包的边界上选择一个面 \(F\)，并选取该面上的一条边 \(e\)，这条边的另一个相邻面尚待确定。 接着，绕着边 \(e\) 将包含面 \(F\) 的平面 \(\pi\) 向点集方向"弯曲bent"，直到遇到第一个点 \(p\)。 如此 \(\text{conv}{p, e}\) 构成了凸包的一个新三角形面，包装可以继续进行。 与二维情况一样，\(p\) 可以通过相对于 \(\pi\) 的最小转角来表征。通过精心设计，该算法可以达到 \(O(n^2)\) 的时间复杂度。 每个面需要 \(O(n)\) 的工作量，正如我们在定理 4.1.1 中看到的，面的数量为 \(O(n)\)。与二维情况类似，该算法的优势在于，它是输出大小敏感的，对于具有 \(F\) 个面的凸包， 其值为时间复杂度为 \(O(nF)\)。

4.2.2 分治算法(Divide and Conquer)

目前已知三维凸包算法的下界与二维的情况一样，都是 \(\Omega(n \log n)\) 的，参见3.6 节。 那么我们自然会问，在三维空间中能否像二维空间那样达到这一复杂度？我们在前一章中提到，尽管有几种二维算法可以推广到三维， 但只有 Preparata & Hong (1977) 提出的分治算法可以达到最优的时间复杂度 \(O(n \log n)\)。该算法不仅在理论上具有重要意义，而且设计十分优美。 但是很难实现，因此在实际应用中，其使用频率不如其他渐近速度较慢的算法，例如增量算法(见 4.2.4 节)， 或者那些仅能保证期望复杂度为 \(O(n \log n)\) 的算法(见 4.5 节)。 在本节中，我将介绍该算法的上层设计，不会深度实现细节。若需更详尽的内容，可参阅 Preparata & Shamos (1985)、Edelsbrunner (1987)、Day (1990) 的著作。

其套路与二维情况相同。首先按 \(x\) 坐标对点进行排序，将其划分为两个集合，递归地构建每一半的凸包，最后进行合并。 为了达到预期的 \(O(n \log n)\) 时间复杂度，合并操作必须在 \(O(n)\) 时间内完成。所有的工作量都集中在合并阶段，因此我们将仅专注于这一部分。

设 \(A\) 和 \(B\) 为待合并的两个凸包。\(A \cup B\) 的凸包将增加一个"带状band"分布的面集合，如图 4.5(b) 所示，其拓扑结构类似于一个没有端盖的圆柱体。 这些面的数量与两个多胞体(polytopes)的大小呈线性关系，因为每个新面至少使用了 \(A\) 或 \(B\) 中的一条边，所以面的总数不会超过边的总数。 因此，在平均情况下，只要能在常数时间内添加每个面，那么在线性时间内完成合并就是可行的。

设 \(\pi\) 为一个从下方支撑 \(A\) 和 \(B\) 的平面，它分别与 \(A\) 相切于顶点 \(a\)，与 \(B\) 相切于顶点 \(b\)。为了简化阐述，假设 \(a\) 和 \(b\) 是唯一的接触点。 此时，\(\pi\) 包含了由 \(ab\) 确定的直线 \(L\)。现在，沿直线 \(L\) 折叠crease该平面，绕 \(L\) 旋转另外半个平面，直到它撞上两个多胞形中的某一个，如图 4.6 所示。 我们会观察到一个关键的结果，如果它首先撞上了多胞形 \(A\) 上的点 \(c\)，那么 \(ac\) 必然是 \(A\) 的一条边。 换句话说，平面 \(\pi\) 撞到的第一个点 \(c\) 必须是 \(a\) 或 \(b\) 的邻接顶点。这一性质将确定下一个碰撞点所需检查的顶点范围限制在了极小的集合内。 我们用一个引理来凸显这一重要事实，但在此不予证明。

一旦平面 \(\pi\) 撞上点 \(c\)，就确定了合并带（merging band）中的一个三角形面 \((a, b, c)\)。 接下来重复此过程，只是需要绕着通过 \(cb\) 的直线旋转，如果 \(c \in A\) 的话。当包裹过程首尾相接形成闭环时，停止操作。

因此，我们需要证明的是，在平均情况下，可以在常数时间内找到点 \(c\)，从而确保整个合并带的构建成本是线性的。

首先，让我们考察一种对所有 \(a,b\) 的相邻顶点进行朴素搜索的方法。我们可以将任何候选点 \(c\) 的"角度angle"定义为，平面 \(\pi\) 从初始位置绕 \(ab\) 旋转击中 \(c\) 所需转过的角度。 设 \(\alpha\) 为与 \(a\) 相邻且角度最小的顶点，称之为"A-winner"，设 \(\beta\) 为与 \(b\) 相邻且角度最小的顶点，称之为"B-winner"。最终 \(c\) 就是 \(\alpha\) 和 \(\beta\) 中角度较小的那个。 显然，找到 \(c\) 所需的时间与 \(a\) 和 \(b\) 的邻点数量成正比。

这里存在两个困难。其一，寻找一个winner可能需要检查 \(\Omega(n)\) 个候选顶点，因为 \(a\) 或 \(b\) 可能拥有许多邻点。 用一圈平面完全包裹 \(A\) 和 \(B\)，可能需要进行 \(\Omega(n)\) 次胜者计算，从而导致合并时间达到平方级 \(O(n^2)\)。 虽然我们无法回避，寻找单个胜者可能耗时 \(\Omega(n)\)这一事实。但这并不像乍看之下那么糟糕，因为我们只需要在所有针对一次合并步骤的胜者计算中， 保证平均每个胜者耗时为常数(即分摊成本为常数)就行。我们将看到，这确实是可以做到的。

第二个困难是，如果 \(\alpha\) 是胜者，那么寻找 \(\beta\) 所做的工作可能就白费了。 想象这样一种情况，来自 \(A\) 的候选点连续多次获胜，导致 \(b\) 保持固定不动。假设此外 \(b\) 还有许多邻居。 那么，如果我们每次都丢弃那些产生败者 \(\beta\) 的搜索结果，并在每次选出 \(A\) 胜者时重新进行搜索，我们再次会陷入平方级的合并时间。

幸运的是，得益于以下单调性性质monotonicity property，这种重复搜索是可以避免的。设 \(\alpha_i\) 和 \(\beta_i\) 分别为第 \(i\) 次迭代中的 A-winner 和 B-winner。 当然，若交换 \(A\) 和 \(B\) 的角色，也有一对称的结论成立。

所谓的单调性是指，每一次迭代，要么直接产生了最终的胜者，在这种情况下，其计算工作无需重复。要么使得旋转轴围绕某个顶点向前推进了一步，而这种推进是不可逆的，无需回退并重新探索。 因此，如果我们把计算成本分摊到被检查的边上，那么每条边最多只会被计费两次(分别从其两个端点各一次)。由此可见，合并过程可以在线性时间内完成。

消除隐藏面(Discarding Hidden Faces)

用一圈构成圆柱状的面包裹住 \(A\) 和 \(B\) 之后，合并过程的最后一步就是剔除被这些包裹平面所遮挡住的面。不幸的是，包裹过程本身并不能直接告诉我们从 \(B\) 的哪些点出发可以看到 \(A\) 的哪些面， 反之亦然，恰恰是这些面需要被删除。不过，包裹过程确实发现了所有"阴影边界shadow boundary edges"，即那些被包裹面所触碰到的 \(A\) 和 \(B\) 的边，如在图 4.5(b) 中深色的部分。 如果把 \(B\) 想象成一个光源，那么 \(A\) 上的阴影边界就标记了明暗的分界线。对称地，当 \(A\) 发光时，\(B\) 上的阴影边界也分隔了光明与黑暗。 直觉上，人们可能会想象着，沿着这些边"剪开snipping"，从而将 \(A\) 和 \(B\) 中被隐藏的"顶盖"部分分离出去。

我曾实现了这一过程，但它偶尔会因为一些令我费解的原因而失败。直到 Edelsbrunner(1987, p. 175) 仔细审查了该算法后，其中的缺陷才变得显而易见。与直觉相反， \(A\) 上的阴影边界边并不一定构成 \(A\) 上的一个简单环(simple cycle)。对于 \(B\) 亦是如此！如图 4.7 所示。图 4.7(a) 中显示了合并前的两个多胞形， \(A\) 是一个扁平的楔形体，在 \(y\) 维度上延伸 10 个单位。\(B\) 是一个高瘦的长方体，在 \(y\) 维度上有 6 个单位。它们顶点的坐标列于表 4.3 和表 4.4 中。

图 4.7(b) 中显示了凸包 \(\text{conv}\{A \cup B\}\)。阴影边界上的 \(A\) 的顶点按顺序 \((0, 2, 4, 0, 1, 3, 5, 1)\) 出现，在图中以深色绘制。形成了图 4.8 所示的拓扑结构"杠铃barbell"。 注意，这个序列两次经过了 \(P_0\) 和 \(P_1\)，因此它并不是一个简单的环。

尽管存在这一意想不到的复杂情况，但隐藏的面确实构成了一个连通的"顶盖connected cap"(参见练习 4.2.3[3])，并且从阴影边界开始，通过深度优先(DFS)等简单的搜索方法就可以找到它们。

我的讨论可能有些散漫，但我希望它能传达出该算法的微妙之处与美感。考虑到构建三维凸包这一任务的复杂性，竟然存在一个 \(O(n \log n)\) 的算法，这让我感到惊喜不已。

4.2.3 练习(Exercises)

1. 制胜角度Winning angle。详细说明 A-winner 的计算过程。假设你已知顶点 \(a\) 和 \(b\)，并且你可以访问 \(A\) 上所有与 \(a\) 相邻的顶点，它们已经按照绕 \(a\) 的逆时针排序。
2. 退化情况Degeneracies。讨论当点不处于一般位置时，分治算法可能面临的困难。例如存在多于两个共线点，或多于三个共面点的情况。
3. 被删除的面Deleted faces。证明在合并过程中从 \(A\) 删除的那些面构成一个连通集合。
4. 阴影边界的拓扑结构Topology of shadow boundary(Michael Goodrich)。 构造两个多胞体 \(A\) 和 \(B\)，使得在 \(\text{conv}\{A \cup B\}\) 中，\(A\) 上的阴影边界具有图 4.9 所示的拓扑结构。

4.2.4 增量算法(Incremental Algorithm)

三维增量算法整体上与二维的(见3.7 节)一样，在第 \(i\) 次迭代中， 计算 \(H_i \leftarrow \text{conv}(H_{i-1} \cup p_i)\)。同样地，其构造凸包的迭代过程有两种情况。令 \(p = p_i, Q = H_{i-1}\)。 首先判断 \(p\) 是否属于 \(Q\)。如果是，则丢弃 \(p\)。如果不是，则计算以 \(p\) 为顶点与 \(Q\) 相切的锥体，并构造新的凸包。

判定 \(p \in Q\) 的方法与二维情形类似。当且仅当 \(p\) 位于由 \(Q\) 的每个面所确定的平面的"正侧"时，\(p\) 才在 \(Q\) 内部。 基于四面体体积的"left-of-triangle"的测试，对应于二维中基于三角形面积的"left-of-segment"。按我们的约定，如果所有面的方向都一致，其体积应为正值， 那么所有这些体积必须具有相同的符号，即均为正。显然，这一测试所需时间与 \(Q\) 的面数成正比，而如前所述，这个数量是 \(O(n)\)。

当 \(p\) 在 \(Q\) 外部时，问题就会变得复杂，因为需要修改凸包。回顾二维增量算法， 此时需要找到从 \(p\) 到 \(Q\) 的两条切线(见图3.10)。 而在三维空间中，对应的是切平面tengent plances而非切线tengent lines。这些切平面围成一个由三角形面组成的锥体cone， 其中每个三角形面的顶点都是 \(p\)，底边则是 \(Q\) 上的一条边 \(e\)。图4.10 和图4.11 分别从两个视角显示了 \(H_{i-1}\) 和 \(H_i\)。接下来我们将讨论如何构造这些锥体面。

想象你站在点 \(p\) 处面向多面体 \(Q\)。我们暂时假设没有任何面是"侧视edge-on"，即视线与面平行的。那么从 \(p\) 看过去，\(Q\) 的每个面的内部有些是可见的，有些不是。 显然，那些可见的面正是从 \(Q = H_{i-1}\) 更新到 \(H_i\) 时需要被剔除的面。此外，可见区域边界上的边，恰恰就是那些将成为以 \(p\) 为顶点的锥体面底边的边。 假设 \(e\) 是 \(Q\) 的一条边，且 \(e\) 和 \(p\) 所确定的平面与 \(Q\) 相切。这条边 \(e\) 邻接两个面，其中一个从 \(p\) 可见，另一个不可见。因此，\(e\) 必然位于可见区域的边界上。 另一种等价的理解方式是，把光源放在点 \(p\) 处。此时，可见区域就是 \(Q\) 中被照亮的部分，而边界边则是明暗区域之间的分界线 —— 这与 4.2.2 节中讨论的"阴影边界"完全类似。

从上述讨论可以看出，如果我们能判断 \(Q\) 的哪些面从 \(p\) 可见,哪些不可见，我们就可以找到所有边界边，从而构造出锥体，并知道该删除哪些面。现在我们需要一个关于"可见性"的精确定义。

一个面 \(f\) 从 \(p\) 可见，当且仅当存在某个位于 \(f\) 内部的点 \(x\)，使得线段 \(px\) 除了端点 \(x\) 外不与 \(Q\) 相交，即 \( px \cap Q = \{x\} \)。 注意在此定义下，如果只能看到某条边，而非面的内部，则该面仍被视为不可见。因此，"侧视"的面也被认为不可见。 从 \(p\) 点是否可见一个三角形面 \((a, b, c)\)，可以通过计算四面体 \((a, b, c, p)\) 的有符号体积signed volume来判断。 当且仅当该体积严格为负时，该面可见。这个符号约定将在 4.3.2 节中详细讨论。

基于上述可见性定义，我们可以概述算法流程，参见算法 4.1。其中，许多细节尚待解释，但算法的基本框架已经很清晰了。

复杂度分析(Complexity Analysis)

回顾定理 4.1.1，设 \(n\) 为多胞形的顶点数，其面数 \(F = O(n)\)，边数 \(E = O(n)\)。 因此，遍历所有面和边的循环都是线性的。由于这些循环嵌套在一个执行 \(n\) 次的外层循环中，总的时间复杂度为 \(O(n^2)\)。