算法（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. 转向判断的物理计算（叉积）
给定三个点
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)a, b, c，计算向量ab和bc的叉积（有符号面积的两倍）：
area2 > 0：左转（逆时针）→ 保留。
area2 < 0：右转（顺时针）→ 弹出栈顶。
area2 == 0：三点共线。在凸包算法中，通常删除中间点（保留最远的端点）或根据具体规则处理。
4. 为什么这个算法依赖于排序
排序的作用是：保证扫描过程是按照围绕最低点
p的逆时针方向进行的。你可以把
p想象成橡皮筋的一个固定端点。从p出发，按极角从小到大处理其他点，相当于一圈一圈地往外“包裹”这些点。如果处理顺序是乱的，你就无法判断何时该丢弃内部点。排序将二维的几何问题降维成了一个一维的扫描序列问题。整个算法的复杂度瓶颈在排序这一步，为O(N log N)。扫描本身是线性的O(N)。