简介这是一份用Python实现凸包算法的可复用项目面向计算机图形学、机器学习或算法学习开发者解决几何点集最小凸多边形快速计算问题。包内代码覆盖Graham扫描、Jarvis步进与Andrew剪枝等常见策略并辅以绘图可视化、单元测试与基准对比脚本便于验证正确性和性能差异。资源共5个文件以Python脚本为主附带Markdown说明文档压缩包仅7KB结构精炼适合直接阅读源码或集成到工程中。作者还通过简洁的代码组织展示了numpy、matplotlib等库在几何计算中的典型用法。已有258人学习下载对于想快速上手凸包原理与Python实现、或需要轻量算法参考的开发者是一份实用的入门与工具型资源。 最近因为一个碰撞检测的小项目我需要在一堆散乱点外面画一圈包围轮廓。一开始想偷懒调现成的库但后面翻到早期图形学资料发现这些库底层用的就是经典的凸包算法convex hull。想着与其当个黑盒调用者不如自己用Python把整套逻辑重写一遍这样既能精确控制边界条件也能在性能敏感的地方做裁剪。这篇文章就是我在重写过程中的完整记录从原理到代码到踩坑都会讲清楚。如果你是做计算几何、图形图像或者数据可视化的又想彻底搞懂凸包算法而不是停留在调包层面这篇文章应该对你有用。凸包的定义听起来抽象其实很直观在平面上给你一堆钉子用一根橡皮筋把所有钉子都围起来橡皮筋绷紧后形成的多边形就是凸包。用数学语言说就是包含所有点的最小凸多边形。它在实际项目里出现得非常频繁——游戏里的碰撞包围体、图像处理里的手势轮廓提取、地理信息里的区域边界简化、还有数据聚类里画边界都会用到这个基础算法。重写过程中我对比了常见的几种实现思路对着自己造的随机数据和真实地形数据反复跑了很多遍踩了不少坑也发现了很多网上教程没讲清楚的细节。下面我会从问题定义开始把算法选型、原理推导、代码实现和坑点排查完整走一遍最后给出一份能直接复制的Python实现。1. 凸包问题是什么为什么值得自己写一遍1.1 凸包在真实场景中的位置凸包不是教科书里的玩具问题它在实际工程里承担着非常重要的角色。最常见的应用是碰撞检测。物理引擎里物体的精确碰撞计算很昂贵所以通常先用一个简单的盒子或者凸多边形把物体包住如果外包络都不相交那就没必要进入精细计算了。这个外包络通常就是用凸包生成的。再举个例子图像处理中的手势识别。人的手掌轮廓是复杂的凹多边形但手指尖的检测可以借助凸包来简化。把手掌的轮廓点集求凸包凸包顶点与原始轮廓的凹陷处会产生明显的缺陷区域这些缺陷区域的数量和深度就是识别手指伸展状态的关键特征。这类算法在OpenCV里封装好了但底层就是凸包计算。还有路径规划比如无人机要绕开一片不规则障碍区域把障碍区域的凸包算出来规划算法就直接在凸包外围飞大幅减少计算量。我自己重写凸包不是因为现成库不好用而是有三个现实的理由。第一很多库里的实现是黑盒一旦遇到边界情况比如所有点共线、点集只有一个点很难定位问题到底出在算法还是出在输入数据的预处理上。第二有些场景需要定制行为比如在凸包上去掉过于接近的顶点或者要求凸包顶点按顺时针方向输出这些定制逻辑如果不懂底层算法改起来非常痛苦。第三纯学习目的——凸包是计算几何的入门算法它涉及的排序、叉积、栈操作都是基础功把它吃透后再去啃更复杂的三角剖分、Voronoi图会顺畅很多。1.2 算法选型Graham扫描法还是单调链法凸包的经典算法有好几种最容易查到的是Graham扫描法Graham Scan和Andrew单调链法Andrews Monotone Chain。另外还有暴力法Jarvis步进法也叫礼品包装法和QuickHull但实际写代码做产品大家基本都在Graham和Andrew之间选。Graham扫描法的思路是先找一个一定会出现在凸包上的点作为基准点通常选y坐标最小如果y相同则选x坐标最小的点然后把其他所有点按照与基准点的极角排序再通过一个栈来维护凸包的顶点序列每加入一个新点时用叉积判断是否发生右转如果右转说明之前的点应该被弹出栈。这个算法的时间复杂度是O(n log n)瓶颈在排序那一步。Andrew单调链法稍微不同它的核心是避免计算极角。先把所有点按x坐标排序x相同则按y坐标排序然后分两次扫描构建凸包从左到右构建下凸包从右到左构建上凸包最后把两部分拼起来。它的时间复杂度同样是O(n log n)但因为没有调用atan2这类三角函数浮点误差风险更小代码也更简洁所以我在这次重写中选了它。从实际工程角度看Andrew单调链还有一个很实用的优势——它天然处理共线点。Graham扫描处理共线点时栈顶弹出逻辑容易出现问题需要额外判断。而Andrew单调链通过叉积的临界处理是保留还是剔除边界上的共线点可以灵活控制输出稍后会详细演示这两种策略。2. 两种主流算法的原理拆解2.1 叉积整个凸包算法的基石不管你用哪种算法核心计算只有一个叉积cross product。给定三个点O、A、B叉积cross(O, A, B)的计算公式是def cross(o, a, b): return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])这个公式的结果有非常直观的几何意义。如果结果大于0说明在O点处从OA向量转向OB向量是逆时针方向左转如果结果小于0说明是顺时针方向右转结果等于0说明O、A、B三点共线。这个大于0左转小于0右转等于0共线的判断就是凸包算法的全部几何基础。我刚开始接触的时候对着这个公式看了半天没理解为什么它能判断转向。后来用一个生活化的类比才搞明白想象你站在O点面朝A点方向B点在你左手边还是右手边叉积大于0B在你的左手边意味着你要向左转才能转过去叉积小于0B在你的右手边要向右转。凸包上的顶点有一个重要性质——沿着凸包边界走每一次转弯都应该是同一个方向全是左转或者全是右转取决于你走的方向。所以扫描过程中一旦发现右转就说明中间夹着的点不是凸包顶点应该丢弃。这就是整个算法的核心逻辑。2.2 Graham扫描法排序 栈扫描Graham扫描的具体步骤如下找到所有点中y坐标最小的点如果有多个y相同的点取x坐标最小的那个记为p0。这个点一定在凸包上因为它是整个点集的最底部。计算每个点相对于p0的极角对点按极角从小到大排序。极角相同的点距离近的排在前面。初始化一个栈先将p0和排序后的第一个点压入栈。依次遍历剩下的点对每个新点p检查栈顶两个点组成的向量到p的转向。如果是右转叉积小于0弹出栈顶点继续检查直到满足左转条件再压入p。遍历完成后栈里剩下的就是凸包顶点。这个算法的名字Graham来自它的发明者Ronald Graham。它在排序上花费了主要时间排序的好坏直接决定算法效率。但它的一个隐性问题在于计算极角需要调用atan2(y, x)而浮点三角函数的误差在不同平台上会有细微差别对精度要求高的场合需要注意。2.3 Andrew单调链法两次扫描不用算角度Andrew单调链法绕开了极角计算只用坐标排序加叉积判断。具体步骤是把所有点按x坐标升序排序x相同的按y坐标升序排序。从左到右扫描一遍构建凸包的下链。维护一个列表lower依次把点加入每次加入后检查最后三个点列表的后三个是否构成右转。如果构成右转说明中间那个点是多余的弹出它。重复检查直到不再右转或者列表长度小于3。从右到左再扫描一遍构建凸包的上链。逻辑相同只是顺序反过来。把下链和上链拼接起来去掉首尾重复点得到完整的凸包。为什么分别扫两遍因为凸包的上半部分和下半部分结构上是对称的一次从左到右只能保证得到下半圈要拿到完整的凸包还需要从右到左再构建一次上半圈。这个算法没有三角函数参与只涉及加减乘除数值稳定性好很多实现也短这是它现在越来越受欢迎的原因。有一个细节值得注意构建下链时我们的判断是最后三个点是否右转如果是右转就删除中间那个点也就是列表的倒数第二个点然后继续回退检查。这个过程用while循环天然就能实现代码写起来非常优雅栈操作的过程完全是隐式的不需要显式维护一个栈结构。3. Python实现从零手写凸包算法3.1 环境准备与测试数据我用的是Python 3.10不需要任何第三方库纯标准库就能跑。最方便的是itertools里的combinations可以在验证时遍历所有点对组合。依赖越少越好这样代码可以平滑运行在任何装了Python的机器上不需要配置环境。测试数据分三类随机生成的大量点、包含共线情况的退化数据、以及真实的地物轮廓数据。随机数据直接用random模块生成二维坐标然后调用算法验证输出是否正确。这里有个很容易被忽略的点验证凸包算法是否正确不能只靠用眼睛看需要一个自动验证的方法。我最常用的验证思路是——遍历原始点集中的每一个点确认它都在凸包内部或边界上再遍历凸包的所有边确认所有原始点都在边的同一侧。这两个条件同时满足算法结果就是正确的。具体代码如下import math import random def cross(o, a, b): 计算向量 OA 和 OB 的叉积。 返回值 0: A-B 为逆时针左转 返回值 0: A-B 为顺时针右转 返回值 0: 三点共线 return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]) def convex_hull(points): Andrew 单调链法求凸包返回逆时针排列的凸包顶点列表。 if len(points) 3: return points[:] # 1. 按 x 坐标排序x 相同则按 y 坐标排序 pts sorted(set(points)) if len(pts) 3: return pts # 2. 构建下链 lower [] for p in pts: while len(lower) 2 and cross(lower[-2], lower[-1], p) 0: lower.pop() lower.append(p) # 3. 构建上链 upper [] for p in reversed(pts): while len(upper) 2 and cross(upper[-2], upper[-1], p) 0: upper.pop() upper.append(p) # 4. 合并去掉首尾重复点 return lower[:-1] upper[:-1]这里我用了cross(...) 0的判断。它的效果是当三点共线或右转时都把中间那个点弹出栈这样最后得到的凸包不包含边上的共线点顶点都是角点。如果你需要凸包边上保留所有与原点集一致的顶点比如计算周长时希望包含更多的边界点把判断条件改成 0只弹出严格右转的点即可。这两种需求在实际项目里都有具体取舍看业务场景。3.2 自动验证凸包结果的辅助函数实现完算法之后我建议立刻写一个验证函数而不是靠肉眼观察散点图。验证函数的核心逻辑是对凸包的每条边确认所有原始点都在这条边的同一侧或者直接利用叉积来判断所有点是否都在凸包多边形内部。def is_valid_hull(points, hull): 检查 hull 是否为 points 的有效凸包。 if len(hull) 3: return False n len(hull) for i in range(n): p1 hull[i] p2 hull[(i 1) % n] # 检查所有点是否在边 p1-p2 的同一侧 for p in points: if cross(p1, p2, p) -1e-12: # 允许微小浮点误差 return False return True注意这里我用了一个很小的负阈值-1e-12而不是直接判断是否小于0。因为浮点数在计算叉积时会产生极其微小的误差比如某个理论值为0的情况计算机可能算出1e-15或者-1e-15如果用严格的 0判断这些边缘点会被错误地判定为在另一侧。加一个1e-12的容差就能把这类浮点噪声过滤掉。这也是我在实际调试中踩到的第一个坑后面Detail会展开讲。3.3 运行测试随机点集与性能观察下面用随机数据跑一下。我生成了1000个二维随机点并记录算法耗时# 生成测试数据 random.seed(42) test_points [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(1000)] # 计算凸包 hull convex_hull(test_points) print(原始点数量:, len(test_points)) print(凸包顶点数量:, len(hull)) print(凸包顶点:, hull) # 验证结果 print(验证通过:, is_valid_hull(test_points, hull))跑出来的结果符合预期。1000个点执行很快整个过程几乎在瞬时完成。凸包顶点数量通常在20~60之间具体取决于数据分布。随机均匀分布的数据凸包顶点数量大约与总点数呈对数关系这也是凸包在降维、简化数据上的价值体现——用几十个点就可以描述上千个点的分布范围。如果需要在代码里可视化验证可以用matplotlib画一下散点和凸包轮廓。虽然这不是算法本身的一部分但实际操作中看到凸包把点集完整包裹、没有漏掉任何点也没有多余顶点对理解算法的正确性非常有帮助。import matplotlib.pyplot as plt def plot_hull(points, hull): xs, ys zip(*points) hx, hy zip(*hull [hull[0]]) plt.plot(xs, ys, o, markersize3) plt.plot(hx, hy, -r, linewidth2) plt.axis(equal) plt.show()3.4 处理特殊输入退化情况凸包实现比很多人想象中更容易翻车的点就是对退化输入的处理。常见的情况包括点集为空或只有1个点所有点共线分布在一条直线上所有点完全重合或重复点较多我的实现中在函数开始处加了一个保护if len(points) 3: return points[:]。这个保护在点集小于3个点时直接返回原样因为此时不存在有面积的凸包。但更隐蔽的坑在所有点共线这个情况。比如输入[(0,0), (1,1), (2,2), (3,3)]它们都在直线yx上此时凸包理论上应该退化为一条线段返回的两个端点即可。用Andrew单调链处理时set(points)去重后仍有4个点先构建下链从(0,0)到(3,3)因为后面每个点都和前面的点共线叉积为0会触发弹出操作最后下链实际上只剩下首尾两个点。上链同理最后合并得到[(0,0), (3,3)]结果恰好是线段的两个端点符合预期。但如果把判断条件改成 0不弹共线点那最后凸包就会包含中间的所有共线点输出就会变成一条线上密密麻麻的顶点。这两种行为对后续几何计算影响差异很大提前想清楚业务需求非常重要。三个或三个以上点全部共线的情况是所有凸包实现都要专门处理的边界。我的建议是涉及面积、范围判断的业务用 0剔除共线中间点涉及路径、边长精度的业务用 0保留共线点。4. 常见问题与排查技巧实录4.1 浮点精度导致的错判这是我在测试过程中遇到最多的一个问题典型场景是数据点坐标小数位很多或者坐标值本身很大。比如点的坐标从几十万量级开始叉积计算动辄涉及百万量级的乘法浮点误差会被放大导致理论为0的共线判断变成-1e-10然后被错误地当作右转导致本应保留的凸包顶点被弹出。遇到这种情况我的第一反应不是调整算法而是统一坐标尺度再做计算。比如所有点都减去最小坐标值让数据落在原点附近的范围内。这个方法在处理地图坐标比如经纬度或者投影坐标时特别有效。另一个方案是在判断叉积时使用一个相对容差而不是绝对值比如判断共线时用abs(cross_val) eps * scale其中scale可以取点集坐标范围的长度。实际使用中我通常是先做坐标平移归一化再用 0的判断两个办法叠加之后基本能规避浮点精度问题。还有一个容易踩的坑是set(points)去重依赖点是可哈希的元组这没问题但如果你的点是用list存储的直接set(points)会报TypeError因为list不可哈希。我测试时顺便写过一个小工具函数把list形式的点自动转成tuple再去重这个细节虽然不起眼但在处理从JSON读进来的数据时非常实用。4.2 共线点去留的策略选择刚才我在代码里用 0剔除了共线点。但有一次我在做地形数据简化需要计算凸包的周长来近似某条道路的围栏长度结果发现剔除共线点之后周长变短了我一开始以为是算法错了后来才意识到是共线点处理的问题。因为这些共线点虽然不是凸包的角点但它们位于凸包的边界上用 0把它们去掉之后凸包边界只保留了直线段的起点和终点道路的总长度就不完整了。这时候就需要一个动态开关来控制共线点的去留。我在项目里给函数加了一个参数def convex_hull(points, keep_collinearFalse): keep_collinearTrue 时保留边界上的共线点。 pts sorted(set(points)) if len(pts) 1: return pts def pop_right_turn(stack, p): while len(stack) 2 and cross(stack[-2], stack[-1], p) (0 if keep_collinear else -1e-12): stack.pop() return stack lower [] for p in pts: pop_right_turn(lower, p) lower.append(p) upper [] for p in reversed(pts): pop_right_turn(upper, p) upper.append(p) return lower[:-1] upper[:-1]这么改完同一个函数就能应对两类场景。默认的keep_collinearFalse适合范围检测、碰撞检测keep_collinearTrue适合周长计算和路径还原。这个参数我强烈建议保留因为实际需求切换的频率比想象中高很多。4.3 性能对比与优化空间用timeit模块分别测试1000、10000、100000个随机点的凸包计算耗时。实测下来Andrew单调链算法处理10000个点大约需要几毫秒处理100000个点大约几十毫秒。瓶颈几乎全在排序上排序之后线性扫描部分非常快。这验证了一个通用原则在O(n log n)算法里真正影响大规模性能的不是扫描过程而是排序过程所以如果数据量特别大可以考虑用更快的排序算法或者直接调用C语言实现的高性能排序。如果点位本身带有序号或者有时间戳可以不用再做排序直接利用原有顺序扫描整体能降一个log因子。但这个优化在普通二维平面上不适用因为凸包算法依赖点的几何分布排序与时间顺序没有必然联系。如果点集维度超过二维比如三维空间找凸包Andrew单调链就不能直接用了需要使用三维凸包算法如QuickHull的3D版本复杂度会明显上升。这类问题在项目里如果遇到建议不要手写直接用现成的计算几何库我常用的有scipy.spatial.ConvexHull它底层是Qhull库支持任意维度性能也很稳。但前提是先理解一维和二维的实现思路这样三维的结果出了问题你也能快速定位到是数据处理的问题还是维度扩展的问题。4.4 一句话总结排查流程如果你在跑代码的时候发现凸包结果怪异按照我排查的顺序来基本都能解决第一步输出原始点集检查是否有重复点、NaN数据或无穷大坐标第二步确认排序结果是否正确排序错误会导致上下链完全错乱第三步检查叉积返回值的方向是否和你定义的左转/右转一致这个最隐蔽因为不同教程对cross参数顺序的约定不同第四步涉及小数运算就加入浮点容差第五步用自动验证函数检查结果是否有效而不是用肉眼观察散点图。这套排查流程我复制到好几个项目用了每次都能快速定位问题。5. 从算法到工程的扩展与思考重写凸包让我有另一个收获——算法实现的风格直接影响后续维护。比如我一开始写的是纯函数式地返回凸包顶点后来业务需要凸包面积和方向顺时针还是逆时针我又加了两个辅助函数。面积用鞋带公式Shoelace Formula计算方向则通过扫描凸包顶点坐标判断。这些代码写出来很简短但正确性依赖凸包输出有序且边界清晰的约定。如果当初没有自己实现底层逻辑不透明遇到计算面积或判断方向的需求还要去查库文档排查起来就绕远了。def polygon_area(vertices): 鞋带公式计算多边形面积。 n len(vertices) if n 3: return 0.0 area 0.0 for i in range(n): x1, y1 vertices[i] x2, y2 vertices[(i 1) % n] area x1 * y2 - x2 * y1 return abs(area) / 2.0这段代码验证时间很快因为面积公式和凸包算法是独立的正好可以互相验证用凸包面积与原始点集的范围对比可以发现凸包结果是否异常。这也是我实际开发中比较喜欢的做法——算法之间互相校验远比单独测试一个函数可靠。最后再分享一个我在实际使用中的体会凸包算法虽然只有几十行代码但它是很多复杂计算几何问题的第一步。比如在游戏开发里做导航网格先对障碍物求凸包把复杂的凹多边形简化成凸多边形后面的寻路算法才跑得动在地理信息系统里做行政区划简化凸包也是顶点抽稀的常用工具甚至在做机器学习的数据预处理时用凸包检测异常值也比简单的z-score方法更贴近数据的真实几何分布。花一个下午把这个算法吃透往后的收益远超预期。我这次的重写任务也已经附在文中代码可以直接复制运行。如果你跑出来的结果和直觉对不上不要怀疑人生先看看是不是共线点开关没调对再用自动验证函数跑一遍多半就能发现问题了。本文还有配套的精品资源点击获取