K. Divide-And-Conquer (1)
数学大学
K. Divide-And-Conquer (1
计算几何 · 01. Convex Hull
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
K. Divide-And-Conquer (1
计算几何 · 01. Convex Hull
Merge
分治凸包的核心是合并：左右两半各自求凸包，再缝成一个。
分治结构
点按 x 排序对半分，递归求解后合并
合并产物
上半桥与下半桥连接两个子凸包
Common Kernel
各子问题共享同一套几何内核：叉积判转向是最基本的原子操作。
叉积判向
叉积正负即左转或右转
复用
所有凸包算法共用这一几何判定
Interior
内部点：合并后落在新凸包内部的点被永久淘汰。
识别
位于两条桥之间的子凸包顶点是内部点
淘汰
淘汰后不再参与后续任何计算
Exterior
外部点：留在合并后凸包边界上的顶点，继续参与更上层合并。
保留
桥端点之间的边界顶点全部保留
向上传递
保留下来的点构成上层合并的输入
本节要点
- ✓分治凸包：递归分半后合并
- ✓叉积判向是共享内核
- ✓合并区分内部点与外部点
延伸主题：实现一次凸包合并分析合并的时间成本
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1分治凸包为什么把点先按 x 排序？
参考答案按 x 排序保证左右两半在竖直方向可分，合并时上下桥的查找有明确方向，且左右凸包不会交叉缠绕。排序的一次投入换来每层合并的有序性。
2内部点被淘汰后如果后来又成了边界点怎么办？
参考答案不会发生：凸包合并后内部点永远在凸区域内，任何后续合并只会扩大凸包、进一步把它埋进去。一次淘汰终身淘汰，这正是淘汰安全的依据。
3只有两个点或所有点共线时，分治凸包怎么处理？
参考答案两点构成一条线段（上下桥重合）；全共线时凸包退化为一条线段，缝合产生的多边形面积为零。实现中对退化情形显式分支，避免除零与空面。