凸包Convex Hull问题算法详解如果你跟计算几何打过交道肯定绕不开凸包这个东西。简单说给一堆散落的点凸包就是能把所有点都包进去的最小凸多边形就像拿一根橡皮筋把钉子板上的钉子全部箍起来。听起来简单但这个“简单”的问题在计算机里并不那么好解决而且它是很多高级算法的基础比如旋转卡壳求最大距离、凸多边形碰撞检测、点云边界提取都会先算凸包。我最早接触凸包是为了处理激光雷达的点云数据后来做图像轮廓分析也频繁用到可以说是计算几何里最高频的入门级硬核问题。这篇文章我会把凸包的几种主流算法——Graham扫描、Andrew单调链、Jarvis步进、分治法——逐个拆开讲不仅讲原理还会给出可以“抄作业”的C实现最后分享一些实际调试中踩过的坑。不管是应付算法面试、写竞赛代码还是做图像处理和点云分析你都能从这篇文章里找到可以直接用的东西。1. 凸包问题本质与算法选型思路1.1 凸包的数学定义和几何直觉凸包的严谨定义是给定平面上点集SS的凸包是所有包含S的最小凸集的边界。这个定义里“凸”是关键——在凸集内任取两点连一条线段这条线段必须完全落在集合内部。凸多边形就是典型的凸集凹多边形就违反了这条规则。几何直觉更简单。你在木板上钉一堆钉子拿一根橡皮筋把这些钉子全部围住松开手后橡皮筋收缩形成的形状就是凸包。橡皮筋碰到的那几个钉子就是凸包顶点没碰到的点都在凸包内部。这个过程其实就是在模拟寻找最外层点的过程。从计算角度看凸包问题本质上是找“极值点”的问题。给定n个点输出结果的规模凸包顶点数h是个变量范围是3到n。这个特性直接影响了不同算法的复杂度分析和适用场景也是很多人一开始搞不清的地方——有些算法在点集本身分布得很“圆”的时候表现很好有些则在凸包顶点数很少时优势巨大。1.2 为什么凸包是计算几何的基础问题凸包之所以重要是因为它能大幅简化几何计算。给定任意一组点如果你想判断一个新点是否落在这些点围成的区域内直接做法需要处理所有点之间的关系复杂度很高。但如果先求出凸包判断新点是否在凸多边形内部可以用O(h)甚至O(log h)的算法完成h为凸包顶点数快得多。另一个经典应用是直径问题。平面上距离最远的两个点一定位于凸包的顶点上。你不需要比较所有点的两两距离先算凸包再用旋转卡壳复杂度直接从O(n^2)降到O(n log n)。类似的性质还有很多——最远点对、最小外接矩形、最大空圆等问题基本都是先求凸包再进一步处理。对从事图像处理的人而言凸包还经常用来做物体形状分析。一个手写数字、一片树叶、一只手的轮廓点的数量可能成千上万直接处理所有边缘点非常耗时。但凸包将轮廓“简化”成一个更紧凑的多边形同时保留了形状的整体特征后续的傅里叶描述子、Hu矩、凸缺陷分析等操作都在凸包基础上进行。1.3 算法复杂度下界与实际选型因素凸包问题有一个重要的理论结论在比较模型下平面上n个点的凸包问题时间复杂度的下界是O(n log n)与排序同阶。这个下界可以通过归约证明——把排序问题转化为凸包问题如果凸包能快于O(n log n)排序也能快于O(n log n)。这意味着任何算法都无法在一般情况下超越n log n的复杂度Graham扫描和Andrew单调链正好达到这个最优界所以它们成为最常用的凸包算法。但实际选型不能只看理论复杂度还要结合数据规模和形态特征点集规模极大百万级且分布接近圆形Graham扫描和Andrew单调链都是O(n log n)哪个都行主要看实现难度和数据输入方式。点集规模大但凸包顶点数h远小于n比如所有点都在一个圆盘内部凸包只有少数几个顶点Jarvis步进的最坏复杂度是O(nh)此时表现可能优于O(n log n)算法。点集已经按x坐标排好序比如按扫描线顺序读取的点云Andrew单调链可以天然利用这个有序性减少一次排序的开销。需要动态维护凸包——不断插入、删除点每次查询凸包信息。这时静态算法都不适合需要上平衡树维护的动态凸包结构如Overmars-Van Leeuwen结构。实际干活的时候我绝大多数场景直接用Andrew单调链因为它避免了对极角的计算浮点误差来源之一只用叉积判断转弯方向实现短、稳定、好调试。后面我会详细展开说。2. 四大经典凸包算法逐一破解2.1 Graham扫描极角排序加栈式维护的教科书算法Graham扫描是1972年提出的算法也是绝大多数教材首选的凸包算法。它的核心思想很优雅先选一个基准点然后把其他点按相对基准点的极角排序最后用一个栈维护凸包顶点边走边“踢掉”造成右转的点。完整步骤如下在所有点中找到y坐标最小如果y相同取x最小的点作为基准点p0。这个点必然在凸包上因为它就是橡皮筋最下方的一个钉子。把其他所有点按与p0的极角从小到大排序。极角相同时距离p0近的点排在前面。将p0和排序后的前两个点压入栈。依次处理剩余每个点p设栈顶为b栈中次顶为a。如果a、b、p三点构成一个右转叉积小于等于0说明b不是凸包顶点将其弹出重复检查直到不再右转然后把p压入栈。处理完所有点后栈中保留的点就是逆时针顺序的凸包顶点。判断左转还是右转用叉积公式设向量ab (bx-ax, by-ay)向量bp (px-bx, py-by)叉积cross ab.x * bp.y - ab.y * bp.x。cross 0是左转cross 0是右转cross 0是共线。Graham扫描需要排序所以整体复杂度是O(n log n)排序是主项扫描阶段只有O(n)。这个算法有一个容易踩坑的地方极角排序时角度相等的处理。如果有多个点与p0的极角相同只保留距离最大的那个点因为距离较近的点会被凸包边界“遮住”不可能成为凸包顶点。但很多实现反而在排序后处理共线点时不干净导致结果里出现多余顶点。我建议在排序时就按“极角优先、距离次之”排好扫描的时候遇到共线直接弹栈。2.2 Andrew单调链不涉及角度运算的稳定实现Andrew单调链算法也叫Andrews Monotone Chain是我个人最推荐的一个版本它避开了极角计算只需要对点按x或y坐标排序然后分别构造凸包的下链和上链最后拼接。复杂度同样是O(n log n)。步骤拆开讲对所有点按x坐标从小到大排序x相同时按y从小到大排。构造下链从左到右遍历所有点把点依次加入凸包链。每加入一个新点检查链尾三个点是否构成左转如果不是左转叉积小于等于0就删掉链尾点直到满足左转条件。这个操作和Graham扫描里的弹栈一样。构造上链从右到左遍历所有点执行同样的“维护左转”操作。下链和上链合在一起去掉首尾重复的点就是完整的逆时针凸包。为什么叫单调链因为整个算法把凸包拆成上下两条“单调”的折线下链上所有点的x坐标单调递增同时链的方向始终保持左转或右转上链从右往左同理。Andrew单调链相比Graham扫描省去了极角排序直接从排序好的坐标出发浮点数计算量更少误差更小代码也更短。处理共线点非常方便你可以在判断时用“小于等于0”弹栈这样结果只保留凸包真正的转折顶点共线上的点全部被剔除如果你想保留边上所有点比如后续需要用到边上点做插值就改成“小于0”只弹右转不弹共线。C实现非常简洁我平时的模板如下#include bits/stdc.h using namespace std; struct Point { double x, y; Point operator-(const Point p) const { return {x-p.x, y-p.y}; } bool operator(const Point p) const { if (x ! p.x) return x p.x; return y p.y; } }; double cross(const Point a, const Point b) { return a.x * b.y - a.y * b.x; } // 叉积判断o-a和o-b的旋转方向 double cross(const Point o, const Point a, const Point b) { return cross(a-o, b-o); } vectorPoint convexHull(vectorPoint p) { if (p.size() 1) return p; sort(p.begin(), p.end()); vectorPoint hull; // 下链 for (int i 0; i (int)p.size(); i) { while (hull.size() 2 cross(hull[hull.size()-2], hull.back(), p[i]) 0) hull.pop_back(); hull.push_back(p[i]); } // 上链 int lower hull.size(); for (int i (int)p.size()-2; i 0; i--) { while ((int)hull.size() lower cross(hull[hull.size()-2], hull.back(), p[i]) 0) hull.pop_back(); hull.push_back(p[i]); } hull.pop_back(); // 去掉重复的最后一个点 return hull; }注意下链第一次循环遍历了全部n个点上链从下标n-2开始遍历到0没有重复处理排序后最后一个点。最后一步弹出重复点这样返回值恰好是顺时针或逆时针的凸包顶点列表不包含起点的重复闭合点。2.3 Jarvis步进像缠线一样一次次“寻找最外侧点”Jarvis步进又叫礼物包裹算法Gift Wrapping的思路和人的直觉最接近。想象你用一根绳子系在凸包最左下角的点然后拉住绳子另一端沿某个方向旋转绳子先碰到哪个点哪个点就是下一条边的终点。这个过程不断重复直到回到起点。具体实现是找到最左下角的点p0y最小y相同时x最小它显然是凸包顶点。设当前点为p_cur寻找“下一个点”p_next使得所有其他点都在向量(p_cur - p_next)的左侧。如果有多个点共线选择距离p_cur最远的那个。将p_cur更新为p_next循环直到回到p0。这个算法的时间复杂度是O(nh)其中h是凸包顶点个数。最坏情况是h n比如所有点都在一个圆上复杂度退化为O(n^2)比Graham扫描差。但如果h远小于n比如几千个点最后凸包就三五个顶点Jarvis步进的速度会非常快实现也简单适合交互式场景。我在处理某些特殊点云时会用Jarvis步进因为它的增量特性很好理解也方便在计算过程中实时展示当前找到的凸包边缘线。但正式项目里用得少毕竟h通常不会太小而且每次寻找下一个顶点都要遍历所有点常数项比较大。2.4 分治法和快速凸包并行友好但常数大的选项分治法求凸包和归并排序的思路一脉相承把点集按x坐标分成左右两半分别求两半的凸包再把两个凸包合并成一个。合并过程比较关键要从左凸包和右凸包中找出“连接”两个凸包的上切线upper tangent和下切线lower tangent删除切线之间那部分内部凸包边把两条切线连接到一起形成一个完整凸包。求切线可以分别从左凸包最右点出发逐步调整直到满足所有点在切线的同一侧。分治法的复杂度是O(n log n)和Graham、Andrew一样。它的优势在于天然适合并行化——左右两个子问题可以同时计算。但这个优势在普通场景下体现不出来因为单机顺序执行的常数比较大而且合并阶段的切线查找写起来要小心容易出bug。快速凸包QuickHull则模仿快速排序从最左最右两点连一条线找出直线两侧最远的点递归地处理两侧的点集。平均复杂度O(n log n)最坏退化到O(n^2)和快速排序一样存在“选点不当导致性能崩溃”的问题。实际工程中我不太推荐理论爱好者可以当思考练习。3. 实战进阶几何细节与实现陷阱3.1 叉积判断方向理解所有凸包算法的“心脏”不管哪种凸包算法核心操作其实就是叉积判断三个点的转向关系。你把这个搞懂所有算法都通了一半。叉积的数值定义给定起点o向量oa (ax-ox, ay-oy)向量ob (bx-ox, by-oy)叉积 a.x * b.y - a.y * b.x。这个值的含义是从向量oa旋转到向量ob是有向面积的两倍。叉积 0从oa到ob是逆时针旋转也就是左转。在一个凸包里按逆时针方向走每一步都应该左转。叉积 0右转。如果按逆时针维护凸包时出现右转说明中间那个点凹进去了不是凸包顶点应该弹栈。叉积 0三点共线。这个情况要额外谨慎是无数bug的源头。实际写代码时我推荐用Graham和Andrew的原理但把它们统一成“按逆时针遍历时叉积必须大于0”的维护逻辑。这样不容易记混。3.2 共线点与重复点绝大多数实现偏差的来源共线点怎么处理直接决定了凸包顶点数是否“纯净”。面试和竞赛题通常要求凸包顶点集合里不包含共线点也就是删除所有在凸包边中间的点。做法就是在弹栈判断时用“ 0”当新点使得栈顶元素右转或共线就弹栈。但如果你的应用恰好想保留边上所有点——比如有些点云处理项目需要知道凸包边上的全部激光点那判断条件就用“ 0”这样只有右转才弹栈共线点全部保留。注意这个改动会导致凸包顶点数增加算法复杂度和结果形状都不同。重复点也很坑。输入的二维点集里可能有坐标完全相同的情况排序后处理起来容易让叉积变成0干扰判断。最保险的方式是在排序后先做一次unique去掉坐标重复的点再进行后续计算。C里可以在排序后用unique和erase配合Point结构体重载运算符实现sort(p.begin(), p.end()); p.erase(unique(p.begin(), p.end()), p.end()); if (p.size() 2) { // 点集过小直接返回后续判断内部还是边上会退化 }3.3 浮点误差与EPS阈值工业级代码的真实痛点几何算法里浮点误差是最隐蔽的杀手。理论上三点共线的叉积计算结果应该是0但浮点运算下结果可能是1e-18这样的微小值。如果你直接用“ 0”判断程序行为会变得不稳定同一个点集在不同机器上可能得到不同结果。工业级代码的标准姿势是引入EPS阈值const double EPS 1e-10; int sign(double x) { if (fabs(x) EPS) return 0; return x 0 ? 1 : -1; } // 叉积判断方向 int dir sign(cross(hull[hull.size()-2], hull.back(), p[i])); if (dir 0) hull.pop_back();这样即使结果落在0附近的一个小邻域内也会被当作共线处理算法行为更可预测。EPS的取值不是死的我用1e-10在多数64位double运算下够用如果数据坐标范围特别大比如天文数字级别EPS要相应调大否则相对误差会被放大。还有一点尽量全程使用double不要用float做中间计算后转double。混合精度会引入不可控的舍入误差问题极难排查。我以前有个项目用float存点云坐标到了合并点云片段的时候凸包偶尔会多出几个碎点查了很久才发现是坐标存储精度不足换double就好了。3.4 特殊输入场景处理稀疏点集和同心点集当点的数量是0、1、2时凸包定义比较微妙。空集直接返回空单点返回该点两个点返回包含这两个点的线段。Andrew单调链在点数量少于3时会返回不正确的结果所以必须加前置判断。还有一个容易被忽略的情况所有点共线。这时候凸包按理论定义是一条线段凸包顶点应该是首尾两点或者依据应用需求保留所有共线点。如果按照“ 0弹栈”的写法最后返回的hull会把所有点都弹掉只剩下两个端点这其实是正确结果。但如果你期望返回一条完整线段上的所有点就要改用“ 0”的写法。务必根据需求提前定好策略。同心圆式分布的点集也是经典坑。所有点均匀分布在一个圆上凸包就是整个圆上所有点h n。任何O(n log n)算法在这里都是“最坏但可接受”的表现Jarvis步进则完全退化。如果遇到这类数据且性能敏感不要用Jarvis步进。4. 凸包算法的真实落地场景与实际操作4.1 点云凸包激光雷达与物体边界提取搜索热词里出现的“点云凸包”是我特别想展开的场景。激光雷达扫描树木、建筑物、人体探头返回的是几千到几百万个三维点。很多应用的第一步就是求这些点的二维凸包来提取目标的轮廓信息。举个例子我们要统计一棵树的冠幅先让激光雷达扫描树木截取某个高度的水平切片得到一个二维点云集合。对这些点求凸包凸包的周长和面积就能估算树的冠幅。这个流程我在林业遥感项目里用过效果很直观。点云凸包在三维空间也有直接对应版本——三维凸包。三维凸包是一个多面体比二维复杂一些。常见算法是增量法每次插入一个点更新当前凸包多面体。实现比较复杂一般直接调第三方库比如CGAL。大多数实际工作里人们仍然会把三维问题投影到二维平面来处理因为二维凸包稳定、快速、好控制。在点云处理中还有一点值得注意点云往往带有噪声。离群点会成为凸包的“钉子”直接扩大凸包范围导致面积估算偏大。我在处理激光点云时一般先做统计滤波Statistical Outlier Removal剔除离群点后再求凸包结果会可靠很多。4.2 图像轮廓分析与凸缺陷检测来自计算机视觉的经典操作OpenCV里有个函数叫convexHull专门用于求图像轮廓的凸包配合convexityDefects可以找到轮廓上的凹陷区域。手部识别、手势检测、物体抓取分析之类的基础视觉用法大多依赖这个组合。一张图怎么用流程大致是读取图像转灰度二值化分割前景用findContours找到轮廓再用convexHull求轮廓的凸包最后用convexityDefects找出凹陷点。凸缺陷的深度和角度可以识别手势——比如手张开时五个指尖形成凸包顶点指缝间的凹陷就是凸缺陷握拳时凸缺陷数量少得多。这种识别方法不依赖训练数据简单场景下效果稳定。我最初用OpenCV处理AED训练器的电极片位置时也遇到过需要求金属片凸包的情况。轮廓点数量动辄上千直接拿所有轮廓点做几何运算开销很大先求出凸包能极大地压缩计算量后续判断点在凸包内外就很快。4.3 碰撞检测与包围盒优化从游戏到机器人规划在机器人运动规划、自动驾驶、游戏物理引擎里凸包常被用作碰撞体的简化表达。一个复杂的汽车底盘模型可能有几千个三角面片直接做碰撞检测非常昂贵。但如果先对模型所有顶点求三维凸包把碰撞体简化为一个凸多面体两个物体是否碰撞就可以用分离轴定理SAT快速判断计算量直线下降。二维场景也一样。无人机在二维平面路径规划时可以把障碍物用凸包近似然后用几何方法判断路径段是否穿越障碍区域。相比原始点集凸包让“点在多边形内”的判断从O(n)变成O(log h)路径规划算法每轮要判断成千上万次这个优化非常可观。GIS和地图导航中还有一类应用对行政区边界、湖泊轮廓、建筑占地做简化。原始边界可能有几十万个点凸包能得到多边形概貌叠加上Douglas-Peucker算法还能进一步压缩顶点数量。虽然“凸包”损失了凹部细节但在画小比例尺图时凸包简化结果一般够用而且非常干净。4.4 旋转卡壳与直径问题凸包之后还能干什么算完凸包后最常见的后续操作是旋转卡壳Rotating Calipers——它用来求凸多边形的直径、宽度、最小面积外接矩形、最近远点对等。最远点对问题一句话概括平面内n个点求距离最大的两个点。暴力是O(n^2)但先求凸包再旋转卡壳就能到O(n log n n) O(n log n)而且旋转卡壳本身只扫一圈。这个场景很容易让人们忽略很多初学者以为凸包只是找到轮廓就结束了其实凸包是很多计算几何问题的“前置加速器”。平面上求两点间欧氏距离最大值其实就是在凸包直径上找最小外接矩形是凸包的一个边贴着矩形边转一圈得到的最优解求最大空格Largest Empty Circle也和凸包有关。知道这些你就能在面试或项目里把凸包灵活当工具用。5. 常见问题速查与调试实录5.1 症状总结与解决方案对照结合实际调试经验我把凸包计算中常见的故障现象和原因整理成一张速查表方便遇到问题时快速定位问题现象可能原因解决方案凸包结果缺了某个明显外凸的顶点排序规则写错导致扫描顺序不对核对Andrew单调链的x、y排序以及Graham扫描的极角排序稳定性凸包多边形自交或乱套排序函数不稳定或共线点处理策略不一致排序加上比较函数严格的不变式unique重复点后再处理点数量小于3时崩溃或返回空缺少前置判断对n0、1、2的情况单独处理结果里出现非常接近但不完全共线的小锯齿边浮点误差引入EPS阈值叉积判断用sign函数包起来运行很慢大数据集卡顿算法选型不对比如h接近n时用了Jarvis步进换成O(n log n)的Andrew单调链或Graham扫描凸包方向是顺时针程序里期望逆时针没有统一方向约定统一使用逆时针必要时在末尾reverse凸包顶点过多共线点没被剔除弹栈条件写成 0而不是 0根据需求选择“保留边上点”或“纯转折点”策略表中最后一条在实践中最常见。很多人从网上抄代码时不注意符号直接导致结果比预期多一堆点。如果你只是想输出凸包的顶点用于边界面积计算用“ 0”几乎总是对的。5.2 实测调试过程回放从崩溃到稳定的三分钟我说一个自己印象很深的调试过程。某次做点云作业写了Andrew单调链用几千个随机点测试一开始结果总是怪怪的凸包多出一条“横穿内部”的线。我打印出排序后的点集合才发现Point结构体里的比较函数写错了我只比较了xx相同时没有继续比较y。结果x相同的点顺序不稳定导致下链构建时栈顶判断依赖了不确定的顺序。这个问题很好地说明了“比较函数必须定义全序关系”的原则。所谓全序就是任意两个元素必须能比较出确定的大小不能存在“相等”却不给出相同优先级的情况。对于二维点比较函数应该先比较x再比较y或者先按y再按x。无论如何都必须两级比较缺一不可。另一个典型的调试问题是坐标范围过大导致的EPS失效。点坐标是从传感器原始读数来的数量级在1e5左右此时double的机器精度相对值大约是1e-16用1e-10做阈值还可以若坐标放大到1e8甚至1e12原来的EPS就太小浮点误差可能超过1e-10导致共线判断失效。解决办法是让EPS随坐标范围缩放或者做坐标归一化后再求凸包。我通常先把所有点平移到原点、缩放到单位尺度内计算完再变换回去这样EPS稳定可靠。5.3 凸包算法的面试考察点与典型变形算法面试里凸包出现的频率不低。面试官考点一般集中在能否准确说出几种算法的复杂度和适用条件。能否解释叉积判断方向的原理。能否写出Andrew单调链的简洁代码。能否应对退化输入重复点、共线点、少点输入。变形题也常有。比如“给你n个点动态删除一个点后问新凸包是什么”这类题静态算法做不了需要预处理求出每个点删除后对凸包的影响。思路是如果删除的点不是原凸包顶点凸包不变如果是凸包顶点消息需要把被挡住的新点“补上来”。一种做法是对每个凸包顶点预先找到它两侧邻近的内部点删除时再用局部点集重新求凸包。这类问题考的是对凸包结构细节的理解不是算法背诵。另一种变形是求三维凸包比如判断空间点集的凸包是否包含原点。三维凸包没有Graham扫描那么简单的解法不过我们可以把三维点投影到二维做剖面分析或者直接用增量法维护三维凸包。竞赛中关键是会调用模板理解原理即可。5.4 大数据量点集凸包的性能优化实践当点的数量达到百万级以上O(n log n)的常数项也会成为瓶颈。我能给出的优化经验是这样的第一用C写避免使用动态vector反复push/pop导致的内存分配开销。可以预分配一个大小为n的数组只用索引移动。排序用标准库sort它的优化已经很好了。第二如果数据有结构性比如按栅格扫描顺序获取的点云可以尝试分段凸包再合并。把点集按x坐标分成若干段每段求凸包再把段的凸包顶点合并成最终凸包。这个思路就是分治法的实用版分段可以并行处理最后合并的复杂度依然是O(n log n)但常数更小。第三跳过明显不可能是凸包顶点的点。有一种俗称“快包排除法”的技巧先随机采样一部分点求凸包然后对剩余点判断是否在这个小凸包内在内直接丢弃。重复几次后就剩下很少的候选点了再对这些候选点跑完整的Andrew单调链。这个技巧对均匀分布的点集效果奇佳可能只需要检查原数据量的5%~10%的点。不过要实现得小心第一次采样得到的凸包不一定是原始点集的凸包子集所以不能绝对地丢弃外部不可能点之外的内部点更安全的是只把它当作预处理最终还是要跑一次完整算法。最后提一个更实际的经验如果项目的凸包计算频率很高但点集变化不大可以考虑缓存排序结果和上次凸包顶点索引。当有新点加入或删除时只增量更新而不是每次全部重算。这个在交互式GIS系统和在线点云处理场景里很实用。写在最后从凸包开始的计算几何修行我最初学凸包是为了处理点云当时翻了很多资料似懂非懂后来踩了无数坑才把Graham扫描和Andrew单调链烂熟于心。现在遇到任何几何问题我第一反应都是能不能先求个凸包把问题规模缩小这个思路帮我在很多项目里省下大量计算时间。最后再分享一个小技巧调试凸包算法时一定要养成可视化测试的习惯。用matplotlib或者OpenCV把随机点集和凸包画出来肉眼看一眼很多逻辑错误当场就能发现比打印一百行中间变量都高效。我到现在写计算几何代码仍然会先可视化再谈性能优化。