计算几何中的平面点集凸包算法 凸包是计算几何中的一个基础且重要的问题。我们先理解“凸包”的定义：给定平面上的一组点集，凸包是包含所有这些点的最小凸多边形。这里的“凸”是指多边形内部任意两点的连线仍完全在多边形内部。凸包算法就是高效求出这个多边形的顶点序列。 第一步：从几何直观到精确描述 想象在木板上钉一些钉子，用一根橡皮筋套住所有钉子，松开后橡皮筋形成的形状就是凸包。从数学上，凸包是点集所有凸组合的集合。对于平面点集S，其凸包CH(S)是满足以下条件的最小凸集：S ⊆ CH(S)。算法目标通常是输出凸包顶点按顺时针（或逆时针）的顺序。 第二步：关键观察与朴素算法 凸包顶点必然是点集中的点。一个朴素算法是：考虑点集中任意两个点构成的线段，检查其他所有点是否都在该线段的同一侧（或线上）。如果是，则该线段是凸包的一条边。但这种方法需要O(n³)时间（n为点数），效率极低。我们需要更优的算法。 第三步：增量算法（Jarvis步进法，又称“礼品包裹”算法） 这是最直观的优化算法，思想是“包裹”点集。 首先找到凸包的一个起点，通常是最左下角的点（y坐标最小，相同时x最小），它一定是凸包顶点。 从该点开始，寻找下一个凸包顶点：遍历所有其他点，找到使得当前点、候选点与任何其他点构成的“向右转”角度最小的点。这相当于寻找“最靠左”的点，可以用向量叉积判断方向。 以找到的新点为起点，重复步骤2，直至回到初始点。 时间复杂度为O(nh)，其中h是凸包上的顶点数。当h≈n时，退化为O(n²)。该方法易于实现，是理解凸包构造的基础。 第四步：更优的算法——格拉汉姆扫描法 该算法能在O(n log n)时间内解决问题，是经典算法。 预处理：找到最下最左的点作为基点p0。 排序：将所有其他点按照相对于p0的极角（与x轴正方向夹角）排序。极角相同的点，只保留离p0最远的。 扫描：使用一个栈来维护凸包顶点的候选序列。依次处理排序后的每个点： a. 检查如果栈顶的两个顶点与当前点构成一个“非左转”（即右转或共线），则弹出栈顶顶点（因为它被当前点“取代”，在凸包内部）。 b. 将当前点压入栈。 c. 这个“左转”判断同样通过计算向量叉积的正负来实现。 扫描完成后，栈中从底到顶的顶点序列就是逆时针的凸包。 其核心在于排序和一次线性扫描，排序主导复杂度，为O(n log n)。正确性基于凸包上任一顶点相邻两边必构成左转。 第五步：分治算法与上下凸壳法 另一种O(n log n)算法是“分治”思想：将点集按x坐标排序后分成左右两半，分别递归求凸包，再合并两个凸包。合并时需要找到连接左右凸包的“上、下”两条公切线。 更直观的变体是“上下凸壳法”：先按x坐标排序所有点，然后分别计算“上凸壳”（从最左点到最右点，斜率不断减小的链）和“下凸壳”（斜率不断增加的链），再合并。这本质上与格拉汉姆扫描一致，但排序方式不同。 第六步：最优算法与输出敏感性 理论上，平面凸包问题在代数判定树模型下的时间复杂度下界是Ω(n log n)。但存在一种“输出敏感”的Chan算法，其时间为O(n log h)，其中h是凸包顶点数。它结合了格拉汉姆扫描和礼品包裹法的思想，当h远小于n时非常高效。 第七步：扩展与应用 理解凸包算法是学习计算几何的基石。其应用广泛，包括： 模式识别（寻找物体的最小包围盒）。 路径规划与碰撞检测。 地理信息系统（GIS）中计算区域范围。 作为其他复杂几何算法（如Delaunay三角剖分、Voronoi图）的子例程。 掌握凸包算法，不仅在于理解其步骤，更在于领悟其中利用几何性质（如叉积判断方向、极角排序）来设计高效算法的核心思想。