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