G. Graham Scan: Algorithm
数学大学
G. Graham Scan: Algorith
计算几何 · 01. Convex Hull
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
G. Graham Scan: Algorith
计算几何 · 01. Convex Hull
Preprocessing
Graham 扫描预处理：以最低再最左点为原点，其余点按极角排序。
基准点
最低再最左的点必为凸包顶点，定为原点
极角排序
绕基准点的极角从小到大排其余点
Scan
扫描：依次读入排序后的点，用栈维护——新点使转向非左转时弹栈。
压栈
每个点先压栈
弹栈
栈顶两点与新点构成右转或共线时弹栈
Simplest Cases
最简情形自查：零点、一点、两点与全部共线的退化输入。
小输入
不足三个点时直接返回原序列
全共线
凸包退化为一条线段的两个端点
本节要点
- ✓预处理：基准点 + 极角排序
- ✓扫描：栈顶右转即弹栈
- ✓退化输入显式分支处理
延伸主题：实现 Graham 扫描用共线点集测试退化处理
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么极角排序后「从左到右」扫描就一定能绕出凸包？
参考答案极角序保证所有点绕基准点逆时针排布，凸包顶点在这个次序中出现，非顶点被夹在中间。栈的弹栈操作恰好剔除那些「右转」造成的凹陷，留下 Pure 的逆时针凸边界。
2极角排序时遇到与基准点相同极角的点怎么办？
参考答案相同极角的多个点按到基准点的距离排序，距离近的在前；扫描时中间的点会因共线弹栈，只保留最远的那个。也可以只保留最远点、删除其余，预处理更干净。
3Graham 扫描输出的顶点顺序是什么方向？
参考答案极角从小到大扫描，弹栈维护左转，最终栈中从底到顶是逆时针方向的凸包顶点序列。需要顺时针输出时整体反转即可。