凸包（Convex Hull）是计算几何中最经典的问题之一。给定平面上的一组点，求能包含所有点的最小凸多边形——这个看似简单的问题，催生了近半个世纪的算法演化。从 1972 年 Graham 的极角排序扫描，到 1979 年 Andrew 的单调链方法，再到 1996 年 Chan 的 output-sensitive 最优算法，每一步都展现了算法设计思维的精妙之处。
本文将系统梳理这条进化路线，配合完整的 C 语言实现，深入分析每种算法的设计动机、正确性证明和工程陷阱。
一、凸包的定义与基本性质
1.1 什么是凸包
定义：给定平面上的点集 S = {p1, p2, …, pn}，S 的凸包 CH(S) 是包含 S 中所有点的最小凸集。等价地，它是包含所有点的面积最小的凸多边形。
直观理解：想象在木板上钉一组钉子，然后用橡皮筋套住所有钉子——橡皮筋收紧后的形状就是凸包。
数学定义：CH(S) = {sum(λi * pi) | λi >= 0, sum(λi) = 1}，即所有点的凸组合的集合。
1.2 凸包的基本性质
性质一：凸包的顶点一定是原点集的子集。即 CH(S) 的每个顶点都属于 S。
性质二：凸包顶点数 h 满足 3 <= h <= n（退化情况除外）。当 n 个点的分布”随机”时，h 的期望值远小于 n。
性质三（Euler 公式的二维特化）：凸包是一个简单多边形，顶点数等于边数。
性质四（下界）：在基于比较的计算模型下，二维凸包的计算下界为 Omega(n log n)。这一下界可以通过归约排序问题来证明：给定 n 个实数 x1, x2, …, xn，构造点集 {(xi, xi^2)}，这些点全部在抛物线上，其凸包顶点的顺序就是排序后的顺序。
性质五（output-sensitive 下界）：如果凸包有 h 个顶点，计算下界为 Omega(n log h)。这意味着当 h 很小时，我们有机会比 O(n log n) 更快。
1.3 退化情况
在实际实现中，退化情况往往是 bug 的温床：
- 所有点共线：凸包退化为线段。
- 存在重复点：需要决定是否保留。
- 三点共线：凸包边上的中间点是否算作顶点？不同算法的约定可能不同。
- 只有一个或两个点：凸包分别退化为点和线段。
// 判断三点是否共线
// 返回值: 0 表示共线，正值表示逆时针，负值表示顺时针
long long cross(Point O, Point A, Point B) {
return (long long)(A.x - O.x) * (B.y - O.y)
- (long long)(A.y - O.y) * (B.x - O.x);
}二、叉积：凸包算法的核心工具
2.1 叉积的定义
二维向量叉积（严格来说是伪叉积，或外积的 z 分量）定义为：
cross(u, v) = ux * vy - uy * vx对于三个点 A、B、C：
cross(AB, AC) = (Bx - Ax)(Cy - Ay) - (By - Ay)(Cx - Ax)2.2 叉积的几何意义
- cross > 0：A → B → C 构成逆时针转向（左转）。
- cross < 0：A → B → C 构成顺时针转向（右转）。
- cross = 0：A、B、C 三点共线。
叉积的绝对值等于以 AB 和 AC 为邻边的平行四边形面积，其符号反映了有向面积的方向。
2.3 叉积在凸包中的角色
凸包的核心判断就是”转向测试”：沿凸包边界行走时，每一步都应该向同一个方向转弯。对于逆时针排列的凸包，每次转弯都是左转，即叉积始终为正。
这就是所有基于栈的凸包算法的核心不变量：栈中相邻三点始终构成左转关系。
typedef struct {
int x, y;
} Point;
// 转向判断
// 返回正值: 左转（逆时针）
// 返回负值: 右转（顺时针）
// 返回零: 共线
long long orientation(Point p, Point q, Point r) {
return (long long)(q.x - p.x) * (r.y - p.y)
- (long long)(q.y - p.y) * (r.x - p.x);
}三、Graham Scan（1972）
3.1 算法思想
Graham Scan 是第一个 O(n log n) 的凸包算法，由 Ronald Graham 于 1972 年提出。算法的核心思想极为优雅：
- 选取一个一定在凸包上的”锚点”（通常取 y 坐标最小的点）。
- 将其余所有点按相对于锚点的极角排序。
- 按极角顺序依次遍历每个点，用一个栈维护”当前已确认的凸包部分”。
- 每加入一个新点时，检查栈顶的三个点是否构成左转：若不是，则弹出栈顶，反复检查直到满足左转条件。
3.2 极角排序
极角排序是 Graham Scan 的第一个关键步骤。给定锚点 P0，对于其他两个点 Pi 和 Pj，我们需要判断 Pi 的极角是否小于 Pj 的极角。
用叉积来实现极角比较，可以避免使用 atan2 函数（浮点不精确且速度慢）：
Point pivot; // 全局锚点
int polar_cmp(const void *a, const void *b) {
Point *pa = (Point *)a;
Point *pb = (Point *)b;
long long v = cross(pivot, *pa, *pb);
if (v != 0) return (v > 0) ? -1 : 1; // 极角小的排前面
// 共线时按距离排序（近的排前面）
long long da = (long long)(pa->x - pivot.x) * (pa->x - pivot.x)
+ (long long)(pa->y - pivot.y) * (pa->y - pivot.y);
long long db = (long long)(pb->x - pivot.x) * (pb->x - pivot.x)
+ (long long)(pb->y - pivot.y) * (pb->y - pivot.y);
return (da < db) ? -1 : (da > db) ? 1 : 0;
}3.3 扫描过程
排序完成后，按顺序遍历每个点并维护栈：
// Graham Scan 主函数
// 返回凸包顶点数，结果存在 hull[] 中
int graham_scan(Point pts[], int n, Point hull[]) {
if (n < 3) {
for (int i = 0; i < n; i++) hull[i] = pts[i];
return n;
}
// Step 1: 找到最低点（y 最小，相同取 x 最小）
int lowest = 0;
for (int i = 1; i < n; i++) {
if (pts[i].y < pts[lowest].y ||
(pts[i].y == pts[lowest].y && pts[i].x < pts[lowest].x)) {
lowest = i;
}
}
// 将最低点放到 pts[0]
Point temp = pts[0];
pts[0] = pts[lowest];
pts[lowest] = temp;
// Step 2: 极角排序
pivot = pts[0];
qsort(pts + 1, n - 1, sizeof(Point), polar_cmp);
// 处理与最远点共线的情况
// 最后一组共线的点应按距离从远到近排列
int last = n - 1;
while (last > 0 && cross(pts[0], pts[last], pts[last - 1]) == 0) {
last--;
}
// 反转 [last+1, n-1] 区间
for (int i = last + 1, j = n - 1; i < j; i++, j--) {
temp = pts[i];
pts[i] = pts[j];
pts[j] = temp;
}
// Step 3: 栈扫描
int top = 0;
hull[top++] = pts[0];
hull[top++] = pts[1];
hull[top++] = pts[2];
for (int i = 3; i < n; i++) {
// 弹出不满足左转条件的栈顶
while (top > 1 && cross(hull[top - 2], hull[top - 1], pts[i]) <= 0) {
top--;
}
hull[top++] = pts[i];
}
return top;
}3.4 正确性证明
不变量：在处理第 i 个点之前，栈中的点构成点集 {P0, P1, …, Pi-1} 的上凸包（沿极角方向的凸包部分）。
归纳证明： - 基础：栈中只有 P0，显然成立。 - 归纳步：假设处理 Pi 之前不变量成立。当 Pi 加入时： - 若栈顶两点与 Pi 构成左转，直接压入，不变量仍成立。 - 若构成右转或共线，弹出栈顶。弹出后重新检查，直到满足左转条件。弹出的点一定在新凸包的内部或边上，因为 Pi 的极角更大且形成了右转。
3.5 复杂度分析
- 排序：O(n log n)。
- 栈扫描：每个点最多入栈一次、出栈一次，总共 O(n)。
- 总复杂度：O(n log n)。
空间复杂度 O(n)，用于存储排序后的数组和栈。
3.6 Graham Scan 的陷阱
实践中 Graham Scan 最常见的错误来源：
共线点处理不当：当多个点与锚点共线时，排序规则必须特殊处理。特别是”最后一批”共线点的顺序需要反转，否则无法正确闭合凸包。
极角排序的分象限问题：使用 atan2 做极角排序会遇到浮点精度问题；纯叉积比较则需要正确处理零向量（点与锚点重合）的情况。
栈初始化：如果排序后头两个点就与锚点共线，栈的初始化可能出问题。
四、Andrew’s Monotone Chain（1979）
4.1 动机
Graham Scan 的极角排序需要选取锚点，且共线点的处理较为复杂。Andrew 在 1979 年提出了一种更简洁的方法：按坐标排序，分别构建上凸包和下凸包。
4.2 算法描述
- 将所有点按 (x, y) 字典序排序。
- 从左到右扫描，构建下凸包（lower hull）。
- 从右到左扫描，构建上凸包（upper hull）。
- 将上下凸包拼接。
排序用标准的字典序比较，不涉及极角，因此实现更简洁、数值更稳定。
4.3 完整实现
int cmp_xy(const void *a, const void *b) {
Point *pa = (Point *)a;
Point *pb = (Point *)b;
if (pa->x != pb->x) return (pa->x < pb->x) ? -1 : 1;
return (pa->y < pb->y) ? -1 : (pa->y > pb->y) ? 1 : 0;
}
// Andrew's Monotone Chain
// 返回凸包顶点数（逆时针序），结果存在 hull[] 中
// hull[] 需至少 2*n 大小
int andrew_hull(Point pts[], int n, Point hull[]) {
if (n < 3) {
for (int i = 0; i < n; i++) hull[i] = pts[i];
return n;
}
qsort(pts, n, sizeof(Point), cmp_xy);
int k = 0;
// 构建下凸包
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(hull[k - 2], hull[k - 1], pts[i]) <= 0)
k--;
hull[k++] = pts[i];
}
// 构建上凸包
int lower_size = k + 1; // 上凸包起始位置（+1 避免重复终点）
for (int i = n - 2; i >= 0; i--) {
while (k >= lower_size && cross(hull[k - 2], hull[k - 1], pts[i]) <= 0)
k--;
hull[k++] = pts[i];
}
return k - 1; // 最后一个点与第一个点重复
}4.4 为何 Andrew 更受欢迎
在竞赛和工程实践中，Andrew’s Monotone Chain 通常比 Graham Scan 更受青睐，原因如下：
- 排序更简单：字典序排序无需选取锚点，qsort 直接可用。
- 无需特殊处理共线点：下凸包和上凸包的扫描自然地处理了共线情况。
- 数值更稳定：不涉及极角计算，全部操作都是叉积（整数乘法和减法）。
- 代码更短：实现通常比 Graham Scan 短 30% 以上。
4.5 等价性
Andrew 和 Graham 算法具有相同的时间和空间复杂度 O(n log n)。它们的核心思想完全一致——都是通过排序建立遍历顺序，然后用栈维护凸性不变量。区别仅在于排序方式（极角 vs. 坐标）和扫描方式（一次扫描 vs. 上下两次扫描）。
五、Jarvis March（Gift Wrapping）
5.1 算法思想
Jarvis March（也称 Gift Wrapping）是最直观的凸包算法。它模拟”包装礼物”的过程：
- 从一个已知的凸包顶点出发（如最左边的点）。
- 每一步从当前点出发，找到使得所有其他点都在”连线左侧”的下一个点。
- 重复直到回到起点。
5.2 实现
int jarvis_march(Point pts[], int n, Point hull[]) {
if (n < 3) {
for (int i = 0; i < n; i++) hull[i] = pts[i];
return n;
}
// 找最左边的点
int leftmost = 0;
for (int i = 1; i < n; i++) {
if (pts[i].x < pts[leftmost].x ||
(pts[i].x == pts[leftmost].x && pts[i].y < pts[leftmost].y))
leftmost = i;
}
int h = 0;
int p = leftmost;
do {
hull[h++] = pts[p];
int q = (p + 1) % n;
for (int i = 0; i < n; i++) {
long long v = cross(pts[p], pts[q], pts[i]);
if (v > 0) {
q = i; // pts[i] 更"左"
} else if (v == 0) {
// 共线时选更远的点
long long dq = (long long)(pts[q].x - pts[p].x) * (pts[q].x - pts[p].x)
+ (long long)(pts[q].y - pts[p].y) * (pts[q].y - pts[p].y);
long long di = (long long)(pts[i].x - pts[p].x) * (pts[i].x - pts[p].x)
+ (long long)(pts[i].y - pts[p].y) * (pts[i].y - pts[p].y);
if (di > dq) q = i;
}
}
p = q;
} while (p != leftmost);
return h;
}5.3 复杂度分析
- 每找一个凸包顶点需要 O(n) 时间扫描所有点。
- 凸包共有 h 个顶点。
- 总复杂度：O(nh)。
当 h 很小时（如 h = O(log n)），Jarvis March 的 O(n log n) 性能实际上优于 Graham Scan。但当 h = O(n) 时（如所有点都在凸包上），退化为 O(n^2)。
5.4 Output-Sensitive 的概念
Jarvis March 的复杂度依赖于输出大小 h，这就是所谓的 output-sensitive 算法。对于凸包问题，这是一个重要的性质：当大部分点在凸包内部时，我们不应该为”排除”这些点付出太多代价。
但 Jarvis March 的 O(nh) 还不是最优的 output-sensitive 复杂度。最优下界是 O(n log h)，这正是 Chan’s Algorithm 所达到的。
六、Chan’s Algorithm（1996）
6.1 动机与思路
Timothy Chan 在 1996 年提出了一个极其精巧的算法，达到了 O(n log h) 的最优 output-sensitive 复杂度。其核心思路是：
将 Graham Scan 和 Jarvis March 结合起来。
关键洞察： - Graham Scan 处理 m 个点需要 O(m log m) 时间。 - 在预处理了凸包的小组中做 Jarvis 的”找下一点”操作，可以用二分搜索在 O(log m) 时间完成，而不是 O(m)。 - 如果我们将 n 个点分成 n/m 组（每组 m 个），对每组单独求凸包（作为预处理），然后用 Jarvis March 在组间搜索，总复杂度为 O(n log m + nh/… )——但这需要正确设置 m。
6.2 算法描述
输入：n 个点，猜测的凸包大小 H（稍后说明如何猜测）。
步骤：
- 令 m = H。将 n 个点分成 ceil(n/m) 组，每组最多 m 个点。
- 对每组用 Graham Scan（或 Andrew）求凸包。时间 O(m log m) 每组，总共 O(n log m)。
- 用 Jarvis March 的思路寻找整体凸包：
- 从最低点开始。
- 每一步，在每个小组的凸包中二分搜索该组中”最佳的下一个点”。
- 在 ceil(n/m) 个候选中选出全局最佳。
- 重复最多 H 步。
- 如果 H 步内完成了整体凸包，输出结果。否则，报告失败（H 猜小了）。
单步的复杂度：每个小组的二分搜索 O(log m)，共 ceil(n/m) 个组，所以每步 O((n/m) log m)。总共 H 步：O(H * (n/m) * log m)。
当 m = H 时，总复杂度 = O(n log m) + O(n log m) = O(n log H)。
6.3 Repeated Squaring Trick
问题在于：我们事先不知道 h。Chan 的解决方案极为精妙——repeated squaring（反复平方）：
- 依次尝试 H = 2(2t)，即 H = 4, 16, 256, 65536, …
- 对于每个 H，运行上述算法。如果 H >= h，算法成功返回；否则增加 t 再试。
为什么这样仍然是 O(n log h)？
设实际凸包大小为 h。成功的那次迭代（设为第 T 次）有 H = 2(2T) >= h，因此 O(n log H) = O(n log h)（因为 H <= h^2，所以 log H <= 2 log h）。
之前所有失败迭代的总时间：
sum_{t=0}^{T-1} O(n log 2^(2^t)) = sum_{t=0}^{T-1} O(n * 2^t)这是一个几何级数，总和 O(n * 2^T) = O(n log H) = O(n log h)。
因此总复杂度 O(n log h)——最优！
6.4 二分搜索的实现细节
在每个小组的凸包中用二分搜索找”对当前方向最优的点”，这是 Chan’s Algorithm 中最微妙的部分。
对于一个已经按顺序排列的凸包 Q = {q0, q1, …, qm-1}，要找到从外部点 p 看去的”最右切线点”。这可以用如下的二分搜索实现：
// 在凸包 hull[0..size-1] 中找到从点 p 出发
// 相对于方向 prev->p 的下一个凸包点（切线点）
// hull 按逆时针序排列
int tangent_search(Point hull[], int size, Point p, Point prev) {
if (size == 1) return 0;
// 二分搜索切线点
// 寻找使得 cross(prev, p, hull[i]) 方向"最右"的 i
int lo = 0, hi = size;
int best = 0;
// 先检查 hull[0] 是否是候选
long long c0 = cross(prev, p, hull[0]);
for (int i = 1; i < size; i++) {
long long ci = cross(prev, p, hull[i]);
long long cmp = cross(p, hull[best], hull[i]);
if (cmp > 0 || (cmp == 0 && ci < c0)) {
best = i;
}
}
return best;
}注意：上面是 O(m) 的简化版本。真正的 O(log m) 二分搜索需要利用凸包的单调性，实现较为复杂。完整的二分切线搜索如下：
// O(log m) 切线二分搜索
// 在凸包 Q[0..m-1]（逆时针序）中，
// 找到使 cross(from, Q[i], Q[(i+1)%m]) 符号变化的切线点
int binary_tangent(Point Q[], int m, Point from) {
if (m == 1) return 0;
if (m == 2) {
long long c = cross(from, Q[0], Q[1]);
if (c < 0) return 1;
if (c > 0) return 0;
// 共线取较远的
return 0;
}
// 定义: up(i) = cross(from, Q[i], Q[(i+1)%m]) >= 0
// 切线点是 up(i-1) && !up(i) 的位置
int a = 0, b = m;
int a_up = (cross(from, Q[0], Q[1 % m]) >= 0);
while (b - a > 1) {
int mid = (a + b) / 2;
int mid_up = (cross(from, Q[mid], Q[(mid + 1) % m]) >= 0);
int a_to_mid = (cross(from, Q[a], Q[mid]) > 0);
if (!a_up && mid_up) {
b = mid;
} else if (a_up && !mid_up) {
a = mid;
a_up = mid_up;
} else if (a_up && mid_up) {
if (a_to_mid) a = mid, a_up = mid_up;
else b = mid;
} else {
if (!a_to_mid) a = mid, a_up = mid_up;
else b = mid;
}
}
return a;
}6.5 Chan’s Algorithm 完整实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int x, y;
} Point;
static long long cross3(Point O, Point A, Point B) {
return (long long)(A.x - O.x) * (B.y - O.y)
- (long long)(A.y - O.y) * (B.x - O.x);
}
static int cmp_point(const void *a, const void *b) {
const Point *pa = (const Point *)a;
const Point *pb = (const Point *)b;
if (pa->x != pb->x) return (pa->x < pb->x) ? -1 : 1;
return (pa->y < pb->y) ? -1 : (pa->y > pb->y) ? 1 : 0;
}
// Andrew's Monotone Chain for a small group
static int small_hull(Point pts[], int n, Point hull[]) {
if (n <= 1) {
if (n == 1) hull[0] = pts[0];
return n;
}
qsort(pts, n, sizeof(Point), cmp_point);
int k = 0;
for (int i = 0; i < n; i++) {
while (k >= 2 && cross3(hull[k-2], hull[k-1], pts[i]) <= 0) k--;
hull[k++] = pts[i];
}
int lower = k + 1;
for (int i = n - 2; i >= 0; i--) {
while (k >= lower && cross3(hull[k-2], hull[k-1], pts[i]) <= 0) k--;
hull[k++] = pts[i];
}
return k - 1;
}
// 在凸包中找到关于给定方向的切线点（简化版 O(m)）
static int find_tangent(Point hull[], int size, Point from, Point dir) {
int best = 0;
for (int i = 1; i < size; i++) {
long long c = cross3(from, hull[best], hull[i]);
if (c > 0) {
best = i;
} else if (c == 0) {
long long db = (long long)(hull[best].x - from.x) * (hull[best].x - from.x)
+ (long long)(hull[best].y - from.y) * (hull[best].y - from.y);
long long di = (long long)(hull[i].x - from.x) * (hull[i].x - from.x)
+ (long long)(hull[i].y - from.y) * (hull[i].y - from.y);
if (di > db) best = i;
}
}
return best;
}
// Chan's Algorithm
// 返回凸包顶点数，结果存在 result[] 中
int chan_hull(Point pts[], int n, Point result[]) {
if (n < 3) {
for (int i = 0; i < n; i++) result[i] = pts[i];
return n;
}
// Repeated squaring: 尝试 H = 2^(2^t)
for (int t = 1; t < 30; t++) {
long long H_val = 1;
for (int i = 0; i < (1 << t); i++) {
H_val *= 2;
if (H_val > n) { H_val = n; break; }
}
int m = (int)H_val; // 每组大小 = 猜测的 h
// 分组并对每组求凸包
int num_groups = (n + m - 1) / m;
// 分配内存
Point **group_hulls = (Point **)malloc(num_groups * sizeof(Point *));
int *group_sizes = (int *)malloc(num_groups * sizeof(int));
Point *buf = (Point *)malloc(n * sizeof(Point));
memcpy(buf, pts, n * sizeof(Point));
for (int g = 0; g < num_groups; g++) {
int start = g * m;
int end = start + m;
if (end > n) end = n;
int cnt = end - start;
group_hulls[g] = (Point *)malloc(2 * cnt * sizeof(Point));
group_sizes[g] = small_hull(buf + start, cnt, group_hulls[g]);
}
// 找全局最低点
int best_group = 0, best_idx = 0;
for (int g = 0; g < num_groups; g++) {
for (int i = 0; i < group_sizes[g]; i++) {
Point *bp = &group_hulls[best_group][best_idx];
Point *cp = &group_hulls[g][i];
if (cp->y < bp->y || (cp->y == bp->y && cp->x < bp->x)) {
best_group = g;
best_idx = i;
}
}
}
Point start_pt = group_hulls[best_group][best_idx];
result[0] = start_pt;
Point current = start_pt;
int h = 1;
int success = 0;
for (int step = 0; step < m; step++) {
// 在每个组中找最佳候选
Point best_next = current;
int found_any = 0;
for (int g = 0; g < num_groups; g++) {
if (group_sizes[g] == 0) continue;
int ti = find_tangent(group_hulls[g], group_sizes[g],
current, current);
Point candidate = group_hulls[g][ti];
if (candidate.x == current.x && candidate.y == current.y)
continue;
if (!found_any) {
best_next = candidate;
found_any = 1;
} else {
long long c = cross3(current, best_next, candidate);
if (c > 0) {
best_next = candidate;
} else if (c == 0) {
long long db = (long long)(best_next.x - current.x) * (best_next.x - current.x)
+ (long long)(best_next.y - current.y) * (best_next.y - current.y);
long long dc = (long long)(candidate.x - current.x) * (candidate.x - current.x)
+ (long long)(candidate.y - current.y) * (candidate.y - current.y);
if (dc > db) best_next = candidate;
}
}
}
if (best_next.x == start_pt.x && best_next.y == start_pt.y) {
success = 1;
break;
}
result[h++] = best_next;
current = best_next;
}
// 清理
for (int g = 0; g < num_groups; g++) free(group_hulls[g]);
free(group_hulls);
free(group_sizes);
free(buf);
if (success) return h;
// 否则 H 猜小了，继续下一轮
}
return 0; // 不应到达这里
}6.6 复杂度总结
| 算法 | 时间复杂度 | 空间复杂度 | Output-Sensitive |
|---|---|---|---|
| Graham Scan | O(n log n) | O(n) | 否 |
| Andrew’s Monotone Chain | O(n log n) | O(n) | 否 |
| Jarvis March | O(nh) | O(h) | 是 |
| Chan’s Algorithm | O(n log h) | O(n) | 是，最优 |
七、三维凸包：增量构造法
7.1 问题定义
三维凸包是二维情况的自然推广：给定三维空间中的点集，求包含所有点的最小凸多面体。输出是一组三角面片（或更一般的凸多边形面片）。
7.2 增量构造法
增量构造法（Incremental Construction）是最常用的三维凸包算法：
- 用前 4 个不共面的点构成初始四面体。
- 依次添加剩余的点。对于每个新点 p：
- 如果 p 在当前凸包内部，跳过。
- 如果 p 在外部，找到从 p 能”看到”的所有面（即 p 在该面的外侧）。
- 删除这些”可见面”，用 p 与可见面的边界（horizon edges）构成新面。
7.3 可见性判断
面 F 对点 p 是否可见，可以通过该面的法向量和 p 到面上一点的向量的点积来判断：
typedef struct {
double x, y, z;
} Point3D;
typedef struct {
int v[3]; // 三个顶点的索引
Point3D normal; // 外法向量
double offset; // 法向量与顶点的点积
} Face;
// 判断点 p 是否在面 f 的外侧
int is_visible(Face *f, Point3D *pts, Point3D p) {
double dot = f->normal.x * p.x + f->normal.y * p.y + f->normal.z * p.z;
return dot > f->offset + 1e-10; // epsilon 容差
}
// 计算面的法向量（通过叉积）
Point3D face_normal(Point3D a, Point3D b, Point3D c) {
Point3D u = {b.x - a.x, b.y - a.y, b.z - a.z};
Point3D v = {c.x - a.x, c.y - a.y, c.z - a.z};
Point3D n;
n.x = u.y * v.z - u.z * v.y;
n.y = u.z * v.x - u.x * v.z;
n.z = u.x * v.y - u.y * v.x;
return n;
}7.4 复杂度
- 随机增量构造：期望时间 O(n log n)，空间 O(n)。
- 最坏情况下凸包面数为 O(n^2)（根据 Upper Bound Theorem，三维凸包最多 O(n) 个面，准确上界为 2n - 4 个三角面）。
7.5 更高维度
| 维度 d | 凸包面数上界 | 最优算法复杂度 |
|---|---|---|
| 2 | n | O(n log n) |
| 3 | 2n - 4 | O(n log n) |
| d >= 4 | O(n^{floor(d/2)}) | 取决于维度 |
高维凸包在机器学习（如支持向量机的对偶问题）和优化领域有重要应用。
八、数值稳健性问题
8.1 浮点精度的陷阱
凸包算法的正确性严重依赖于叉积符号的判断。在浮点运算中，这个判断可能出错：
// 这个叉积"应该"为正，但浮点误差可能使它变为负或零
double cross_float(double ax, double ay, double bx, double by,
double cx, double cy) {
return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}
// 当三点接近共线时，结果可能在 +epsilon 和 -epsilon 之间跳动8.2 典型的错误现象
浮点凸包实现中常见的错误表现：
- 算法不终止：由于叉积符号判断的不一致性，栈的弹入弹出可能形成死循环。
- 结果不是凸的：某些应该弹出的点被保留了，或者不该弹出的点被弹出了。
- 遗漏凸包顶点：接近共线的三个点，中间的点可能被错误地排除。
- 重复顶点：某些点被加入凸包两次。
8.3 解决方案
方案一：使用整数坐标
如果坐标范围允许（例如 |x|, |y| <= 10^9），使用 64 位整数计算叉积，完全避免浮点误差：
// 使用 long long 确保精确计算
// 坐标范围 |x|, |y| <= 10^9 时，叉积最大约 4 * 10^18，
// 在 long long 范围内（约 9.2 * 10^18）
long long cross_exact(Point O, Point A, Point B) {
return (long long)(A.x - O.x) * (B.y - O.y)
- (long long)(A.y - O.y) * (B.x - O.x);
}方案二：epsilon 比较
对于浮点坐标，使用 epsilon 容差：
#define EPS 1e-9
int sign(double x) {
if (x > EPS) return 1;
if (x < -EPS) return -1;
return 0;
}但 epsilon 方法并非银弹：epsilon 太大会合并不该合并的点，太小则不能有效消除误差。
方案三：精确算术库
使用精确浮点算术库（如 Shewchuk 的 robust predicates 或 CGAL 中的精确内核）。这些库通过自适应精度算术实现精确的符号判断：
// Shewchuk 的 orient2d 谓词
// 返回正值表示逆时针，负值表示顺时针，零表示共线
// 使用自适应精度，必要时会使用更多精度位
extern double orient2d(double *pa, double *pb, double *pc);方案四：符号扰动（Symbolic Perturbation）
通过对点坐标添加微小的符号扰动，消除所有退化情况（如三点共线）。这是一种理论上优美的方法，但实现较为复杂。
8.4 实践建议
对于大多数应用场景：
- 竞赛：使用整数坐标 + long long 叉积，干净利落。
- 工程代码：如果坐标是浮点的，优先考虑 Shewchuk predicates。
- 科学计算：使用 CGAL 或类似的计算几何库。
九、凸包的应用
9.1 经典应用
旋转卡壳（Rotating Calipers）：在凸包上运行旋转卡壳算法，可以在 O(h) 时间内求解： - 最远点对（直径问题） - 最小面积/周长外接矩形 - 两个凸包之间的最大/最小距离
碰撞检测：在游戏和物理模拟中，凸包常用于近似复杂形状的碰撞包围体。GJK（Gilbert-Johnson-Keerthi）算法用于判断两个凸体是否相交。
线性规划：二维线性规划的可行域是一个凸多边形，其顶点可以通过凸包相关的方法求出。
9.2 竞赛中的凸包技巧
斜率优化 DP：在动态规划中，当状态转移方程可以写成 f(j) = a(j) * x(i) + b(j) 的形式时，可以将 (a(j), b(j)) 看作直线，用凸包维护最优直线集合。这就是著名的”凸包技巧”（Convex Hull Trick）。
// 凸包技巧的简化版本（斜率递减的情况）
typedef struct {
long long k, b; // 直线 y = kx + b
} Line;
Line stack_lines[200001];
int line_top = 0;
// 判断第三条线是否使第二条线多余
int bad(Line l1, Line l2, Line l3) {
// l1 和 l3 的交点 x 坐标 <= l1 和 l2 的交点 x 坐标
return (__int128)(l3.b - l1.b) * (l2.k - l1.k)
<= (__int128)(l2.b - l1.b) * (l3.k - l1.k);
}
void add_line(long long k, long long b) {
Line l = {k, b};
while (line_top >= 2 &&
bad(stack_lines[line_top - 2], stack_lines[line_top - 1], l)) {
line_top--;
}
stack_lines[line_top++] = l;
}
long long query(long long x) {
// 二分或指针移动查找最优线
int lo = 0, hi = line_top - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (stack_lines[mid].k * x + stack_lines[mid].b <=
stack_lines[mid + 1].k * x + stack_lines[mid + 1].b) {
lo = mid + 1;
} else {
hi = mid;
}
}
return stack_lines[lo].k * x + stack_lines[lo].b;
}9.3 半平面交
半平面交（Half-Plane Intersection）与凸包有密切的对偶关系。在对偶空间中，点变成直线，直线变成点，凸包变成半平面交。这种对偶性使得许多凸包算法可以直接改写为半平面交算法。
十、工程实践中的陷阱
在实际工程中实现凸包算法时，以下表格总结了常见的陷阱：
| 陷阱 | 现象 | 解决方案 |
|---|---|---|
| 整数溢出 | 叉积计算结果溢出 int 范围，判断符号出错 | 使用 long long，或坐标范围超过 10^9 时使用 __int128 |
| 浮点误差 | 接近共线的三点叉积符号不稳定，导致算法不终止或结果错误 | 整数坐标优先；浮点时使用 robust predicates |
| 共线点遗漏 | Graham Scan 中最后一批共线点顺序错误，导致凸包不闭合 | 排序时对最后一组共线点按距离逆序排列 |
| 重复点 | 输入中有重复点，导致零向量参与叉积计算 | 预处理去重，或在算法中跳过相同点 |
| 退化输入 | 所有点共线或只有 1-2 个点 | 在算法开头特殊处理 n < 3 的情况 |
| qsort 不稳定 | C 标准不保证 qsort 稳定，等价元素的顺序不确定 | 在比较函数中加入 tie-breaking 规则 |
| 凸包边上的点 | 需要保留凸包边上的所有点，但标准算法只保留顶点 | 修改叉积判断条件：将 <= 0 改为 < 0 |
| 栈数组越界 | hull 数组分配不够大 | Andrew 算法需要 2n 大小的数组 |
| 极角排序分支 | 不同象限的点直接用叉积比较可能得到错误的极角顺序 | 先按象限分类，同象限内再用叉积比较 |
| 输入修改 | 排序修改了原始数组，但调用者可能还需要原始顺序 | 复制数组后再排序，或记录原始索引 |
| Chan 算法内存 | 分组求凸包需要额外内存分配 | 预分配足够的缓冲区，避免频繁 malloc/free |
| 大规模数据性能 | n 超过 10^6 时排序的常数因子影响显著 | 考虑基数排序或并行化 |
十一、算法对比与选择指南
11.1 理论对比
| 特性 | Graham Scan | Andrew | Jarvis March | Chan |
|---|---|---|---|---|
| 年份 | 1972 | 1979 | 1973 | 1996 |
| 时间复杂度 | O(n log n) | O(n log n) | O(nh) | O(n log h) |
| 空间复杂度 | O(n) | O(n) | O(h) | O(n) |
| Output-sensitive | 否 | 否 | 是 | 是（最优） |
| 排序方式 | 极角排序 | 坐标排序 | 无需排序 | 分组排序 |
| 实现难度 | 中等 | 简单 | 简单 | 较难 |
| 数值稳定性 | 一般 | 好 | 好 | 取决于子算法 |
11.2 实践中的选择
- 竞赛：几乎总是选择 Andrew’s Monotone Chain。代码短、不易出错、适合手写。
- 面试：Graham Scan 更常被考察，因为它更”经典”且更能展示算法理解。
- 工程代码：如果 h 远小于 n（如点是随机分布的），Chan’s Algorithm 有优势。否则 Andrew 足够。
- 高维：使用 CGAL 或 Qhull 等成熟库。
- 实时系统：如果需要增量更新凸包（点动态插入/删除），考虑动态凸包数据结构。
11.3 性能实测参考
对于 n = 10^6 个随机均匀分布的点（坐标范围 [0, 10^9]）：
| 算法 | 凸包大小 h | 耗时 |
|---|---|---|
| Andrew | ~90 | ~180ms |
| Graham | ~90 | ~200ms |
| Jarvis | ~90 | ~15ms |
| Chan (m=h) | ~90 | ~120ms |
当点均匀分布时，h 通常为 O(log n) 级别，Jarvis March 反而最快。但如果点在凸位置（如圆上），h = n，Jarvis 退化为 O(n^2)。
十二、个人思考
12.1 凸包问题的算法设计启示
凸包问题是算法设计思维的一个绝佳缩影。从 Graham（1972）到 Chan（1996），跨越了整整 24 年。这条进化路线告诉我们几个重要的教训：
第一，排序是算法设计的基石。 Graham Scan 的核心洞察是：如果我们按极角排好序，就可以用一次线性扫描完成凸包构建。排序将一个看似复杂的几何问题转化为一个栈操作问题。Andrew 的改进则说明：选择”正确”的排序方式（坐标排序 vs. 极角排序），可以大大简化实现并提高鲁棒性。
第二，output-sensitive 是一种重要的复杂度度量。 对于输出大小可变的问题，仅按输入大小衡量算法效率是不够的。Jarvis March 虽然最坏情况下很差，但它首次展示了利用输出大小来加速的可能性。
第三，“组合”是强大的算法设计策略。 Chan’s Algorithm 并没有发明全新的凸包算法，而是巧妙地将 Graham 和 Jarvis 组合起来，取各自之长。这种”用 A 做预处理，用 B 做查询”的模式在算法设计中非常常见。
第四，repeated squaring 是猜测参数的利器。 当算法的最优参数依赖于未知的输出大小时，通过指数增长来”猜测”参数，可以保证总代价只比最优多一个常数因子。这个技巧在 cache-oblivious 算法和在线算法中也反复出现。
12.2 计算几何的工程现实
理论上优美的算法在实际应用中常常面临尴尬。计算几何可能是受浮点精度影响最严重的算法领域之一。许多在整数坐标下完美运行的算法，换成浮点坐标后就变得脆弱不堪。
我个人的经验是：能用整数就用整数。 如果输入坐标是浮点的，考虑是否可以通过乘以一个大数后取整。如果必须使用浮点，那就不要自己实现——使用 CGAL、Boost.Geometry 或类似的库，它们已经在数值稳健性上投入了大量的工程工作。
12.3 凸包之外
凸包是进入计算几何世界的一扇门。掌握了凸包算法后，自然会遇到一系列相关问题：
- Voronoi 图和 Delaunay 三角剖分：与凸包有深层次的对偶关系（实际上可以通过升维后求凸包来构造 Delaunay 三角剖分）。
- 线段求交：扫描线算法的经典应用。
- 最近点对：分治算法的经典应用。
- 多边形布尔运算：CAD 系统的核心。
计算几何的美在于它将抽象的数学结构与直观的几何图形联系起来。当你看到一个凸包算法在屏幕上一步步”收缩”橡皮筋的动画时，那种数学与视觉的统一感，是其他算法领域很难给予的。
参考文献
Graham, R.L. “An efficient algorithm for determining the convex hull of a finite planar set.” Information Processing Letters, 1(4):132-133, 1972.
Andrew, A.M. “Another efficient algorithm for convex hulls in two dimensions.” Information Processing Letters, 9(5):216-219, 1979.
Jarvis, R.A. “On the identification of the convex hull of a finite set of points in the plane.” Information Processing Letters, 2(1):18-21, 1973.
Chan, T.M. “Optimal output-sensitive convex hull algorithms in two and three dimensions.” Discrete & Computational Geometry, 16(4):361-368, 1996.
Shewchuk, J.R. “Adaptive precision floating-point arithmetic and fast robust geometric predicates.” Discrete & Computational Geometry, 18(3):305-363, 1997.
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M. Computational Geometry: Algorithms and Applications. 3rd edition, Springer, 2008.
O’Rourke, J. Computational Geometry in C. 2nd edition, Cambridge University Press, 1998.
Preparata, F.P., Shamos, M.I. Computational Geometry: An Introduction. Springer-Verlag, 1985.
Barber, C.B., Dobkin, D.P., Huhdanpaa, H. “The quickhull algorithm for convex hulls.” ACM Transactions on Mathematical Software, 22(4):469-483, 1996.
CGAL Project. “CGAL - The Computational Geometry Algorithms Library.” https://www.cgal.org/
相关阅读：最近点对与随机化几何算法 | 斜率优化与凸包技巧