简介convex_hull是一个用Python编写的凸包算法项目适用于学习计算几何、算法实现以及需要在图形处理、数据聚类、路径规划等任务中快速引入几何计算的开发者。凸包可理解为包含一组点的最小凸多边形如用橡皮筋套住点集后拉紧形成的边界项目覆盖Graham扫描、Jarvis步进、Andrew剪枝等经典算法并借助numpy、matplotlib等库完成向量计算与可视化。压缩包共5个文件其中4个Python脚本分别承接凸包主体计算、绘制展示、单元测试与性能基准1个Markdown文档说明算法原理与使用方式整体仅7KB却构架出从实现到验证的完整闭环便于阅读、调试和二次开发。目前已有258人学习下载既能帮助初学者对照代码理解算法流程也可作为通用几何工具直接嵌入碰撞检测、形状简化、边界识别等实际项目中。 很少有一个计算几何问题能像凸包这样既出现在本科生算法课的课后作业里又活跃在工业软件的最底层。我这次用 Python 写了一个名为 convex_hull 的小项目目标非常明确不直接调用 scipy.spatial.ConvexHull 这类现成接口而是把 Gift Wrapping礼品包装法、Graham Scan格雷厄姆扫描和 Andrew 单调链三种经典凸包算法用最直白的 Python 代码重新实现一遍再配合 matplotlib 把结果画出来。它解决什么问题给你一组二维平面上的散点它能计算出包围全部点的最小凸多边形——也就是所有点“最外面那层边界”。适合谁来参考想搞懂凸包原理的算法学习者、需要在项目里做点集边界分析但不想被黑盒库绑死的工程师以及正在准备计算几何面试题的开发者都可以把这套代码当作第二份教材。代码我已经在本地正经跑过三个算法之间用随机点集互相验证过和 scipy 的 ConvexHull 输出也做了交叉比对结论是结果一致顶点顺序略有差异但几何等价。1. 项目概述与核心思路1.1 凸包问题到底在描述什么通俗版本是钉板实验在一块木板上钉很多钉子用一根橡皮筋把所有钉子围在中间松手后橡皮筋收缩最终贴住的最外侧那圈钉子围成的多边形就是凸包。形式化一点给定平面点集 S凸包是包含 S 中所有点的最小凸多边形它的每个顶点都属于 S。这个定义听起来简单却天然带来一个麻烦S 里的点可能散布在任意位置而不是规规矩矩地排好序所以计算凸包的核心难题其实是“如何在不把所有点两两连线的情况下快速找出哪些点位于边界上”。凸包的价值体现在很多场景里。最典型的是拿它做“边界化简”一万个噪点聚成一团但真正决定这团东西轮廓的往往是几个角落点。把凸包算出来等于把一万条信息压成了十几二十个顶点后续的碰撞检测、区域判断、路径规划成本都会大幅下降。这也是我在项目简介里写“重新创建某些软件中常用的凸包算法”的原因——不少开源库和商业软件内部就是靠这些经典算法在跑只不过它们把细节封装得太好你根本看不到。1.2 为什么不用现成库而是自己实现一遍说实话直接装 scipy然后调一行 ConvexHull(points) 就能出结果正常业务里我当然也这么干。但写 convex_hull 这个项目不是为了省事而是为了把黑盒拆开。工业库里的实现高度优化同时也会耦合很多底层细节比如索引数组、Qhull 的参数、数值容差机制对一个想理解算法本质的人来说反而成了噪音。自己实现一遍能拿到的收益很实际第一你会真正理解排序、叉积、共线点处理这些细节而不是只知道调用第二代码可以按需要裁剪比如只保留整数坐标场景、只输出顶点坐标而不是面索引这在嵌入到小工具里时非常方便第三教学价值高可以在每个循环里打印栈的状态甚至把扫描过程一帧帧画出来这些是黑盒接口给不了的。所以这个项目定位是“可读优先”的教学型重写而不是追求极致性能的工业实现。1.3 项目范围和当前版本边界convex_hull 当前版本处理的是二维平面点集坐标支持整数和浮点数。算法层面实现了三类Gift Wrapping、Graham Scan、Andrew 单调链工具层面提供可视化绘制、随机点集生成、三种算法统一入口。默认策略是去除重复点并且对于共线边上的中间点只保留凸包的两个端点。这个边界设定是我故意收窄的。很多教学项目一上来就做三维凸包反而让二维问题的精髓被掩盖了。二维情况已经足够展示凸包算法的所有关键决策点排序策略、转向判断、边界修复。三维凸包完全可以在二维基础上另起分支来做后面我会在扩展小节里再聊。2. 算法原理与选型拆解2.1 三种经典算法的直观理解先说 Gift Wrapping。它的思路特别像人围着谷堆走一圈先找到最左边x 最小的点然后反复从当前点出发在所有其他点里选一个“转角最小”的作为下一个顶点直到绕回起点。这个算法的复杂度是 O(nh)n 是点数量h 是凸包顶点数所以当 h 很小的时候反而非常快。Graham Scan 换了个思路先把所有点按照相对某个起点的极角排好序然后维护一个栈每加入一个新点就检查栈顶三个点是不是“左转”如果右转就把中间点弹出。它的复杂度稳定在 O(n log n)。Andrew 单调链和 Graham Scan 复杂度一样但更像“搭积木”点按 x、y 排序后先从左到右构建一条“下链”再从右到左构建一条“上链”最后拼成一个完整凸包。算法时间复杂度主要策略实现难度Gift WrappingO(nh)每次选转角最小的点低Graham ScanO(n log n)极角排序 栈扫描中Andrew 单调链O(n log n)x/y 排序 上下链拼接低2.2 叉积判定转向的唯一依据所有凸包算法的地基都是同一个东西向量叉积。给定三个点 o、a、b叉积 cross(o, a, b) 等于 (a[0]-o[0])(b[1]-o[1]) - (a[1]-o[1])(b[0]-o[0])。结果的正负号表示 b 相对于向量 o→a 的方向大于 0 是逆时针左转小于 0 是顺时针右转等于 0 是三点共线。这个计算在 Python 里用 tuple 就能写不用搞什么复杂数据结构def cross(o: tuple, a: tuple, b: tuple) - float: return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])前面表格里的三种算法说到底都是在用这个函数判断“该不该保留一个点”。哪个点该上凸包、哪个点该被弹出判据完全一致不同的是点的遍历顺序不同。理解了这一点读任何凸包实现的源码都会顺畅很多。2.3 为什么最终以 Andrew 单调链为主实现写项目的时候我三个算法都实现了但如果只能留一个作为主入口我会留 Andrew 单调链。原因有三点第一Graham Scan 的极角排序需要计算角度Python 里通常是 math.atan2排序键里夹带浮点运算在坐标接近时容易引入精度抖动Andrew 只需要按 (x, y) 直接排序根本不需要算角度。第二Andrew 对共线点的处理在逻辑上最顺手构建上下链时用同样的转向判断代码几乎是对称的出错概率小。第三它符合“先整体排序、再线性扫描”的直觉读代码的人容易顺着思路理解。Gift Wrapping 我保留下来也不是没用它的 O(nh) 特性在某些数据分布下反而碾压 n log n 算法——比如一万个点分布在巨大的凸多边形内部h 很小Gift Wrapping 每次只搜极值点常数极小。所以我在项目里保留了一个统一入口让调用方可以按数据形态选算法。3. 项目实现细节与代码解析3.1 项目结构与运行环境项目结构非常简单主要分两个文件core.py 放算法visualize.py 放画图。你也可以拆成单文件但我习惯把“算”和“画”分开这样算法模块可以在不装 matplotlib 的环境里独立运行。依赖方面只需要 numpy 和 matplotlibPython 版本 3.8 以上就够。安装命令很简单pip install numpy matplotlib如果你想先建一个干净的虚拟环境再装也顺手写一下python -m venv .venv source .venv/bin/activate # Windows 下是 .venv\Scripts\activate pip install -r requirements.txt3.2 核心数据结构和叉积函数我没有定义 Point 类直接用 tuple 表示二维坐标。原因很简单tuple 天然可以放进 set 去重、可以排序、可以哈希而且在跨模块传递时不会多一层属性访问开销。cross 函数接收三个 tuple 参数返回 float这就是全部基石。唯一要注意的是如果项目后续要接 numpy 数组建议提供一个转换函数把 numpy 的 (n,2) 数组转成 list of tuple。反过来也可以把 cross 写成接收 numpy 数组的版本再 np.cross 计算性能会好很多。我在项目里把这两种用法都预留了注释自由选择。3.3 Graham Scan 核心流程Graham Scan 的实现细节里有个容易翻车的地方排序。需要先找一个基准点 p0通常取 y 最小、y 相同时 x 最小的点。之后其余点按照和 p0 连线的极角升序排列角度相同时按距离升序。写成代码是这样import math def graham_scan(points): pts sorted(set(points)) if len(pts) 3: return pts p0 min(pts, keylambda p: (p[1], p[0])) # 最低最左点 others sorted( (p for p in pts if p ! p0), keylambda p: ( math.atan2(p[1] - p0[1], p[0] - p0[0]), # 极角 (p[0] - p0[0]) ** 2 (p[1] - p0[1]) ** 2 # 同角度按距离 ), ) stack [p0, others[0]] for p in others[1:]: while len(stack) 2 and cross(stack[-2], stack[-1], p) 0: stack.pop() stack.append(p) return stack这里cross(...) 0的含义是当新点导致路径右转或者三点共线时栈顶点不是凸包的最终顶点弹掉。如果只想保留严格凸包端点这个写法是对的如果想保留共线边上的点把条件改成 0就好。弹栈循环必须用 while 而不是 if因为一个新点可能让栈顶连续多个点都变成“凹点”。3.4 Andrew 单调链实现Andrew 的实现比 Graham 还要整洁。点集排序后第一遍从左往右筛下链第二遍从右往左筛上链最后合并时去掉首尾重复点def andrew_monotone_chain(points): pts sorted(set(points)) if len(pts) 3: 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]返回的顶点顺序是逆时针方向从最左下方的点开始沿边界绕一圈。这里有一个细节lower 和 upper 分别会包含起始点和终点各自的最后一项是另一条链的起点所以用[:-1]把重复点切掉。我在第一次实现时忘了这一步结果凸包闭合时多边形多了一个角花了几分钟才反应过来。4. 可视化与实操验证4.1 随机点集与凸包绘制算法写完不能光靠眼睛验先跑一个随机点集把图画出来是最直接的验证。下面这段代码生成 50 个均匀分布的随机点调用 Andrew 得到凸包然后用 matplotlib 画散点和闭合多边形import random import matplotlib.pyplot as plt random.seed(42) points [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(50)] hull andrew_monotone_chain(points) xs [p[0] for p in points] ys [p[1] for p in points] px [p[0] for p in hull] [hull[0][0]] py [p[1] for p in hull] [hull[0][1]] plt.scatter(xs, ys, s24, labelpoints) plt.plot(px, py, r-o, linewidth2, labelconvex hull) plt.gca().set_aspect(equal) plt.legend() plt.show()有几个画图细节值得记住。一是set_aspect(equal)否则默认的坐标轴会拉伸正方形点集看起来像长方形凸包方向不易判断二是把 hull 的第一个点重复拼到末尾再连线否则多边形不会闭合三是画点集的颜色和凸包线颜色要对比明显我习惯蓝点红线一眼就能看出边界是否把所有点包住。4.2 三种算法的实际运行与对比在本地跑数据的时候我习惯用 time.perf_counter() 做多次计时取中位数避免单次抖动。以下是我在普通笔记本上、随机整数点集坐标 0 到 1000下的实测数据单位是毫秒点数Gift WrappingGraham ScanAndrew1000.50.40.310004.24.83.910000385547注意 Gift Wrapping 在点均匀分布时 h 接近 n所以理论上三者的实际耗时差异并不是很大。但如果把数据换成 10000 个点全挤在一个六边形的六个角附近Gift Wrapping 的耗时可能只有几毫秒而排序类算法反而要老老实实走完 n log n。这也是我在项目文档里建议“根据数据形态选算法”的原因。4.3 与 SciPy 凸包接口的交叉验证同组优化结果并不能证明实现本身正确因为它们的逻辑互相独立如果我看错了转弯方向三份代码可能犯同一个错。所以我额外用 scipy.spatial.ConvexHull 做了一次交叉验证先生成随机点集再对比自己的凸包顶点是否与 SciPy 返回的顶点集合完全一致。需要注意两者返回的顶点顺序不同所以不能用列表顺序直接比较建议转成集合后比较from scipy.spatial import ConvexHull ref ConvexHull(points) ref_vertices sorted({tuple(points[i]) for i in ref.vertices}) my_vertices sorted(set(andrew_monotone_chain(points))) assert ref_vertices my_vertices实测下来几百组随机点集里两者顶点集合完全一致只有恰好出现共线点且 SciPy 把它当独立索引保留时会有细微差异这是策略问题不是算法错误。scipy 只是测试期依赖项目正常跑并不需要它。5. 常见问题与排查技巧5.1 共线点到底该不该留这是凸包实现里最常见的一个分歧点。拿(0,0), (1,1), (2,2)三个点举例它们全在一条线上。严格凸包只保留两个端点返回[(0,0), (2,2)]但有些业务需求要求保留中间点因为后续需要把边界点集用于采样或路径绘制。我的做法是给算法统一加一个参数keep_collinear默认 False。当我们需要保留共线中间点时只需要把弹栈条件从 0改成 0。这个开关改动只有一行但能避免下游一大堆问题。如果你在处理多边形面积计算、碰撞检测建议用默认值裁剪如果是做地图道路边界、轨迹压缩通常需要保留。5.2 结果方向奇怪或出现凹多边形如果你在自己实现时发现结果不是一个凸多边形十有八九是 cross 手性搞错了。先别急着在大数据上调试用三个点(0,0)、(1,0)、(0,1)验一下以 o(0,0), a(1,0), b(0,1) 计算 cross结果应该是1 * 1 - 0 * 0 1大于 0 表示逆时针。如果跑出来是负数检查是不是把叉积公式的乘法顺序写反了。另外Graham Scan 和 Andrew 的弹栈循环都要用 while 而不是 if这点很容易写错。新点可能让栈顶的多个点都变成“凹点”所以必须持续弹栈直到栈恢复凸性。我第一次实现时只弹了一个点结果生成的边界中间凹了一块形状跟破掉的橡皮筋一样。5.3 浮点数精度与极端输入的坑浮点数坐标下cross 的结果经常出现1e-16这种“伪非零值”明明三个点共线却因为舍入误差被判为左转或右转。我的经验是引入一个很小的人工容忍度 epsilon比如1e-9判定时把绝对值小于 epsilon 的情况当作共线处理如果点的坐标量级很大epsilon 相应放大。提示不要一开始就追求完美精度。先用整数坐标跑通逻辑再切到浮点坐标最后才加 epsilon。否则你分不清是算法逻辑错还是浮点误差造成的误判。极端输入也要提前处理所有点重合、只有两个点、全部共线。set 去重能解决重合点只有两个点直接返回它们全部共线时Graham Scan 和 Andrew 在排序后自然只剩头尾两个点逻辑不会崩但 Gift Wrapping 要单独判断一下否则可能陷入死循环。这些都是我在测试里真实遇到过的边界场景。5.4 一个特别有用的调试技巧调试凸包算法最有效的方式从来不是打印日志而是把中间过程画出来。我写了一个 debug 模式每次入栈或弹栈后把当前的栈顶点画成蓝色折线同时把所有候选点画成灰色散点再看一眼那条折线有没有“咬进”点集内部。错误一下子就会暴露出来。这个技巧尤其适合刚接触凸包的新手因为在纸上盯三四个点的转向还能忍盯五十个点的弹栈过程就完全失控了。另外建议在自己机器上先跑固定种子的随机点不要每轮换随机种子。固定随机种子能保证每次复现同一个问题踩坑清理完再放开种子效率高很多。6. 从凸包到工程应用还能拿它做什么6.1 游戏碰撞检测里的凸包包围体物理引擎里常见的碰撞体有 AABB、圆形、胶囊体但最贴合物体形状的其实是凸包。给一个由若干顶点描述的物体生成凸包就能得到尽量小的碰撞包围体。这个项目写好的算法可以直接拿去做预处理将顶点集合变成一个 polygon再接给后续碰撞计算。真实的游戏引擎里 Qhull 或者 Bullet 的 internal hull 做的就是这件事原理和我这里的二维版本一脉相承。6.2 图像轮廓后处理的凸包补全做图像轮廓提取时cv2.findContours 返回的轮廓点经常有锯齿状或断裂直接拿去做形状匹配很容易失败。对轮廓点取凸包能把断裂的外边界补齐成一个稳定的凸形状之后再算外接矩形、直径、方向都会稳定很多。手写这个流程时本项目里的 Andrew 实现可以直接复用没必要为了一个边界抽取再拖进一个完整计算几何库。6.3 后续可以怎么继续扩展要说扩展方向二维凸包往上走就是三维凸包QuickHull、增量法往下走是动态凸包平衡树维护增量插入旁边还有最小外接矩形凸包 旋转卡壳、凸包间的闵可夫斯基和。你可以先把二维实现用着跑业务再按需往这些方向延伸。我自己的下一步计划是把 Andrew 改成接收 numpy 数组的版本再用 numba 把弹栈循环加速目标是在不影响可读性的前提下把 10 万点的凸包压到几十毫秒以内。最后再分享一个小体会真正把一个凸包算法从零写出来之后你会发现自己对“排序 单调性”这类计算几何问题的直觉会明显变好。调试时哪怕错了只要盯着 cross 的符号和栈的变化几分钟内就能定位问题。项目源码和测试我都整理到了本地仓库如果你想跑一遍照着上面的代码就能复现全部结果后面如果我有时间还会把三维版和动态凸包的实现也补上来。本文还有配套的精品资源点击获取