凸包（Convex Hull）算法详解：从几何原理到工程代码实现

第一次在图像处理任务里真正用到凸包（Convex Hull）这个概念时，我其实并没有意识到这个听起来有点学术味的几何术语，会是这么多算法问题的公共底座。当时要做的事很简单：把一张点云图里最外面的轮廓描出来，找最小外接矩形做旋转校正。结果查了一圈资料，发现所有方案最终都指向同一个东西——构建凸包。后来在路径规划、碰撞检测、聚类可视化里又反复见到它，我才反应过来，这玩意儿不是冷门数学题，而是计算几何里真正绕不开的基础算法。

这篇博文我想把凸包问题一次讲透。从定义、多种主流算法的原理与选型，到可以用在生产环境的完整代码实现，再到我这些年踩过的浮点精度、共线点、退化数据之类的坑，全部摊开写清楚。适合正在学算法竞赛入门、准备面试数据结构与算法题，或者在实际项目中突然被点云凸包、OpenCV 轮廓凸包逼到墙角的开发者参考。保证你看完能直接把这套逻辑搬到代码里。

1. 凸包问题的本质与应用场景解析

1.1 从一支笔和一堆钉子说起

想理解凸包，一个特别好的生活化类比是：在一块木板上钉一堆钉子，然后拿一根橡皮筋，把这堆钉子全部圈在中间。橡皮筋松开后收缩，最终绷紧贴在“最外面一圈”钉子上——这根橡皮筋形成的闭合多边形，就是这堆点的凸包。

这里有两个要点值得细品。第一，凸包一定是一个凸多边形，所有内角都小于等于 180 度，不可能出现“凹”进去的部分。第二，凸包是由点集中的一部分点作为顶点构成的，那些被包在里面的点，在计算过程中会被舍弃掉。换句话说，凸包就是“用最少的外部顶点，包围住所有内部点”的最小凸集。

从数学定义上严格说，一个点集 S 的凸包是包含 S 的最小的凸集合。在二维平面上，它就是那个最优的凸多边形；到了三维空间，就变成凸多面体。大多数人日常接触到的凸包问题，都在二维平面，但三维凸包在点云处理、三维重建里也很常见，方法会更复杂一些，比如快速凸包（QuickHull）的 3D 版、增量法等等。

1.2 一个看似简单却暗藏杀机的问题

从输入输出上看，凸包问题非常朴素：给你一堆平面坐标点，让你求包围它们的最外层凸多边形顶点。但真正动手实现就会发现，这里面的细节非常多。

首先，怎么判断一个点是否在另一个点的“左边”还是“右边”？这需要引入向量叉积。其次，当多个点在同一条直线上时，要保留端点还是全部保留？不同算法处理方式不一样，结果也可能不同。再者，浮点运算的误差怎么控制？用atan2算极角排序时，两个角度几乎相等的点怎么排序？一个小的 epsilon 设置不好，算法可能直接崩掉或者输出错误结果。

这些问题单独看都不难，但合在一起，就会让一个看似 30 行能写完的算法，在实际运行中展现出完全不同的难度。这也是为什么凸包问题能成为计算机视觉、算法竞赛、机器人路径规划、地理信息系统等领域里公认的经典题目。它考察的不是某个偏门技巧，而是一整套处理几何数据时必备的工程素养。

1.3 凸包在哪些场景真正落地

理论归理论，凸包能解决的现实问题其实非常多，我至少见过下面几类高频应用。

• 点云凸包与形状拟合：激光雷达扫描得到的点云数据，首先要提取点云的轮廓。用凸包算法拿到最外边界，才能进一步做体积计算、路面边缘检测或者物体识别。三维的凸包甚至可以直接用于计算物体的包围体积。
• 碰撞检测与路径规划：在机器人或者游戏 AI 中，用凸包代替复杂的不规则碰撞体，可以大幅降低碰撞检测的计算量。两个凸多边形的碰撞检测复杂度远低于两个凹多边形，因为只需要检查分离轴定理即可。
• 图像处理与计算机视觉：OpenCV 里的convexHull函数是专门为这个任务提供的接口。使用轮廓上的点计算凸包后，可以找到“凸性缺陷”，比如手指之间的凹谷，进而做手势识别。这在《计算机视觉：算法与应用》这类经典教材里也有讨论。
• 最小外接矩形与面积最小化：先求凸包，再在凸包上旋转卡壳求最小外接矩形，是计算包围盒的常用套路。很多 OCR 文字矫正、工业检测中的目标对齐，都是基于这条技术路线。
• 聚类分析与数据可视化：在 K-Means 等聚类算法中，把每一类的边界凸包画出来，能非常直观地展示聚类效果。DBSCAN 聚类后，也可以用凸包来描绘每个簇的分布范围。

一句话总结：只要你在做和“形状边界”、“最小包围”、“轮廓提取”相关的事，你几乎绕不开凸包。下面我重点讲算法本身的选型和实现。

2. 主流凸包算法选型对比：别一上来就写代码

2.1 四种常见算法的总体印象

提到凸包算法，市面上流传最广的通常是四种：Graham 扫描、Andrew 单调链、Jarvis 步进法（也叫礼品包裹法）、快速凸包（QuickHull）。很多人第一次学凸包，会直接被 Graham 扫描的“极角排序”劝退，然后转投 Andrew 的怀抱。我个人觉得，这两种算法是优先值得掌握的，它们也都是工程里最常用的。

• Graham 扫描：核心思想是选一个最左下的点作为基准，把其余点按照极角排序，然后用一个单调栈维护凸包顶点。复杂度 O(n log n)，主要耗时在排序，栈操作为 O(n)。
• Andrew 单调链：也叫 Andrew 算法，它不需要极角排序，只需要按照 x 坐标排序，然后分别构建下凸壳和上凸壳，最后拼起来。复杂度同样是 O(n log n)，但因为避免了三反函数和精度问题，工程上稳定性更好。
• Jarvis 步进法 / Gift Wrapping：思路非常直观，像用绳子绕钉子一圈，每次选择转角最小的点作为下一个凸包顶点。复杂度 O(nh)，其中 h 是凸包顶点数。当 h 很小的时候表现极佳，最坏情况退化为 O(n^2)。
• 快速凸包 QuickHull：分治思想，每轮找最左和最右点，再递归处理两侧的最远点。平均复杂度 O(n log n)，最坏情况也可能退化到 O(n^2)，在代码实现上比前两者要绕一些。

2.2 算法复杂度和适用场景对比

为了让你在项目里做选型时一眼能看明白，我把常用算法的核心参数整理成了下面的对照表。

这里需要说明一下O(nh)的意义。Jarvis 步进法的复杂度除了和点数 n 有关，还取决于最终凸包上的顶点数量 h。你想象一个近似圆形的点集，凸包顶点 h 可能接近 n，此时 Jarvis 会退化到 O(n^2)，效率很差。但如果你处理的是点云里的一次均匀采样，凸包顶点通常远小于总点数，Jarvis 反而可能跑得比排序类算法还快。所以没有绝对的“最优算法”，只有“最适合当前数据形态的算法”。

2.3 我在实际项目中如何选择

就我自己的工程经验来讲，90% 的二维凸包需求，我会优先选择 Andrew 单调链算法。原因非常实际：它不涉及极角和浮点三角函数运算，排序对象只是 x/y 坐标，数值稳定性最好，代码也足够短。Graham 扫描虽然更“经典”，但在处理坐标值很大的整数点或者带有噪声的浮点坐标时，用atan2算极角再排序，容易出现两个角度非常接近或者跨象限边界时的排序稳定性问题。

Python 里如果只是快速验证思路，我也会直接用 OpenCV 的cv2.convexHull，它底层是 Sklansky 算法，效率很高。但如果我要把这个逻辑嵌入到 C++ 服务端或者算法竞赛代码里，我会自己实现 Andrew。接下来两章，我把 Graham 扫描和 Andrew 单调链各展开讲一遍，附上完整可运行的实现，再说明关键细节和为什么。

3. Graham 扫描算法：从极角排序到栈操作

3.1 前置知识：向量叉积

Graham 扫描的核心判断工具是向量叉积（Cross Product）。对于三个点 p、q、r，叉积可以写成：

$$ cross(p, q, r) = (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x) $$

这个值的意思是：从向量 pq 到向量 pr 的旋转方向。在二维平面上：

• 如果cross(p, q, r) > 0，说明点 r 在向量 pq 的左侧，三个点呈逆时针转向；
• 如果cross(p, q, r) < 0，说明点 r 在向量 pq 的右侧，呈顺时针转向；
• 如果cross(p, q, r) == 0，说明三点共线。

我们维护凸包栈的时候，要确保所有相邻顶点之间都保持同一方向的转向（通常保留逆时针）。一旦发现新的点让栈顶出现顺时针转向，就说明这个栈顶点“凹”了，需要弹出。这个逻辑是 Graham 和 Andrew 算法的共同基石。

3.2 Graham 扫描完整的步骤拆解

我把 Graham 扫描拆成下面这几个步骤来写，代码实现的时候按这个顺序基本不会乱。

1. 选择基准点：在所有点中找到 y 坐标最小的点，如果 y 相同则取 x 坐标更小的点。这个点一定在凸包上，记为 p0。
2. 按极角排序：以 p0 为原点，把其余点按照相对于 p0 的极角从小到大排序。如果极角相同，则按照距离 p0 由近到远排序。
3. 用单调栈扫描：先把 p0 和排序后的第一个点压入栈。然后依次处理后续每个点 p，如果当前栈顶的两个点和 p 构成的转向是顺时针（叉积小于等于 0），就把栈顶弹出，重复直到叉积大于 0，再把 p 压入栈。
4. 得到结果：扫描结束后，栈中剩下的就是从 p0 开始按逆时针排列的凸包顶点。

其中“极角相同则按距离排序”这一点非常重要。比如基准点 p0 正上方有好几个点，如果不排序直接处理，后面的逻辑会出现栈中相邻点交叉的情况，最终漏掉最远点或者输出错误顺序。排序后，距离近的先进栈，距离远的点在扫描时会因为“叉积大于 0”而被保留，而中间的点会被弹出。

3.3 C++ 完整实现及关键注释

以下是 Graham 扫描的 C++ 实现，我加了比较详细的注释。注意，工程上处理浮点数据时建议引入一个很小的eps来避免精度问题，但我这里为了可读性先用直接比较，后面会在常见问题章节专门讲 eps 的取值逻辑。

#include <bits/stdc++.h> using namespace std; struct Point { double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} bool operator<(const Point& other) const { if (y != other.y) return y < other.y; return x < other.x; } }; // 叉积：pq 与 pr 的转向关系 double cross(const Point& p, const Point& q, const Point& r) { return (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x); } // 平方距离，避免开根号，减少浮点误差 double dist2(const Point& a, const Point& b) { double dx = a.x - b.x; double dy = a.y - b.y; return dx * dx + dy * dy; } // 输入点集，输出凸包顶点（逆时针顺序） vector<Point> convexHullGraham(vector<Point> pts) { int n = (int)pts.size(); if (n <= 1) return pts; // 1. 找基准点：最低最左 sort(pts.begin(), pts.end()); Point p0 = pts[0]; // 2. 极角排序，极角相同则按距离升序 sort(pts.begin() + 1, pts.end(), [&](Point a, Point b) { double c = cross(p0, a, b); if (c != 0) return c > 0; // 极角更小的排前面 return dist2(p0, a) < dist2(p0, b); // 共线时近的在前 }); // 3. 单调栈扫描 vector<Point> hull; for (int i = 0; i < n; ++i) { while (hull.size() >= 2 && cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0) { hull.pop_back(); // 出现顺时针或共线，弹出中间点 } hull.push_back(pts[i]); } return hull; } int main() { vector<Point> pts = { {0, 0}, {1, 1}, {2, 2}, {0, 3}, {3, 0}, {3, 3}, {1, 2}, {2, 1} }; vector<Point> hull = convexHullGraham(pts); for (auto& p : hull) { cout << "(" << p.x << ", " << p.y << ")" << endl; } return 0; }

代码里最核心的就是while循环中的叉积判断。这里我写的是<= 0，意味着如果出现顺时针转向或者三点共线，就会把栈顶点弹掉。这个选择需要结合题目要求看：如果你希望凸包顶点不包含共线边上的中间点，就用这个版本；如果你想保留所有共线边界点，可以把<= 0里的等号去掉，变成只弹掉顺时针的情况。

从输出顺序来看，这段代码返回的凸包顶点是逆时针排列的，起始点是最低最左点。实测下来，这个顺序在很多几何计算中非常重要，比如后续做多边形面积计算时，逆时针顺序配合叉积公式能直接得到正面积。

4. Andrew 单调链算法：工程上更好用的选择

4.1 为什么还需要 Andrew 算法

Graham 扫描虽然经典，但有个隐患：极角排序需要计算atan2之类的角度值。当点数量很大，或者坐标是浮点数时，角度值的微小误差可能让两个点的排序关系不稳定，最终导致凸包顶点顺序错乱。而且atan2本身是带计算成本的，如果数据点有几万个，这个性能损耗会很明显。

Andrew 单调链算法巧妙地规避了这些问题。它只对点的 x 坐标排序，不需要计算任何角度，利用单调栈分别构造上凸壳和下凸壳，最后合并。排序逻辑简单、稳定，所以是工程上我更推荐的首选方案。本质上说，Andrew 是 Graham 扫描的一个更稳健的变体，只不过排序基准从“极角”换成了“横坐标”。

4.2 Andrew 单调链核心流程

Andrew 算法的完整流程分成这四步：

1. 按坐标排序：将所有点按照 x 坐标升序排序，如果 x 相同，再按 y 坐标升序排序。
2. 构造下凸壳：从左往右扫描所有点，用单调栈维护，保证转向一直为逆时针。遇到顺时针或者共线，就弹出栈顶。
3. 构造上凸壳：从右往左扫描所有点，同样用单调栈维护，保证转向为逆时针。
4. 合并结果：下凸壳和上凸壳合并之后，首尾有点重复，去掉最后一个重复点即可，最终就得到按逆时针排列的完整凸包。

这个算法非常优雅的一点是，下凸壳和上凸壳的拼接过程非常自然，不需要额外的旋转操作。复杂度是排序的 O(n log n) 加线性扫描的 O(n)，整体 O(n log n)，和 Graham 一致，但常数更小，且极少因为浮点比较出问题。

4.3 C++ 实现示例与 Python 版本

先看 C++ 实现，我建议工程里直接抄这一版：

#include <bits/stdc++.h> using namespace std; struct Point { double x, y; Point(double x = 0, double y = 0) : x(x), y(y) {} bool operator<(const Point& other) const { if (x != other.x) return x < other.x; return y < other.y; } }; double cross(const Point& p, const Point& q, const Point& r) { return (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x); } vector<Point> convexHullAndrew(vector<Point> pts) { int n = (int)pts.size(); if (n <= 1) return pts; sort(pts.begin(), pts.end()); vector<Point> lower; // 从左到右，构造下凸壳 for (auto& p : pts) { while (lower.size() >= 2 && cross(lower[lower.size() - 2], lower.back(), p) <= 0) { lower.pop_back(); } lower.push_back(p); } vector<Point> upper; // 从右到左，构造上凸壳 for (auto it = pts.rbegin(); it != pts.rend(); ++it) { while (upper.size() >= 2 && cross(upper[upper.size() - 2], upper.back(), *it) <= 0) { upper.pop_back(); } upper.push_back(*it); } // 下凸壳最后一个点是上凸壳第一个点，去掉重复 lower.pop_back(); upper.pop_back(); lower.insert(lower.end(), upper.begin(), upper.end()); return lower; } int main() { vector<Point> pts = { {0, 0}, {1, 1}, {2, 2}, {0, 3}, {3, 0}, {3, 3}, {1, 2}, {2, 1} }; vector<Point> hull = convexHullAndrew(pts); for (auto& p : hull) { cout << "(" << p.x << ", " << p.y << ")" << endl; } return 0; }

运行每个点都能对上。lower 和 upper 分别弹出最后一个元素，是为了去掉首尾连接处的重复点。如果你需要对凸包上的共线点做去重，可以调整<= 0的等号。

Python 版本我同样给一个，日常分析和原型验证足够用：

import math def cross(p, q, r): return (q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0]) def convex_hull(points): pts = sorted(points) # 按 x 升序，再按 y 升序 if len(pts) <= 1: return pts lower = [] for p in pts: while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) upper = [] for p in reversed(pts): while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) return lower[:-1] + upper[:-1] points = [(0, 0), (1, 1), (2, 2), (0, 3), (3, 0), (3, 3), (1, 2), (2, 1)] print(convex_hull(points))

Python 版本的好处是结构一目了然，特别适合初学者把它和 C++ 版本对照理解。两个版本的核心判断条件完全一致，所以你在一个环境里调通的逻辑，可以直接翻译到另一个环境。

4.4 用 OpenCV 快速完成凸包计算

如果你的工作流本身就在用 OpenCV，完全没必要重复造轮子。对一幅图像做完轮廓提取后，可以直接调用cv2.convexHull得到轮廓的凸包。核心用法如下：

import cv2 # contours 来自 cv2.findContours contour = contours[0] hull = cv2.convexHull(contour) # 默认 returnPoints=False，这里返回索引

这里有一个容易踩的坑：cv2.convexHull有个参数returnPoints，默认是False，返回的是凸包顶点的轮廓索引，而不是坐标。如果你直接用cv2.convexHull(contour)，拿到的是一串整数索引，后续绘制轮廓才发现不对劲。想要坐标，要显式设成returnPoints=True。另外，OpenCV 的凸包是按轮廓点的存储顺序输出的，不保证是严格的逆时针，所以再往下一步做几何计算时，可能需要重新处理顺序。

5. 常见问题与排查技巧实录

5.1 浮点精度：为什么我的凸包总是差一点

这是我在实际项目里遇到最多的问题。坐标是浮点数，叉积计算中会产生微小误差。判断叉积cross == 0在浮点世界里几乎不可靠，尤其三点接近共线时，叉积可能是1e-15或者-1e-15这种极小值，直接比较等于 0 很容易漏判。

解决办法是引入一个容差值eps，把所有比较改成容差比较。比如判断是否顺时针时用cross <= eps，判断是否逆时针时用cross >= -eps。这个eps通常取1e-8到1e-10之间，具体看你的坐标尺度。如果你的坐标都是 0 到 10000 之间的整数，叉积的量级很大，1e-10没问题；如果你的坐标是 0 到 1 之间的小数，叉积本身可能只有1e-4，这时候eps取1e-10反而没问题，因为数据噪声远大于浮点误差。经验法则是：eps要比浮点误差高一个量级，同时远小于数据本身的有效精度。

5.2 共线点的归宿：边界上的点保不保留

很多初学者在这里纠结很久。假设点集中有一整排点在同一条直线上，这些点都在凸包的边界上。Graham 和 Andrew 用<= 0弹出共线点的话，最终凸包只会保留这条边两端的端点，中间点会被丢掉。

如果你需要保留所有共线边界点，可以把判断条件改成cross < 0（只弹顺时针），这样三点共线的时候会保留中间点。但这个选择会影响后面很多计算，比如凸包顶点数会变多、旋转卡壳的最值位置可能改变。我的建议是：除非题目明确要求“输出所有边界点”，否则一律用<= 0弹出共线点，让凸包顶点数保持最小，这样后续无论做面积计算、碰撞检测还是可视化，都更清爽。

5.3 退化情况：点数不足、全部共线、重合点

实际输入数据不会像教科书样例那么干净。我梳理过一份凸包算法最容易翻车的退化情况清单，你可以对照自查：

尤其注意重复点。如果不去重，重复点之间叉积为 0，配合<= 0的弹出条件，结果通常还好，但如果你换成cross < 0保留共线点的写法，重复点会造成凸包顶点数量膨胀。稳妥做法是在进入算法前统一sort + unique去重，或者用哈希集合去重。

5.4 排序稳定性与索引起点问题

Graham 扫描里，极角排序结果如果不稳定，很容易出现两个点极角相等但距离排序颠倒的情况。前面代码里用dist2(p0, a) < dist2(p0, b)处理了极角相同的情况，这行不能省。否则排序器可能把远的点排在近的点前面，扫描时会漏掉应该作为凸包顶点的最远点。

Andrew 算法虽然只按 x/y 排序，没有极角问题，但要注意比较器必须满足严格弱序（strict weak ordering）。在 C++ 的std::sort里，如果你的比较器返回相等结果时没有正确处理，会导致排序结果不确定甚至崩溃。比如：

if (a.x != b.x) return a.x < b.x; return a.y < b.y;

这种写法就是正确的，因为它对完全相等的点返回 false，对不同的点也能给出明确的真假结果。千万不要只写return a.x < b.x;，否则 x 坐标相同的点之间比较关系不对称，排序就会不稳定。

另外还有一个低调但常见的坑：很多计算几何代码里点的索引从 0 开始，但某些库或 OpenCV 接口里返回的索引是另外一套规则。调试凸包问题时，建议先可视化输出每个顶点坐标，而不要直接根据索引做计算，否则很容易因为下标错位排查半天。

5.5 实测性能对比与调参经验

我在一个约 5 万个随机点的点集上做过一次简单测试，Graham 和 Andrew 的耗时差距大概在 10% 到 20% 之间，Andrew 通常更快，主要原因就是少了对atan2的大量调用。如果你的点集是实时生成的点云，比如每秒钟处理几十次，这个差异会被放大。

OpenCV 的cv2.convexHull底层实现效率很高，在图像轮廓数据上表现非常好，但它是针对整数坐标的和特定场景优化的。如果你需要对浮点坐标做更精细的几何处理，自实现 Andrew 往往更可控。

关于栈操作的一个小细节：很多人担心vector的pop_back会不会影响性能。实测下来不用担心，在O(n log n)排序面前，栈操作的O(n)线性成本根本排不上号。反而是在排序环节，如果你用带比较函数对象的写法，可能在数万点级别就会感受到明显开销。这时候可以用std::sort加 lambda，编译器优化后会好很多。

6. 个人的一些收尾经验

如果你现在正要开始写凸包，我的建议是直接写 Andrew 单调链，它对新手友好，代码也短。先把 C++ 或 Python 的版本跑通，再回头把 Graham 扫描的原理对照着看一遍，你会发现两个算法骨子里是同一套叉积思想。最后再用 OpenCV 处理一张真实图像，感受一下轮廓凸包和点云凸包的差别，这个流程下来，凸包问题基本就吃透了。

我在实际项目里还有个小习惯：凡是涉及凸包的代码，我一定会写一个纯随机的点集测试函数，跑个几千个点，然后和暴力法或者 OpenCV 的凸包结果对比验证。这个步骤能帮你抓住浮点误差、共线点处理不当等等几乎所有边界问题。另外，计算几何的调试和普通业务代码不太一样，打印日志不如画图直观。Python 里用 matplotlib 画一下点集和凸包，一眼就能看出哪里错了。

最后再分享一个小技巧：对于海量点云数据，如果不需要精确凸包，可以先对点云做降采样或者格网化，再去求凸包，速度能提升非常多，结果通常也足够用。需要精确结果的场景，再用本文的算法直接对全部点运算。凸包本身只是一个起点，后面接的旋转卡壳、最小外接矩形、凸性缺陷检测才是真正发挥它价值的地方。