【算法分析与设计】第36篇：计算几何基础：凸包问题的分治与扫描线解法
从字符串的线性结构转向平面上的点集，我们进入了算法设计中另一个丰富而优美的领域——计算几何。凸包问题是计算几何的第一课：给定平面上 nn 个点的集合，找出一个最小的凸多边形，使其包含所有点。这里的“最小”不是指面积最小，而是指包含关系——凸包是包含所有点的所有凸多边形的交集。如果把点想象为钉在木板上的钉子，用一根橡皮筋套在所有钉子外围，橡皮筋自然收紧后形成的形状就是凸包。
一、凸包的形式化定义
设 P={p1,p2,…,pn}P={p1,p2,…,pn} 为平面上的 nn 个点。PP 的凸包 CH(P)CH(P) 定义为包含 PP 中所有点的最小凸集，等价于 PP 中所有点的凸组合的集合：
CH(P)={∑i=1nλipi | λi≥0,∑i=1nλi=1}CH(P)={∑i=1nλipi∣λi≥0,∑i=1nλi=1}
凸包的边界是一个凸多边形，其顶点是 PP 的某个子集。凸包问题即要求按逆时针（或顺时针）顺序输出这些顶点的列表。
一个关键的性质是：PP 中的点 pp 是凸包的顶点，当且仅当存在一条直线，使得 PP 中除 pp 外的所有点都在这条直线的同一侧。换言之，凸包顶点是那些“无法被其他点的凸组合表示”的极端点。这一性质为凸包算法的设计提供了几何直觉。
二、Graham扫描法：基于极角排序的线性扫描
Graham扫描法是凸包问题最经典的算法，由Ronald Graham于1972年提出。其核心流程分为三步：
第一步，选定基点。从 nn 个点中选出 yy 坐标最小的点作为基点 p0p0。若有多个这样的点，选其中 xx 坐标最小的。显然 p0p0 必定是凸包的顶点——因为它是整个点集在纵轴负方向上的极端点。
第二步，极角排序。对除 p0p0 外的所有点，按它们相对于 p0p0 的极角从小到大排序。若有多个点具有相同的极角（即它们与 p0p0 共线），仅保留距离 p0p0 最远的那个，其余的不可能成为凸包顶点。排序完成后，点序列按逆时针方向围绕 p0p0 排列。
第三步，栈式扫描。维护一个栈，初始时将 p0p0 和排序后的前两个点压入。此后依次处理排序中的每个点 pipi。设栈顶的两个点为 AA 和 BB（AA 为栈顶，BB 为次栈顶），检查向量 BA⃗BA 与 APi⃗APi 的叉积。若叉积为正（即 pipi 相对于 BABA 是“向左转”），则压入 pipi。若叉积为负（“向右转”），则弹出栈顶 AA，重新检查新的栈顶，直至满足向左转条件或栈中只剩两个点。这一过程保证了栈中的点始终保持逆时针方向的凸性。
算法的复杂度分析非常直接。选基点耗时 O(n)O(n)，极角排序耗时 O(nlogn)O(nlogn)，栈式扫描部分每个点至多入栈一次、出栈一次，总操作 O(n)O(n)。因此总复杂度为 O(nlogn)O(nlogn)，排序占据主导。
极角排序的实现有一个值得注意的技巧：排序的键值不是直接计算反正切值（涉及浮点运算，存在精度隐患），而是利用叉积的正负来比较两点的极角大小。具体而言，对于点 pipi 和 pjpj，通过计算向量 p0pi⃗p0pi 与 p0pj⃗p0pj 的叉积来判断二者的相对顺序。叉积为正说明 pipi 的极角小于 pjpj；叉积为负则反之；叉积为零时二者共线，按距离排序。这一技巧保证了排序的精确性，完全避免了浮点误差。
三、分治法：归并凸包的递归策略
Graham扫描简洁优美，但它是一种增量式算法。另一种设计思路来自我们熟悉的分治范式。
分治法的流程与归并排序高度相似。将 nn 个点按 xx 坐标排序（xx 相同时按 yy 坐标）。若 n≤3n≤3，所有点都是凸包顶点，直接构造小凸包。否则将点集按 xx 坐标中位数平分为左右两部分 PLPL 和 PRPR，递归求解左右各自的凸包。合并步骤是算法的核心：给定两个分离的凸多边形，求它们整体的凸包。
合并两个分离凸包的技巧是寻找上下公切线。上公切线连接左右凸包各一个顶点，使得所有点都在该线或该线下方。下公切线则使得所有点在该线或该线上方。这两条公切线将左右凸包中位于“内部”的顶点排除，剩下的顶点构成了合并后的凸包。
寻找公切线的过程非常高效。以找上公切线为例：初始选取左凸包最右边的点为左候选，右凸包最左边的点为右候选。循环调整——若左候选的顺时针下一个邻居使连线更“向上”，则左候选沿顺时针移动；若右候选的逆时针下一个邻居使连线更“向上”，则右候选沿逆时针移动。当两候选都不再需要调整时，当前连线即为上公切线。由于调整始终沿凸包边界单向进行，整个过程在左右凸包顶点数之和的线性时间内完成。
分治法的递归方程为 T(n)=2T(n/2)+O(n)T(n)=2T(n/2)+O(n)，解得 T(n)=O(nlogn)T(n)=O(nlogn)，与Graham扫描相同。虽然分治法在最坏情况下的常数因子较大，但它能同时维护多个子凸包，在某些需要动态更新的场景中更具灵活性。
四、两种方法的比较与适用场景
Graham扫描法和分治法虽然都达到了 O(nlogn)O(nlogn) 的最优界，但在不同场景下各有优势。
Graham扫描法实现简洁，常数因子小，是算法竞赛和简单应用的首选。但它的 O(nlogn)O(nlogn) 瓶颈在于排序，即使点集几乎已经有序，仍需支付完整的排序代价。此外，Graham扫描本质上是“静态”算法——若后续增加新点，必须重新排序整个点集，无法增量更新。
分治法的优势在于结构上的灵活性。由于分治法天然将点集组织为二叉树结构，当点集允许动态插入或删除时，可以通过维护一棵平衡二叉树来增量更新凸包。此外，分治法的合并步骤自然地导出两个凸包的公切线，这在求两个凸多边形的最小距离、判断凸多边形相交等问题中直接复用。
从更宏观的视角看，两种方法背后对应着计算几何的两种通用策略：Graham扫描代表的是扫描线策略——通过排序将二维问题化为一维顺序处理，这一思想在后续的线段交、矩形并面积等问题中反复出现。分治法代表的则是空间递归分割策略，与平面点集的最近点对问题、Voronoi图的构造等方法一脉相承。
五、应用场景
凸包是许多几何算法的基础子程序。
在碰撞检测中，复杂的物体形状可以先用凸包近似。两个凸多边形是否相交，可以通过检查它们是否存在分离轴来高效判定。凸包简化了物体的边界表示，使碰撞检测从复杂的形状匹配变为多边形的线性扫描。
在形状分析与模式识别中，点集的凸包是最基本的形状描述符之一。凸包的面积、直径（最远点对）、宽度（两条平行支撑线间的最小距离）都是形状特征提取的核心指标。
在数据可视化中，散点图的边界轮廓可直接用凸包刻画，帮助观察数据的分布范围与离群点。
在Voronoi图与Delaunay三角剖分的构造中，凸包是初始边界条件。Delaunay三角剖分的外边界恰好是点集的凸包，这一联系将在后续篇章中详细展开。
六、总结与展望
凸包问题以简洁的输入输出承接了计算几何的核心方法论。Graham扫描法通过极角排序将二维散点组织为线性序列，再用栈模拟凸性的维护过程；分治法将点集沿坐标轴递归分割，再通过公切线的寻找完成凸包的归并。两种算法殊途同归，皆达到 O(nlogn)O(nlogn) 的理论最优界。
然而，凸包只是计算几何的起点。当我们需要处理线段之间的交点、多边形的布尔运算，或者面对大量矩形在平面上的覆盖问题时，单纯的凸包已不够用。下一篇，我们将进入平面扫描的通用框架——以线段交问题为切入点，系统介绍扫描线算法的设计思想与事件点调度机制，为后续更复杂的几何算法奠定基础。
本回答由 AI 生成，内容仅供参考，请仔细甄别。