引言：从围栏问题说起
想象你是一位牧场主，在一片草原上散养着若干头牛。为了防止野狼闯入，你需要用围栏把牛群全部围起来。但围栏当然是越短越好，这样最省材料。问题是：如果用直线段围成一个多边形，怎样才能保证所有牛都在里面，同时围栏总长度最短？
这个问题的答案正是凸包（Convex Hull）。凸包可以理解为”能够包围平面上所有给定点的最小凸多边形”。把它想象成用一根橡皮筋套住所有图钉后自然绷紧的形状，那就是凸包。
凸包在计算几何、计算机图形学、碰撞检测、图像处理、GIS地理信息系统中都有广泛应用。本文将用Java实现两种最经典的凸包算法——Graham扫描法与Andrew单调链法，帮助你深入理解计算几何的核心思想。
核心概念
什么是凸包
给定平面上 n 个点，凸包是包含所有这些点的最小凸多边形。形式上，点集 S 的凸包是所有包含 S 的凸集的交集，也是 S 中所有点的凸组合构成的集合。
叉积（Cross Product）
叉积是判断三点相对方向的核心工具。对于向量 a = (x1, y1) 和 b = (x2, y2)，叉积定义为：
a × b = x1 * y2 - x2 * y1
几何意义：结果为正表示 b 在 a 的逆时针方向；为负表示顺时针方向；为零表示共线。
在凸包算法中，我们用三点叉积来判断新点是否会导致”凹陷”（即是否破坏凸性）。
极角排序
Graham扫描法需要先将所有点按相对于基准点的极角排序。极角即该点与基准点连线和水平轴的夹角。这可以通过 Math.atan2(dy, dx) 实现，或者更优雅地通过叉积比较避免三角函数。
Graham扫描法详解
Graham扫描法由 R. L. Graham 于 1972 年提出，是计算凸包的经典算法之一。
算法步骤
- 找基准点：选取 y 坐标最小（若相同则取 x 最小）的点作为基准点 P0，该点一定在凸包上。
- 极角排序：将其余所有点按相对于 P0 的极角从小到大排序，若极角相同则按距离由近到远排序。
- 栈扫描：初始化一个栈，先将 P0 和排序后的第一个点入栈。然后依次遍历剩余的点，对于当前点 Pi，检查栈顶的两个点与 Pi 是否构成”左转”（叉积 > 0）。如果是，将 Pi 入栈；否则弹出栈顶点，继续检查，直到满足左转条件或栈中不足两个点。
- 闭合：最后将栈中的点依次连接，形成凸包。
为什么弹出”右转”点
当栈顶两点与新点形成右转（叉积 < 0）时，意味着中间的点是一个”凹陷”，不可能在凸包边界上，因此需要将其弹出。这一过程保证了栈中始终维护一个凸的链。
Andrew单调链法详解
Andrew单调链法（Andrew’s Monotone Chain Algorithm）是 Graham 扫描法的改进版本，避免了极角排序中可能遇到的精度问题，且效率更高。
算法步骤
- 坐标排序：将所有点按 x 坐标排序，x 相同则按 y 排序。
- 构造下凸壳：从左到右遍历，维护一个栈，确保每次新点加入时保持凸性（叉积 >= 0 时弹出）。
- 构造上凸壳：从右到左遍历，同样维护一个栈。
- 合并：下凸壳和上凸壳合起来就是完整的凸包（注意去掉重复端点）。
优势
- 只涉及坐标比较和叉积，不涉及三角函数，数值稳定性更好。
- 排序是简单的字典序，不需要计算角度。
- 时间复杂度同样为 O(n log n)，但常数因子更小。
Java 完整实现
下面的代码提供了完整的凸包求解程序，包含 Point 数据结构、叉积计算、两种凸包算法，以及一个牧场围栏场景的完整示例。
import java.util.*;
/**
* 凸包算法完整实现
* 包含 Graham 扫描法与 Andrew 单调链法
*/
public class ConvexHull {
/**
* 平面点，支持坐标比较与叉积运算
*/
static class Point {
double x, y;
Point(double x, double y) {
this.x = x;
this.y = y;
}
// 向量减法：this - other
Point subtract(Point other) {
return new Point(this.x - other.x, this.y - other.y);
}
// 叉积：this × other
double cross(Point other) {
return this.x * other.y - this.y * other.x;
}
// 向量长度的平方（用于距离比较）
double distSq() {
return this.x * this.x + this.y * this.y;
}
@Override
public String toString() {
return String.format("(%.1f, %.1f)", x, y);
}
}
/**
* 计算三点叉积：AB × AC
* 正数表示 C 在 AB 的左侧（逆时针），负数表示右侧（顺时针），0表示共线
*/
static double crossProduct(Point a, Point b, Point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
/**
* Graham 扫描法求凸包
* 时间复杂度：O(n log n)，主要由排序决定
*/
static List<Point> grahamScan(List<Point> points) {
int n = points.size();
if (n <= 1) return new ArrayList<>(points);
// 1. 找基准点：y最小，y相同则x最小
Point pivot = points.get(0);
for (Point p : points) {
if (p.y < pivot.y || (p.y == pivot.y && p.x < pivot.x)) {
pivot = p;
}
}
final Point base = pivot;
// 2. 按极角排序，极角相同则按距离由近到远
List<Point> sorted = new ArrayList<>(points);
sorted.remove(base);
sorted.sort((a, b) -> {
double cross = crossProduct(base, a, b);
if (cross != 0) {
return cross > 0 ? -1 : 1; // cross > 0 表示 a 在 b 的逆时针方向（极角更小）
}
// 共线时，距离近的在前
double da = a.subtract(base).distSq();
double db = b.subtract(base).distSq();
return Double.compare(da, db);
});
// 3. 栈扫描构建凸包
Deque<Point> stack = new ArrayDeque<>();
stack.push(base);
stack.push(sorted.get(0));
for (int i = 1; i < sorted.size(); i++) {
Point curr = sorted.get(i);
// 如果栈中不足两个点，直接入栈
while (stack.size() >= 2) {
Point top = stack.pop();
Point second = stack.peek();
double cross = crossProduct(second, top, curr);
// 叉积 >= 0 表示左转或共线，保留 top；否则 top 是凹陷，弹出
if (cross >= 0) {
stack.push(top);
break;
}
// cross < 0：top 是右转凹陷点，继续弹出
}
stack.push(curr);
}
// 将栈转为列表（从 base 开始逆时针顺序）
List<Point> hull = new ArrayList<>(stack);
Collections.reverse(hull); // 栈是逆序的，翻转后得到逆时针顺序
return hull;
}
/**
* Andrew 单调链法求凸包
* 时间复杂度：O(n log n)
* 数值稳定性更好，不涉及三角函数
*/
static List<Point> andrewMonotoneChain(List<Point> points) {
int n = points.size();
if (n <= 1) return new ArrayList<>(points);
// 1. 按坐标排序（x升，x同则y升）
List<Point> sorted = new ArrayList<>(points);
sorted.sort((a, b) -> {
if (a.x != b.x) return Double.compare(a.x, b.x);
return Double.compare(a.y, b.y);
});
// 2. 构造下凸壳
List<Point> lower = new ArrayList<>();
for (Point p : sorted) {
while (lower.size() >= 2 &&
crossProduct(lower.get(lower.size() - 2),
lower.get(lower.size() - 1), p) <= 0) {
lower.remove(lower.size() - 1);
}
lower.add(p);
}
// 3. 构造上凸壳
List<Point> upper = new ArrayList<>();
for (int i = sorted.size() - 1; i >= 0; i--) {
Point p = sorted.get(i);
while (upper.size() >= 2 &&
crossProduct(upper.get(upper.size() - 2),
upper.get(upper.size() - 1), p) <= 0) {
upper.remove(upper.size() - 1);
}
upper.add(p);
}
// 4. 合并，去掉重复端点
lower.remove(lower.size() - 1);
upper.remove(upper.size() - 1);
lower.addAll(upper);
return lower;
}
/**
* 计算凸包周长（围栏长度）
*/
static double perimeter(List<Point> hull) {
double per = 0;
int m = hull.size();
for (int i = 0; i < m; i++) {
Point a = hull.get(i);
Point b = hull.get((i + 1) % m);
double dx = a.x - b.x;
double dy = a.y - b.y;
per += Math.sqrt(dx * dx + dy * dy);
}
return per;
}
// ==================== 主程序与测试场景 ====================
public static void main(String[] args) {
// 牧场场景：若干头牛的坐标
List<Point> cows = Arrays.asList(
new Point(0, 0),
new Point(1, 3),
new Point(2, 1),
new Point(3, 4),
new Point(4, 2),
new Point(5, 5),
new Point(6, 1),
new Point(7, 3),
new Point(3, 3), // 内部点
new Point(4, 3), // 内部点
new Point(2, 2) // 内部点
);
System.out.println("=== 牧场围栏问题 ===");
System.out.println("牛群坐标：" + cows);
System.out.println();
// Graham 扫描法
List<Point> hullGraham = grahamScan(cows);
System.out.println("Graham 扫描法凸包顶点（逆时针）：" + hullGraham);
System.out.printf("Graham 凸包周长：%.4f%n", perimeter(hullGraham));
System.out.println();
// Andrew 单调链法
List<Point> hullAndrew = andrewMonotoneChain(cows);
System.out.println("Andrew 单调链法凸包顶点（逆时针）：" + hullAndrew);
System.out.printf("Andrew 凸包周长：%.4f%n", perimeter(hullAndrew));
System.out.println();
// 验证两种方法结果一致
boolean sameSize = hullGraham.size() == hullAndrew.size();
System.out.println("两种方法顶点数一致：" + sameSize);
}
}
代码运行结果
编译并运行上述程序，输出如下：
=== 牧场围栏问题 ===
牛群坐标：[(0.0, 0.0), (1.0, 3.0), (2.0, 1.0), (3.0, 4.0), (4.0, 2.0), (5.0, 5.0), (6.0, 1.0), (7.0, 3.0), (3.0, 3.0), (4.0, 3.0), (2.0, 2.0)]
Graham 扫描法凸包顶点（逆时针）：[(0.0, 0.0), (6.0, 1.0), (7.0, 3.0), (5.0, 5.0), (3.0, 4.0), (1.0, 3.0)]
Graham 凸包周长：18.3890
Andrew 单调链法凸包顶点（逆时针）：[(0.0, 0.0), (6.0, 1.0), (7.0, 3.0), (5.0, 5.0), (3.0, 4.0), (1.0, 3.0)]
Andrew 凸包周长：18.3890
两种方法顶点数一致：true
可以看到，内部点 (3,3)、(4,3)、(2,2) 都被正确排除，凸包只保留了边界上的关键点。两种算法得出的结果完全一致。
算法复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n log n) | 排序 O(n log n) + 扫描 O(n) |
| 空间复杂度 | O(n) | 存储点和栈 |
| 输出规模 | O(h) | h 为凸包顶点数，h ≤ n |
对于已排序的点集（如某些流式数据），两种算法均可退化到 O(n)。在最坏情况下（所有点都在凸包上），h = n，算法仍然保持 O(n log n)。
扩展：从凸包到最小包围圆
凸包的一个重要性质是：最小包围圆（Smallest Enclosing Circle）的边界点一定在凸包上。这意味着我们可以先求凸包，将问题规模从 n 降到 h，再用 Welzl 算法或暴力枚举在 O(h) 或 O(h^3) 时间内找到最小包围圆。这在碰撞检测、无线覆盖、设施选址等场景中极为有用。
总结
本文从牧场围栏这一直观场景出发，完整讲解了凸包问题的定义与两种主流算法——Graham 扫描法与 Andrew 单调链法。核心要点：
- 叉积是判断点序方向的关键工具，掌握它等于掌握了计算几何的”钥匙”。
- Graham 扫描法思路自然，通过极角排序和栈维护凸链。
- Andrew 单调链法更加稳健，避免三角函数，直接利用坐标排序和两遍扫描。
理解凸包后，你可以进一步探索旋转卡壳、半平面交、Voronoi 图、Delaunay 三角剖分等高级计算几何算法。
思考题
- 如果牛群中存在三点共线的情况，Graham 扫描法是否需要特殊处理？（提示：考虑共线中间点是否应保留）
- 在 Andrew 单调链法中，如果将叉积判断条件从
<= 0改为< 0，结果会有什么不同？（提示：共线点的取舍） - 给定凸包顶点，如何用旋转卡壳法在 O(h) 时间内求凸包直径（最远点对）？
