算法（11）：Convex hull-5.6

凸包的物理来源是你有一组钉在板上的点比如图钉用一个橡皮筋从外部套住它们全部。橡皮筋绷紧后形成的那个多边形轮廓就是这些点的凸包。这个问题的计算目标就是找出这个多边形的顶点原始点集中的哪些点以及它们在边界上的顺序。1. 核心几何观察这是整个算法的物理依据如果沿着凸包的边界逆时针行走你在每一个顶点处都只会向左转即逆时针方向。这个性质是凸性的直接几何结果——凸多边形内部始终在边界路径的左侧。相反如果你在某个点处向右转顺时针那么这个点一定不在凸包边界上它位于凸包内部应该被舍弃。2. Graham 扫描算法的步骤PPT 上展示的算法是 Graham 扫描法的一个变体。第一步找最低点p在给定的点集中找到y坐标最小的点如果有多个取x最小的。这个点必然在凸包上因为在所有点中最南端的点不可能被任何两个点围住。第二步按极角排序以p为原点计算其他所有点相对于p的极角从正右方逆时针旋转到该点方向的角度。按极角从小到大排序。极角越小的点在从p出发的逆时针方向上越靠前。第三步扫描并丢弃右转点维护一个栈。按排序后的顺序依次处理每个候选点c如果栈中元素少于 2 个直接入栈。如果栈中至少有 2 个点取栈顶第二个点为a栈顶点为b判断从a → b → c的转向左转逆时针c可能是凸包顶点保留b将c入栈。右转顺时针b不可能是凸包顶点将b弹出栈。然后重复检查新的a、b、c直到b被保留或栈中少于 2 个点。扫描结束后栈中剩余的点按顺序依次连接就是凸包的逆时针顶点序列。3. 转向判断的物理计算叉积给定三个点a, b, c计算向量ab和bc的叉积有符号面积的两倍area2(b.x−a.x)×(c.y−a.y)−(b.y−a.y)×(c.x−a.x)area2(b.x−a.x)×(c.y−a.y)−(b.y−a.y)×(c.x−a.x)area2 0左转逆时针→ 保留。area2 0右转顺时针→ 弹出栈顶。area2 0三点共线。在凸包算法中通常删除中间点保留最远的端点或根据具体规则处理。4. 为什么这个算法依赖于排序排序的作用是保证扫描过程是按照围绕最低点p的逆时针方向进行的。你可以把p想象成橡皮筋的一个固定端点。从p出发按极角从小到大处理其他点相当于一圈一圈地往外“包裹”这些点。如果处理顺序是乱的你就无法判断何时该丢弃内部点。排序将二维的几何问题降维成了一个一维的扫描序列问题。整个算法的复杂度瓶颈在排序这一步为O(N log N)。扫描本身是线性的O(N)。