★ FEATURED ARTICLE 第一次在图像处理任务里真正用到凸包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 算法复杂度和适用场景对比为了让你在项目里做选型时一眼能看明白我把常用算法的核心参数整理成了下面的对照表。算法时间复杂度是否依赖极角排序工程稳定性适用场景Graham 扫描O(n log n)是中等依赖角度计算精度一般静态点集教科书经典Andrew 单调链O(n log n)否高只依赖 x/y 坐标排序工程推荐尤其是浮点数据Jarvis 步进法O(nh)否高逻辑简单凸包顶点数很小的场景QuickHull平均 O(n log n)否中等最坏退化二维/三维均可动态场景少见这里需要说明一下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 扫描拆成下面这几个步骤来写代码实现的时候按这个顺序基本不会乱。选择基准点在所有点中找到 y 坐标最小的点如果 y 相同则取 x 坐标更小的点。这个点一定在凸包上记为 p0。按极角排序以 p0 为原点把其余点按照相对于 p0 的极角从小到大排序。如果极角相同则按照距离 p0 由近到远排序。用单调栈扫描先把 p0 和排序后的第一个点压入栈。然后依次处理后续每个点 p如果当前栈顶的两个点和 p 构成的转向是顺时针叉积小于等于 0就把栈顶弹出重复直到叉积大于 0再把 p 压入栈。得到结果扫描结束后栈中剩下的就是从 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; } // 输入点集输出凸包顶点逆时针顺序 vectorPoint convexHullGraham(vectorPoint 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. 单调栈扫描 vectorPoint 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() { vectorPoint pts { {0, 0}, {1, 1}, {2, 2}, {0, 3}, {3, 0}, {3, 3}, {1, 2}, {2, 1} }; vectorPoint 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 算法的完整流程分成这四步按坐标排序将所有点按照 x 坐标升序排序如果 x 相同再按 y 坐标升序排序。构造下凸壳从左往右扫描所有点用单调栈维护保证转向一直为逆时针。遇到顺时针或者共线就弹出栈顶。构造上凸壳从右往左扫描所有点同样用单调栈维护保证转向为逆时针。合并结果下凸壳和上凸壳合并之后首尾有点重复去掉最后一个重复点即可最终就得到按逆时针排列的完整凸包。这个算法非常优雅的一点是下凸壳和上凸壳的拼接过程非常自然不需要额外的旋转操作。复杂度是排序的 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); } vectorPoint convexHullAndrew(vectorPoint pts) { int n (int)pts.size(); if (n 1) return pts; sort(pts.begin(), pts.end()); vectorPoint 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); } vectorPoint 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() { vectorPoint pts { {0, 0}, {1, 1}, {2, 2}, {0, 3}, {3, 0}, {3, 3}, {1, 2}, {2, 1} }; vectorPoint 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) # 默认 returnPointsFalse这里返回索引这里有一个容易踩的坑cv2.convexHull有个参数returnPoints默认是False返回的是凸包顶点的轮廓索引而不是坐标。如果你直接用cv2.convexHull(contour)拿到的是一串整数索引后续绘制轮廓才发现不对劲。想要坐标要显式设成returnPointsTrue。另外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 或 1算法直接返回空或单点代码开头提前判断并返回原数组全部点共线凸包退化成一条线段甚至只剩两个点确认需求需要输出两端点还是所有共线点存在重复坐标点排序后相邻重复叉积为 0预处理去重否则可能引起栈内死循环所有点 x 坐标相同Andrew 的下凸壳退化成一个点只要排序稳定算法仍能正确输出线段或点尤其注意重复点。如果不去重重复点之间叉积为 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 画一下点集和凸包一眼就能看出哪里错了。最后再分享一个小技巧对于海量点云数据如果不需要精确凸包可以先对点云做降采样或者格网化再去求凸包速度能提升非常多结果通常也足够用。需要精确结果的场景再用本文的算法直接对全部点运算。凸包本身只是一个起点后面接的旋转卡壳、最小外接矩形、凸性缺陷检测才是真正发挥它价值的地方。
阅读完成 · 觉得有帮助？
