企业官网建设流程全解析

凸包（Convex Hull）问题算法详解

如果你跟计算几何打过交道，肯定绕不开凸包这个东西。简单说，给一堆散落的点，凸包就是能把所有点都包进去的最小凸多边形，就像拿一根橡皮筋把钉子板上的钉子全部箍起来。听起来简单，但这个“简单”的问题在计算机里并不那么好解决，而且它是很多高级算法的基础，比如旋转卡壳求最大距离、凸多边形碰撞检测、点云边界提取，都会先算凸包。我最早接触凸包是为了处理激光雷达的点云数据，后来做图像轮廓分析也频繁用到，可以说是计算几何里最高频的入门级硬核问题。

这篇文章我会把凸包的几种主流算法——Graham扫描、Andrew单调链、Jarvis步进、分治法——逐个拆开讲，不仅讲原理，还会给出可以“抄作业”的C++实现，最后分享一些实际调试中踩过的坑。不管是应付算法面试、写竞赛代码，还是做图像处理和点云分析，你都能从这篇文章里找到可以直接用的东西。

1. 凸包问题本质与算法选型思路

1.1 凸包的数学定义和几何直觉

凸包的严谨定义是：给定平面上点集S，S的凸包是所有包含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年提出的算法，也是绝大多数教材首选的凸包算法。它的核心思想很优雅：先选一个基准点，然后把其他点按相对基准点的极角排序，最后用一个栈维护凸包顶点，边走边“踢掉”造成右转的点。

完整步骤如下：

1. 在所有点中找到y坐标最小（如果y相同取x最小）的点作为基准点p0。这个点必然在凸包上，因为它就是橡皮筋最下方的一个钉子。
2. 把其他所有点按与p0的极角从小到大排序。极角相同时，距离p0近的点排在前面。
3. 将p0和排序后的前两个点压入栈。
4. 依次处理剩余每个点p，设栈顶为b，栈中次顶为a。如果a、b、p三点构成一个右转（叉积小于等于0），说明b不是凸包顶点，将其弹出，重复检查直到不再右转，然后把p压入栈。
5. 处理完所有点后，栈中保留的点就是逆时针顺序的凸包顶点。

判断左转还是右转，用叉积公式：设向量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单调链算法（也叫Andrew's Monotone Chain）是我个人最推荐的一个版本，它避开了极角计算，只需要对点按x（或y）坐标排序，然后分别构造凸包的下链和上链，最后拼接。复杂度同样是O(n log n)。

步骤拆开讲：

1. 对所有点按x坐标从小到大排序；x相同时按y从小到大排。
2. 构造下链：从左到右遍历所有点，把点依次加入凸包链。每加入一个新点，检查链尾三个点是否构成左转，如果不是左转（叉积小于等于0），就删掉链尾点，直到满足左转条件。这个操作和Graham扫描里的弹栈一样。
3. 构造上链：从右到左遍历所有点，执行同样的“维护左转”操作。
4. 下链和上链合在一起，去掉首尾重复的点，就是完整的逆时针凸包。

为什么叫单调链？因为整个算法把凸包拆成上下两条“单调”的折线，下链上所有点的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); } vector<Point> convexHull(vector<Point> p) { if (p.size() <= 1) return p; sort(p.begin(), p.end()); vector<Point> 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）的思路和人的直觉最接近。想象你用一根绳子系在凸包最左下角的点，然后拉住绳子另一端沿某个方向旋转，绳子先碰到哪个点，哪个点就是下一条边的终点。这个过程不断重复，直到回到起点。

具体实现是：

1. 找到最左下角的点p0（y最小，y相同时x最小），它显然是凸包顶点。
2. 设当前点为p_cur，寻找“下一个点”p_next，使得所有其他点都在向量(p_cur -> p_next)的左侧。如果有多个点共线，选择距离p_cur最远的那个。
3. 将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 症状总结与解决方案对照

结合实际调试经验，我把凸包计算中常见的故障现象和原因整理成一张速查表，方便遇到问题时快速定位：

表中最后一条在实践中最常见。很多人从网上抄代码时不注意符号，直接导致结果比预期多一堆点。如果你只是想输出凸包的顶点用于边界面积计算，用“<= 0”几乎总是对的。

5.2 实测调试过程回放：从崩溃到稳定的三分钟

我说一个自己印象很深的调试过程。某次做点云作业，写了Andrew单调链，用几千个随机点测试，一开始结果总是怪怪的，凸包多出一条“横穿内部”的线。我打印出排序后的点集合，才发现Point结构体里的比较函数写错了：我只比较了x，x相同时没有继续比较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把随机点集和凸包画出来，肉眼看一眼，很多逻辑错误当场就能发现，比打印一百行中间变量都高效。我到现在写计算几何代码，仍然会先可视化，再谈性能优化。