I. Graham Scan: Correctness
数学大学
I. Graham Scan: Correctn
计算几何 · 01. Convex Hull
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
I. Graham Scan: Correctn
计算几何 · 01. Convex Hull
Left Turn
左转判定：连续三点构成左转（逆时针）时保留中间点。
判据
ToLeft 测试为正即左转
不变式
栈内始终满足相邻三点左转
Right Turn
右转即凹：出现右转说明中间点是凹点，必须弹出。
弹栈条件
栈顶两点与新点右转时弹出栈顶
重复直到
反复弹栈直到左转或栈中不足两点
Presorting
预排序的正确性作用：极角序保证扫描一遍就能确定每个点的最终归宿。
次序保证
先到的点不可能在后到点的极角内侧
与回溯
弹栈即回溯：撤销被证明非顶点的选择
本节要点
- ✓左转保留，右转弹栈
- ✓栈的不变式：相邻三点始终左转
- ✓预排序保证一遍扫描定局
延伸主题：追踪一次扫描的栈变化证明弹栈不会错杀顶点
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1弹栈「错杀」的可能顶点为什么其实不会是顶点？
参考答案右转意味着中间点位于前后两点连线的右侧，即被新点与更早点夹成凹角——它必然落在剩余点集凸包的内部。弹栈淘汰的是被证明非极点的点，不会误伤真顶点。
2Presorting 的 O(n log n) 会不会成为整个算法的瓶颈？
参考答案会，而且恰恰是瓶颈所在：扫描本身只花 O(n)。这并非缺点——结合下界 Ω(n log n)，Graham 的总复杂度已达到理论最优，排序成本无法也不必再压。
3「共线点算不算凸包顶点」对扫描逻辑有什么影响？
参考答案若保留共线点，弹栈条件应为「右转才弹」（不弹共线）；若不保留，「非严格左转也弹」。两种约定都正确，但必须全程一致，否则凸包会出现共线残留点。