简介这是一份用Python编写的凸包算法项目适合正在学习计算几何、图形学或需要快速集成几何计算能力的开发者。资源围绕凸包这个经典问题演示了葛立恒扫描、贾维斯步进等常见算法的实现思路并配有二维点集可视化模块与测试用例帮助读者直观理解算法执行过程、对比不同实现的正确性与性能表现。压缩包共五个文件包含四个Python脚本和一个Markdown说明文档分别承担核心算法实现、绘图展示、单元测试、性能基准测试以及使用环境说明整体仅7KB结构清晰、注释简洁便于直接阅读、修改和二次开发。在实际应用中凸包可用于碰撞检测、数据聚类、区域边界提取、路径规划等众多场景。项目目前已有两百六十一人学习对于算法初学者和工程开发者都是一份轻量实用的参考资料。1. 凸包算法重实现给点云拉一根“最小橡皮筋”在 GIS 数据清理、CAD 描边、图像轮廓标注这些场景里最常做的一件事就是把屏幕上密密麻麻的散点圈出一个边界。凭肉眼描边出图没有问题一旦交给下游算面积、做碰撞检测多一个点少一个点结果都对不上。凸包算法做的正是这件事——在所有点外侧拉出一条最小凸多边形只保留真正的外围角点。这个用 Python 写的 convex_hull 项目重新实现了多款软件里最常用的凸包算法并自带可视化和命令行输出。你不需要把整个几何库搬进项目直接拿这份源码该跑的跑通想换算法的也只用动一个文件。适合做图形处理、地理数据整理以及准备算法相关面试的开发者。2. 项目结构与技术选型四个模块如何把一个算法拆成工程2.1 目录结构与模块职责这个仓库并没有把凸包算法堆在一个脚本里而是按“数据生成、算法求解、结果渲染、命令行入口”拆成了四个关注点目录结构大概长这样convex_hull/ ├── convex_hull/ │ ├── __init__.py # 包初始化导出算法入口 │ ├── core.py # 叉积、方向判断等基础几何工具 │ ├── algorithms.py # Graham / Andrew / Jarvis 三种算法 │ ├── render.py # matplotlib 可视化 │ └── cli.py # 命令行入口生成随机点并导出结果 ├── examples/ │ └── demo_random_points.py # 一键可视化的演示脚本 ├── tests/ │ └── test_convex_hull.py # 最小回归测试 └── README.md核心文件职责对照如下文件职责core.py提供cross()叉积计算这是整个凸包判定的地基algorithms.py三种算法实现输入统一为点列表输出统一为逆时针凸包点列表render.py把原始点集和凸包画在同一坐标系便于肉眼核验cli.py读取参数、生成数据、调算法、落盘结果算法层和渲染层隔离带来的好处很明显以后新增 QuickHull完全不用碰画图代码调试时可以直接在 Python REPL 里调algorithms.graham_scan(points)拿到顶点列表再做面积或周长校验不需要经过命令行。这种分层方式比把算法和可视化写在一个文件里更适合拿来二次开发。2.2 技术选型为什么只依赖 matplotlib这个项目本质上是个纯计算几何工程不涉及矩阵运算、线性代数numpy用在这里纯粹是拉高安装门槛。我一般不会在这种规模的算法库里引入它点坐标直接用标准库的tuple表示算法内部做的只是加减法和比较set去重、sort排序都是 Python 内置能力。所以core.py和algorithms.py这两个模块在任何 Python 3.8 环境里都能直接跑连 pip 都不用装。可视化选择 matplotlib 是最省事的方案。它用来散点、画线、填充多边形都足够直观而且几乎每个 Python 开发环境里都有。唯一要注意的是plt.axis(equal)必须加否则 X 轴和 Y 轴比例不一致圆形点云会被拉成椭圆形凸包看起来像画歪了实际并没有。这也是我最早写可视化时常踩的坑。2.3 从命令行拉起一个最小 Demo先把环境跑起来最小操作是这样python -m venv .venv source .venv/bin/activate # Windows 使用 .venv\Scripts\activate pip install matplotlib python examples/demo_random_points.py --seed 2024--seed参数用来固定随机种子。没有它每次生成的随机点都不一样调试时很难对比结果固定种子以后同一台机器上每次跑出来的点集和凸包完全一致方便你对照源码检查顶点顺序。如果你不需要弹窗看图形只想拿计算结果走命令行入口更合适python -m convex_hull.cli --count 200 --seed 42 --output hull.txt这条命令会生成 200 个横纵坐标在 0100 之间的随机点计算完凸包后把顶点按逆时针顺序写入hull.txt每行一个x,y。拿到这个文件后你可以用鞋带公式算一下多边形面积面积为正说明顶点顺序确实是逆时针这也是最快的结果校验方式。3. 核心实现逐段拆解Graham 扫描如何一步步拉出外圈3.1 地基叉积与三点转向判断整个 convex_hull 项目所有算法都建立在同一个函数上——叉积。先看core.py里的实现def cross(o, a, b): 计算向量 OA 与 OB 的叉积判断三点之间的转向关系 return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])叉积返回值有明确的几何含义大于 0 表示向量 OA 逆时针旋转到 OB等于 0 表示三点共线小于 0 表示顺时针。这个函数在凸包代码里出现频率极高Graham 扫描弹栈用它Andrew 单调链判断上下包用它Jarvis 步进选下一个点也用它。参数o是基准点a和b是被测点。命名上刻意把基准点放第一位读代码时cross(stack[-2], stack[-1], p)一眼就能看出谁是当前边、谁是新来的点。这个约定在三个算法里全程保持一致避免方位搞混。3.2 Graham 扫描找最低点、极角排序、单调栈Graham 扫描的思路是先找一个必然在凸包上的点通常是 y 坐标最小的点再把其余点按极角排序最后用单调栈维护凸包的边界。看实现import math def graham_scan(points): # 先去重再排序保证点不重复 points sorted(set(points)) if len(points) 3: return points # 如果所有点共线凸包退化成一条线段直接返回两端点 if all(cross(points[0], points[1], p) 0 for p in points[2:]): return [points[0], points[-1]] # 找到最低点y 最小y 相同时取 x 最小 p0 min(points, keylambda p: (p[1], p[0])) rest [p for p in points if p ! p0] # 以 p0 为原点按极角排序 rest.sort(keylambda p: math.atan2(p[1] - p0[1], p[0] - p0[0])) # 单调栈扫描 stack [p0, rest[0], rest[1]] for p in rest[2:]: while len(stack) 2 and cross(stack[-2], stack[-1], p) 0: stack.pop() stack.append(p) return stack第一眼看上去最容易被忽略的是共线预检查。当所有输入点在同一条直线上时stack初始化的三个点就已经共线后续循环不会弹出中间点最后返回三个点而不是一条线段。所以算法开头必须判断“全共线”这个退化场景直接返回两端点。这个边界条件很多教科书实现都不处理实际接入数据时却很容易碰到。极角排序用math.atan2是最直观的写法它返回范围是(-π, π]能正确处理四个象限。排序后从最低点 p0 出发按逆时针方向扫描一旦发现新点让栈顶出现顺时针转向叉积小于等于零说明栈顶点被包在内部弹掉。 0的写法同时把共线点也弹掉保证凸包是严格最小多边形不包含边上的冗余点。3.3 Andrew 单调链不做三角函数排序的工程替代Graham 的极角排序涉及浮点三角函数而 Andrew 单调链完全避开了这个环节。它对点集按(x, y)排序后分别构建下链和上链最后拼接成完整凸包def andrew_monotone_chain(points): points sorted(set(points)) if len(points) 3: return points # 构建下凸包从左到右扫描 lower [] for p in points: while len(lower) 2 and cross(lower[-2], lower[-1], p) 0: lower.pop() lower.append(p) # 构建上凸包从右到左扫描 upper [] for p in reversed(points): while len(upper) 2 and cross(upper[-2], upper[-1], p) 0: upper.pop() upper.append(p) # 两端点会重复拼接时各去掉最后一个 return lower[:-1] upper[:-1]这个实现里排序是关键一步排序规则是先 x 后 y完全基于整数比较不涉及任何浮点角度。所以 Andrew 在某些软件里的出镜率比 Graham 还高——它稳定输出顺序可控而且在输入点分布极端时不容易翻车。实际写代码时我用它就是当作 Graham 的对照组专门验证随机点集下两个算法画出来的多边形是否重合。两次扫描的复杂度是 O(n log n)瓶颈在排序扫描本身是线性的。lower[:-1] upper[:-1]这么拼接是有原因的下链的最后一个点是全图 x 最大的点上链的第一个点也是它直接拼接会重复同理最左侧点也会重合所以两边各去掉尾部一个顶点。3.4 可视化渲染把点云和凸包叠在同一张图里render.py里的函数很短但它承担了“肉眼验收”的职责。算法算得对不对跑一遍看图形立刻见分晓import matplotlib.pyplot as plt def draw(points, hull): xs, ys zip(*points) plt.scatter(xs, ys, s12, colorgray, label点集) hx [p[0] for p in hull] [hull[0][0]] hy [p[1] for p in hull] [hull[0][1]] plt.plot(hx, hy, colorred, linewidth2, label凸包) plt.fill(hx, hy, colorred, alpha0.2) plt.legend() plt.axis(equal) plt.show()zip(*points)把点列表拆成 x 序列和 y 序列scatter画原始散点plot负责把凸包顶点依次连起来。注意hx和hy在顶点列表后面又追加了第一个点这是为了闭合多边形——否则画出来是一条折线不是封闭图形。fill用半透明红色填充内部方便确认凸包是否包含所有点、有没有点露在外面。axis(equal)是最容易被忽略的参数。坐标范围不一致时matplotlib 会默认拉伸画面圆点云可能看起来是椭圆凸包的边视觉上就不贴合点云容易误判算法有问题。加上这个参数后X、Y 轴的单位长度一致图形所见即所得。4. 常见问题与避坑方向、精度、共线是最容易翻车的三件事4.1 极角排序的浮点陷阱现象在点几乎共线但稍有随机扰动时跑 Graham 扫描输出的凸包顶点顺序偶尔会变换一个 Python 版本结果也可能不同。原因math.atan2返回浮点角度当两个点和基准点几乎在同一条射线上时角度差值小到超过浮点精度排序器认为两个键相等先后顺序就交给sort的稳定性决定。而稳定排序保留原顺序原顺序一旦在输入里变化输出顶点顺序跟着变。解决生产环境优先用 Andrew 单调链它只做整数叉积比较如果必须用 Graham自定义比较器代替角度键——先用叉积判断方向叉积为 0 时再按距离排序全程不计算角度。我写第 3 章代码时保留atan2是为了教学直观实际接数据我一般切 Andrew。4.2 共线点到底该不该保留现象从 CAD 软件导出描边点计算凸包做等距采样时发现原本落在直线边上的点全不见了下游工序拿不到原始采样点。原因while条件写成cross(...) 0凡是叉积等于零的共线点一律弹栈。这在几何上没问题凸包确实不需要中间点但业务上这些点可能承担着等距标尺、纹理坐标等额外属性。解决需要保留边界点时把弹出条件改成 0共线点会留在栈里面积不变但顶点数变多。我建议在算法入口加一个keep_boundary参数让调用方显式选择哪种子行为而不是悄悄改全局逻辑。4.3 输出方向不统一导致面积符号飘现象同一个点集用 Graham 算出正面积用 Jarvis 算出负面积某 GIS 库接手后直接报参数异常。原因鞋带公式算面积的正负由顶点绕行方向决定逆时针为正顺时针为负。三种算法实现约定不一致时下游只要直接用返回值就会踩雷。解决所有算法统一约定逆时针输出并加一个入口校验函数def ensure_ccw(hull): area 0 for i in range(len(hull)): x1, y1 hull[i] x2, y2 hull[(i 1) % len(hull)] area x1 * y2 - y1 * x2 if area 0: return hull[::-1] return hull这段代码用鞋带公式算有向面积面积为负就把整个列表反转。放进所有算法返回之前输出方向就永远一致了。4.4 经纬度坐标直接计算的结果只是“看起来对”现象把地图上的经纬度点喂进算法画出来是凸包但拿去算面积和地理软件给出的结果差一大截。原因经纬度是角度坐标不是平面投影坐标叉积公式在经纬度上不成立。纬度越高同样经度差对应的实际距离越短直接用角度计算会扭曲凸包形状和面积。解决先把经纬度投影到平面坐标再算凸包。常见做法是使用墨卡托或高斯投影近似把点转换成以米为单位的平面坐标算完凸包后再把顶点投影回经纬度。这个项目本身没有内置投影能力但算法层接收的是纯数字点你可以在调用前先完成坐标转换cross()完全感知不到差异。4.5 无桌面环境跑 demo 卡死不动现象在服务器或 Docker 容器里跑demo_random_points.py程序既不退出也不报错像死了一样。原因matplotlib 的plt.show()在无桌面环境里没有图形后端可用会进入阻塞状态等一个永远不会出现的窗口。解决给渲染函数加一个save_path参数有值时用plt.savefig(save_path)代替plt.show()。跑在服务器上就传一个 PNG 路径图形会被写入文件不会卡住。这也是我把render.py单独拆出来的原因算法和渲染解耦后在不同环境下替换渲染策略只需改一个函数。5. 二次开发把这个凸包模块接进你的项目5.1 读取自己的点集examples里生成的是随机点实际项目中点集通常来自 CSV、数据库或接口。把数据源替换成文件是最常见的改造def load_points(path): with open(path, r, encodingutf-8) as f: return [ (float(x), float(y)) for line in f if line.strip() for x, y in [line.strip().split(,)] ] from convex_hull import algorithms points load_points(road_nodes.csv) hull algorithms.andrew_monotone_chain(points)注意先转浮点再去重因为文本读进来的字符串比较不等于浮点数比较。我在测试里遇到过顶点数异常偏多的问题最后定位就是没做类型转换导致去重失效。5.2 用策略模式切换算法现在algorithms.py里的三个函数签名完全一致接新算法可以直接做成注册表ALGORITHMS { graham: algorithms.graham_scan, andrew: algorithms.andrew_monotone_chain, jarvis: algorithms.jarvis_march, } def solve(points, methodandrew): return ALGORITHMS[method](points)替换算法时调用方只需要换一个字符串参数不需要改任何业务代码。这也意味着你可以放心加第四种算法比如 QuickHull只要保持“输入点列表、输出逆时针顶点列表”的约定就行。5.3 图像坐标系的 Y 轴翻转做图像轮廓标注时图像坐标的 y 轴是向下的直接用图像坐标算凸包视觉上会上下颠倒。常见做法是把 y 取负转成笛卡尔坐标算完再转回来points_cartesian [(x, -y) for x, y in points_image] hull_cartesian algorithms.andrew_monotone_chain(points_cartesian) hull_image [(x, -y) for x, y in hull_cartesian]转换之后再算面积、周长、顶点顺序都会符合图像坐标下的直觉。从那以后我每次给项目换算法或换数据源都会先用固定种子跑一遍回归用例把顶点数、面积、周长三项和上一轮结果做对比确认三项都对得上再接入正式流程省掉了很多以为自己改错代码的排查时间。希望帮到你。本文还有配套的精品资源点击获取
