D. Incremental Construction
数学大学
D. Incremental Construct
计算几何 · 01. Convex Hull
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
D. Incremental Construct
计算几何 · 01. Convex Hull
Decrease and Conquer
减治策略：从少数点的凸包出发，逐个加入新点并维护凸包。
递推
已知前 k 个点的凸包，处理第 k+1 个点
与分治之别
减治逐个添加，分治成块合并
In-Convex-Polygon Test
新点在凸包内的判定：对每条边做 ToLeft 测试，全部同侧即在内。
O(h) 检查
h 为当前凸包边数
在内即弃
新点在内则凸包不变，处理下一点
Why Not Binary Search
为什么不用二分查找定位：新点在外部时它可能「看见」任意长的边界弧段。
切点可能多个方向
外点的支持线与可见弧不保证单调
结论
凸多边形二分只适用于「点在内」的判定
Support-Lines
支撑线：过外点与凸包相切的直线，切点即新凸包的接驳位置。
两条支撑线
左切点与右切点界定可见弧段
几何意义
支撑线旋转扫描时最先触碰凸包的位置
Pattern Of Turns
转向模式：沿凸包边行进时左右转的交替规律，用来定位切点。
转向记录
逐边记录 ToLeft 结果的序列
切点特征
转向模式翻转处即为左右切点
Exterior/Interior
外点插入：删除可见弧段上的边，用两条新边连接外点与弧端点。
删边
可见弧上的旧边全部删除
补边
外点与弧两端点各连一条新边
本节要点
- ✓减治：逐点插入维护凸包
- ✓内点 O(h) 检查后直接跳过
- ✓外点：支撑线定切点，删可见弧补新边
延伸主题：实现逐点插入凸包构造最坏输入测性能
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1增量构造的最坏时间复杂度是多少？由什么输入触发？
参考答案每插入一个外点需 O(h) 定位并重建，h 可达当前点数，总计 O(n²)。最坏输入是点按「恰好都在当前凸包外」的次序到达，如按极角螺旋排列的点集。
2减治法「先检查在内、再处理在外」的次序为什么重要？
参考答案绝大多数新点落在当前凸包内部（尤其随机均匀分布时），O(h) 的内置检查让它们被快速跳过，摊还成本极低。先做便宜的排除测试，再动昂贵的重建，是几何算法通用的效率纪律。
3新点恰好在当前凸包边界上（共线）怎么处理？
参考答案三种约定：忽略（凸包不变）、替换共线边的中途点、或保留为边界共线点。计数类应用通常忽略，几何应用按是否需要「边界点全保留」决定。