帮你处理过这么一类需求游戏里有几十个散落的资源点策划想在地图上画一个高亮范围把它们全包进去还要求这个范围尽量贴合、不要留太多无关的空白区域。第一次听到这个需求时我先想到的是最小覆盖矩形但点一旦斜着分布矩形就会空出一大片无意义区域。后来我把方案换成了凸包——把所有点围起来的那个最小的凸多边形——效果一下就对了。这个看起来直接、却不容易一次写对的经典问题就是计算几何里的凸包问题而 Graham-Scan 算法是我个人推荐优先理解和实现的第一个凸包解法。这篇分享面向刚接触计算几何的开发者或者做过一些算法题但一直对凸包实现没把握的人。我会把原理、完整代码、边界条件和常见坑都过一遍最后聊聊从凸包继续延伸出来的旋转卡壳等进阶思路让你不只学会调一个模板还能搞清楚每一步为什么这么做。1. 凸包是什么从橡皮筋到最小凸多边形1.1 钉钉子与橡皮筋的直觉模型纸上钉一排钉子拿一根橡皮筋把所有钉子套住然后松手。橡皮筋会自动收缩最终贴住最外圈的一批钉子形成一圈紧绷的多边形。这个多边形就是点集的凸包。这个例子几乎每个讲凸包的教程都会用因为它不仅形象还直接说出了凸包的两个本质它把所有点都包在内部或边界上它是最小的任何一条边都不会被更靠外的点撑得更远。从数学上给定义平面有限点集 S 的凸包是包含 S 的最小凸集。所谓凸集直观理解就是集合内任意两点连成的线段仍完全落在集合里。对离散点来说这个最小凸集最终一定是一个凸多边形顶点来自原来的点集不会凭空产生新点。这一点在工程里特别重要——凸包顶点可以直接对应回原始坐标数据后续做碰撞检测、贴图包围盒、路径规划时都不用重新插值。1.2 现实场景里哪里需要凸包凸包离实际开发并不远。我随手就能列出几个典型场景碰撞检测游戏里给不规则物体生成一个凸包作为物理碰撞体比直接用凹多边形或逐像素判定省大量计算。很多物理引擎对凸体的碰撞检测算法都极其友好。图像与点云轮廓提取从边缘检测点或激光雷达点云里求凸包可以快速拿到目标的大致包围轮廓再做形态分析。地图与地理围栏多个兴趣点或定位信号点需要画一个覆盖范围时凸包是范围最小但覆盖所有点的经典答案。数据可视化聚合对散点图求凸包后填充半透明色块能直观展示多类数据的分布边界。凸包也经常作为高级几何算法的前置步骤。比如旋转卡壳求点集最大距离、求最小外接矩形、判断点是否在多边形内部等都要先有一个凸包。所以入门计算几何时凸包往往是第一个必须啃下的硬骨头而在工程里它又是一个低投入高回报的工具。2. Graham-Scan 算法原理极角排序 单调栈2.1 基准点的选择为什么能保证正确Graham-Scan 的整体思路是先选一个必然在凸包上的点作为基准把所有点按相对基准点的极角排序然后按极角顺序扫描用栈维护当前已经确认的凸包顶点。第一步是选基准点。最简单的策略是选 y 坐标最小的点如果有多个 y 相等再选 x 坐标最小的。为什么这个点一定在凸包上因为它是整组点里最下方的点任何包含全部点的凸多边形都必须把它包含进边界否则就无法覆盖到它。用最值确定的点不需要额外验证一定合法。选好基准后把所有其他点按极角从小到大排序。排序完成后从基准点出发连向这些点的射线就像一把均匀张开的扇子。扫描扇子上的点每个点只被考虑一次不回头、不重复这是算法高效的根基。2.2 排序比较叉积优先于 atan2最直白的极角排序方法是调用 atan2 算出每个点的角度再排序。但我建议代码里不要这么做有两个原因一是 atan2 是浮点运算坐标值一旦很大精度误差就可能让排序结果在共线点之间抖动二是浮点数比较本身不如整数稳定碰到需要严格区分共线顺序时会很痛苦。更稳的方法是直接用叉积判断两个点的相对方向。设基准点为 P0待比较的两个点为 A 和 B向量 P0A 与 P0B 的叉积定义为cross(P0, A, B) (A.x - P0.x) * (B.y - P0.y) - (A.y - P0.y) * (B.x - P0.x)这个值的几何意义是从 P0A 旋转到 P0B 的有向面积。如果结果大于 0说明 A 到 B 是逆时针方向B 的极角比 A 大A 应排在 B 前面结果小于 0 则相反结果等于 0 说明 P0、A、B 三点共线此时按距离排序让离基准点近的排前面即可。叉积计算只用加减法和乘法如果输入是整数坐标整个过程可以保持为整数比较彻底避开浮点误差。这是我在实现里优先选叉积而不是 atan2 的根本原因。2.3 扫描与左转保留、右转弹出的几何含义排序结束后进入主扫描过程。维护一个栈先把基准点和排序后的第一个点压入然后依次处理剩余的点。每加入一个新点 C看栈顶元素 B 和栈顶前一个元素 A计算 cross(A, B, C)叉积大于 0A → B → C 是左转逆时针B 仍然可能是凸包顶点保留叉积等于 0三点共线。如果要求严格凸包顶点则弹出 B如果允许凸包边上有原始点则保留叉积小于 0A → B → C 是右转顺时针说明 B 是一个凹进去的点必然不在凸包上直接弹出 B。弹出后还要继续用新的栈顶检查直到栈里只剩两个点或叉积不再为负为止。扫描完全部点后栈里留下的就是按逆时针顺序排列的凸包顶点。这个过程的几何直觉是扫描时维护的是一条局部凸链。极角排序使得后到的点只会把边界往外撑所以一旦出现右转当前栈顶就是被新边界越过的旧点删除它是安全且必要的。这种排序 单调栈的组合正是 Graham-Scan 能做到 O(n log n) 的核心原因。3. 完整可运行的 Python 实现与逐行注释3.1 数据结构与基础函数我用最朴素的 tuple 表示坐标点用两个基础函数完成所有几何判断。这样的代码既适合学习也方便后面移植到其他语言。from functools import cmp_to_key P0 None # 全局基准点供比较器使用 def cross(o, a, b): # 计算向量 oa 与 ob 的叉积 return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) def dist2(a, b): # 两点距离的平方只用于排序和共线判断不需要开根号 return (a[0] - b[0]) ** 2 (a[1] - b[1]) ** 2选择 tuple 而不是自定义 Point 类是为了让去重和排序更直接。set可以直接对 tuple 去重比较器也只要按下标访问坐标。工程上如果追求可读性封装一个 Point 类完全没问题核心逻辑不变。3.2 排序比较器怎么写cross(P0, a, b) 0时a 极角小于 ba 应排在 b 前面。cross等于 0 时按距离从近到远排这一点在后续处理共线点时会影响最终是否保留边上的点。def cmp(a, b): c cross(P0, a, b) if c 0: return -1 if c 0: return 1 d dist2(P0, a) - dist2(P0, b) if d 0: return 1 if d 0: return -1 return 0Python 的functools.cmp_to_key可以把这种老式比较器转成排序用的 key 函数。之所以不直接算角度排序就是上文说的精度和稳定性考虑。3.3 主循环与测试样例主函数里我加了一个keep_collinear参数用来控制共线点的去留。keep_collinearFalse表示只保留凸包顶点keep_collinearTrue表示凸包边上原有的点也一并保留。这两种需求在算法题和工程里都经常遇到用一个参数区分开最方便。def graham_scan(points, keep_collinearFalse): global P0 # 第一步去重。重复点在凸包问题中没有任何作用 points list(set((x, y) for x, y in points)) n len(points) # 点数太少时直接返回 if n 2: return points[:] # 第二步找基准点y 最小y 相同取 x 最小 P0 min(points, keylambda p: (p[1], p[0])) # 第三步其余点按相对基准点的极角排序 rest [p for p in points if p ! P0] rest.sort(keycmp_to_key(cmp)) # 第四步扫描使用栈维护凸包顶点 stack [P0, rest[0]] for p in rest[1:]: if keep_collinear: # 共线点也保留在凸包边上只有右转才弹出 while len(stack) 2 and cross(stack[-2], stack[-1], p) 0: stack.pop() else: # 只保留凸包顶点共线也不允许弹出 while len(stack) 2 and cross(stack[-2], stack[-1], p) 0: stack.pop() stack.append(p) return stack用一组包含共线点、三角形顶点和内部点的数据测试pts [(0, 0), (1, 0), (2, 0), (2, 2), (0, 2), (1, 1), (1, 2)] print(graham_scan(pts)) # 只保留顶点 print(graham_scan(pts, keep_collinearTrue)) # 保留边上所有点输出结果[(0, 0), (2, 0), (2, 2), (0, 2)] [(0, 0), (1, 0), (2, 0), (2, 2), (1, 2), (0, 2)]注意返回结果是从基准点 (0, 0) 开始、按逆时针排列的。不同实现的起点可能不同判断结果是否正确时一般看多边形顶点集合是否一致、顺序是否统一逆时针即可。4. 边界条件与踩坑实录共线、精度、退化场景4.1 keep_collinear 参数共线点的去留这是我在实际做题和项目里反复踩过的地方。同一个点集如果题目要求输出凸包上的所有点你就要把边上的原始点也算进去如果要求输出凸包顶点边界上的共线点要全部剔除。两种需求对应的扫描弹出条件完全不同差一个等号结果就差一层。我见过不少人把标准凸包模板直接用在要求共线点的题目上结果连续提交不过。排查到最后才发现不是算法错了而是对凸包边界的定义理解不一致。所以建议在代码里把keep_collinear做成参数而不是写死一个版本。keep_collinearTrue时还要注意排序方向。我的比较器里共线点按距离从近到远排序这样扫描时同一条边上的点会按顺序依次进栈不会被过度弹出。如果反向排序边上的点顺序就会乱掉。4.2 浮点坐标与整数坐标的精度问题坐标是整数时叉积结果一定是整数整个算法不需要处理浮点误差这是最理想的情况。算法竞赛里的大部分凸包题也是整数坐标。但如果坐标来自浮点计算比如图像坐标归一化、雷达点云坐标叉积结果就是浮点数比较时就得引入一个极小量 epsilon比如cross -1e-12才认为右转cross 1e-12才认为左转否则视为共线。另一种常见问题出现在坐标值极大时。C 里如果坐标是 1e9 量级叉积中间结果能达到 1e18接近 64 位整数的上限直接相乘可能溢出。稳妥做法是用long long并进行符号判断必要时先平移坐标或压缩比例。Python 的整数没有溢出问题所以我更喜欢在算法验证阶段用 Python 把结果跑透再移植到 C 或 Rust。4.3 输入去重、全共线、点数少于 3 的处理三个容易忽略的退化场景重复点如果输入里同一个坐标出现多次不去重的话排序和扫描阶段可能出现重复顶点甚至影响叉积判断。实现第一步先用set去重成本低收益大。全部点共线此时凸包严格意义上是一个退化多边形。按keep_collinearFalse扫描最后栈里会只剩两个端点按keep_collinearTrue则所有点都保留。这两种结果都算合理具体取哪种看业务需求。我在处理地图围栏时通常只保留两个端点一条线段就够了。点数少于 3一个点就是它自己两个点就是一条线段。不是每个资料都会提醒这点忘了处理会在边界数据上报错。另有一个操作习惯写凸包前先在纸上画一组包含共线点、凹点和内部点的测试数据把哪些点应该留在凸包上先标出来再对着代码验证。这一步看着简单却能省下大量定位逻辑 bug 的时间。5. 实测复杂度与同类算法横向对比5.1 Graham-Scan 的复杂度拆解Graham-Scan 的总复杂度是 O(n log n)主要开销在排序。去重和找基准点都是 O(n)扫描阶段每个点进栈一次、出栈至多一次均摊 O(n)。所以当 n 从 1e4 涨到 1e6 时实际耗时增长主要受排序主导整体依然在可接受范围内。我用 Python 在个人笔记本上跑随机均匀分布的点集1e4 个点耗时几十毫秒量级1e6 个点也就几秒量级瓶颈基本在排序本身。扫描部分的常数很小因此对绝大多数应用来说凸包计算都不是瓶颈。真正需要关心的是后续可能要做的 O(n log n) 以上复杂度的操作比如动态凸包维护。5.2 与 Andrew 单调链、Jarvis 步进的选择建议虽然 Graham-Scan 是经典但我得说句实在话现在竞赛里很多人首选的是 Andrew 单调链。它的思路是按 x 坐标排序然后分别求下凸壳和上凸壳整个过程只需要比较叉积不需要极角排序实现更不容易踩精度坑。那么为什么还要学 Graham-Scan我的看法是Graham-Scan 的极角排序 单调栈思想是理解凸包的钥匙。很多计算几何问题比如旋转坐标系、点定位、动态凸包都会用到极角排序这个基础操作。你把 Graham-Scan 吃透了再看 Andrew 会非常轻松。再提两个其他算法方便你做选型算法时间复杂度特点适用场景Graham-ScanO(n log n)思路直观需要极角排序学习首选理解凸包本质Andrew 单调链O(n log n)按 x 排序实现简单精度稳工程和竞赛常用推荐Jarvis 步进礼品包装O(n h)h 为顶点数实现最简单凸包顶点数远小于点总数时暴力枚举边O(n^3)仅理论参考不推荐但适合验证小数据我自己的选型习惯是算法题里直接用 Andrew因为它对边界的控制更干净但如果需要给读者讲清凸包的几何含义我会先用 Graham-Scan 铺路。实际项目里如果点集规模不大且需要动态插入Jarvis 也未必不可用关键还是看凸包顶点的数量级。6. 从凸包继续延伸旋转卡壳与更多几何算法6.1 用旋转卡壳求最大直径凸包之后最自然的一个进阶问题是给定平面点集求距离最远的两个点。一个直觉是最远点对一定出现在凸包顶点上不会出现在内部点之间。拿到凸包后再用旋转卡壳Rotating Calipers可以在 O(h) 时间内求出直径。思路是对凸包的每条边维护一个对踵点——即到当前边所在直线距离最远的顶点。随着边沿凸包逆时针移动对踵点也只沿凸包逆时针移动因此可以用双指针维护。由于每个指针全程至多走一圈总复杂度是线性的。这个技巧的价值在于如果没有凸包最远点对朴素做法是 O(n^2)n 大到一定程度就跑不动了。先 O(n log n) 求凸包再 O(n) 旋转卡壳整体 O(n log n)这是计算几何里非常典型的降维打击思路。6.2 凸包在点集分析中的延伸思路掌握了凸包之后还有很多延伸方向最小外接矩形凸包 旋转卡壳可以求出面积最小的外接矩形在碰撞体生成、OCR 字符矫正里很常见。点是否在凸包内对凸包顶点按角度建立索引后可以在 O(log n) 时间内判断一个点是否在凸多边形内部比逐边判断快一个量级。合并两个点集的凸包可以在已有两个凸包的基础上线性合并出新凸包这在分布式点云合并场景很实用。动态凸包当点集支持在线插入或删除时需要用平衡树等结构维护凸包复杂度上升到 O(log^2 n) 级别。这些进阶算法都以今天这篇的叉积、极角排序和凸包扫描为基础。把基础打牢后面看任何计算几何资料都不会发怵。最后分享一个我自己的习惯代码模板里永远把cross和dist2作为基础函数单独存起来因为旋转卡壳、点定位、判断线段相交都会反复用到它们。另一个建议是写凸包之前先把边界情况列清楚——全共线、共线点去留、浮点 epsilon——再动手写主逻辑。我早期好几次调了半天 bug最后发现问题就出在这些看起来不值一提的地方。