Java实现凸包算法详解（从零开始掌握计算几何中的凸包问题）

为什么选择Andrew算法？

Andrew算法是Graham扫描法的一种变体，具有以下优点：

• 时间复杂度为 O(n log n)，效率高；
• 代码逻辑清晰，易于理解和实现；
• 能正确处理共线点（collinear points）的情况。

这也是我们在Java凸包算法教学中首选它的原因。

算法步骤详解

Andrew算法的核心思想是将点集按x坐标（x相同时按y）排序，然后分别构建凸包的上半部分和下半部分：

1. 对所有点按 x 坐标升序排序（x 相同则按 y 升序）；
2. 从左到右扫描，构建下凸壳（lower hull）；
3. 从右到左扫描，构建上凸壳（upper hull）；
4. 合并上下凸壳，去除重复端点，得到完整凸包。

Java代码实现

首先，我们需要定义一个表示二维点的类：

class Point {    int x, y;        Point(int x, int y) {        this.x = x;        this.y = y;    }        @Override    public String toString() {        return "(" + x + ", " + y + ")";    }}

接下来是核心的凸包算法实现：

import java.util.*;public class ConvexHull {        // 计算叉积：(B - A) × (C - A)    // > 0 表示 C 在 AB 左侧（逆时针）    // < 0 表示 C 在 AB 右侧（顺时针）    // = 0 表示三点共线    private static long cross(Point A, Point B, Point C) {        return (long)(B.x - A.x) * (C.y - A.y) - (long)(B.y - A.y) * (C.x - A.x);    }        public static List<Point> convexHull(List<Point> points) {        if (points.size() <= 1) return points;                // 按 x 升序，x 相同按 y 升序        Collections.sort(points, (a, b) -> {            return a.x != b.x ? a.x - b.x : a.y - b.y;        });                // 构建下凸壳        List<Point> lower = new ArrayList<>();        for (Point p : points) {            while (lower.size() >= 2 &&                    cross(lower.get(lower.size() - 2), lower.get(lower.size() - 1), p) <= 0) {                lower.remove(lower.size() - 1);            }            lower.add(p);        }                // 构建上凸壳        List<Point> upper = new ArrayList<>();        for (int i = points.size() - 1; i >= 0; i--) {            Point p = points.get(i);            while (upper.size() >= 2 &&                    cross(upper.get(upper.size() - 2), upper.get(upper.size() - 1), p) <= 0) {                upper.remove(upper.size() - 1);            }            upper.add(p);        }                // 合并：去掉首尾重复点（因为起点和终点被重复添加）        lower.remove(lower.size() - 1);        upper.remove(upper.size() - 1);                lower.addAll(upper);        return lower;    }        // 测试示例    public static void main(String[] args) {        List<Point> points = Arrays.asList(            new Point(0, 0),            new Point(1, 1),            new Point(2, 2),            new Point(0, 2),            new Point(2, 0),            new Point(1, 0)        );                List<Point> hull = convexHull(points);        System.out.println("凸包顶点：" + hull);    }}

关键点解析

• 叉积判断方向：这是计算几何的基础。通过叉积符号判断三点是左转、右转还是共线。
• 排序的重要性：排序确保我们能按顺序构建上下凸壳。
• 去重处理：上下凸壳的起点和终点相同，需移除重复点。

这个实现能正确处理各种边界情况，包括所有点共线、点数小于3等。

应用场景与扩展

掌握凸包算法教程后，你可以将其应用于：

• 碰撞检测（如游戏开发）
• 图像轮廓分析
• 地理围栏（Geofencing）
• 模式识别与机器学习中的特征提取

进阶方向包括：动态凸包维护、三维凸包、快速近似凸包等。但无论多复杂，都离不开今天学习的这个基础版本。

总结

本文详细讲解了如何用Java语言实现Andrew算法来求解凸包问题。通过清晰的步骤说明和完整的代码示例，即使是初学者也能理解并运行这段计算几何Java代码。希望这篇凸包算法教程能为你打开计算几何的大门！

动手试试吧！修改点集，观察凸包的变化，加深理解。