数学大学
E. Jarvis March
计算几何 · 01. Convex Hull
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
E. Jarvis March
计算几何 · 01. Convex Hull
Selectionsort
Jarvis March 的结构神似选择排序：每轮从剩余点中「选出」下一个凸包顶点。
类比
选择排序每轮选最小，Jarvis 每轮选最「右转」的点
复杂度同构
每轮线性扫描，共 h 轮为 O(nh)
Strategy
策略：从最左下的点出发，反复选择相对当前点「最右转」的候选点作为下一顶点。
候选扫描
对所有点按 ToLeft 逐一挑战当前候选
保证
扫描结束时选出的点必为下一极点
Coherence
连贯性：相邻两轮的选点决策共享大量比较，重复信息可被利用。
重叠比较
上一轮的比较结果下一轮依然有效
优化余地
利用连贯性可进一步减少实际计算
To-Left Test
Jarvis 中的核心判定：候选点是否在当前边右侧，右转最多者胜出。
挑战制
新候选若在「候选边」右侧即取代旧候选
退化
共线时取距离更远者，避免漏掉中间点
Degeneracy
退化情形：多点共线时同一方向上出现并列候选，需按距离打破平局。
共线并列
最右转相同则取离当前点最远的候选
重复点
输入中的重复点应预先剔除
Lowest-Then-Leftmost
起点选取：先最低、同高再最左的点必是凸包顶点，作为第 0 号极点。
确定性起点
唯一保证属于凸包的规范起点
作用
使算法从确定位置开始逐极点推进
Implementation
实现要点：双层循环外层定当前点、内层挑战下一候选，h 轮后回到起点终止。
循环骨架
外层逐极点，内层逐候选挑战
终止条件
下一个顶点回到起点即完成一圈
Output Sensitivity
输出敏感性：Jarvis 的 O(nh) 与凸包规模 h 挂钩——顶点少则快。
h 的角色
凸包顶点数 h 通常远小于 n
对比
Graham 的 O(n log n) 不看 h，各有胜负
本节要点
- ✓Jarvis March = 几何版选择排序
- ✓每轮选相对当前边最右转的候选
- ✓共线取最远，起点最低再最左
- ✓输出敏感 O(nh)，顶点少时极快
延伸主题：实现 Jarvis March构造 h 极小的输入测性能
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1「输出敏感」是什么意思？对算法选择有什么指导？
参考答案运行时间由输出本身的规模（h）决定：凸包顶点极少的海量点集，Jarvis 的 O(nh) 可能远快于 O(n log n) 的 Graham。知道输出的预期规模，才能选对算法。
2Jarvis March 的「挑战制」与选择排序的「擂台制」如何对应？
参考答案选择排序内层循环用「当前最小」做擂台逐个挑战；Jarvis 用「当前最佳下一顶点」做擂台，挑战的判据是 ToLeft 右转与距离。同一个擂台模式，换了比较器而已。
3「h 轮、每轮 n 次比较」的 O(nh) 中，h 何时会退化到接近 n？
参考答案点均匀分布在圆周上时几乎所有点都是极点，h≈n，此时 O(nh)=O(n²)。相反，绝大多数点挤在内部、只有少数顶点时 h 极小，Jarvis 反而大占便宜。