数学大学
H. Edge Chasing
计算几何 · 02. Geometric Intersection
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
H. Edge Chasing
计算几何 · 02. Geometric Intersection
Eliminating Sickles
追边法消镰刀：两个子凸包合并时，逐边「追逐」淘汰必被遮挡的镰刀形边界段。
镰刀段
合并后必被埋入内部的旧边界弧段
追逐
沿边界交替前进，逐步定位上桥与下桥
Example
追边例题：两个子凸包合并时上桥与下桥的定位全程演示。
桥定位
最右点与最左点之间寻找公切线
淘汰
桥之间的旧边界段整体丢弃
Analysis
追边法分析：合并线性，分治总代价 O(n log n)。
线性合并
每个边至多被追逐一次
递归合计
T(n)=2T(n/2)+O(n)
本节要点
- ✓追边法：逐边淘汰镰刀形内部弧段
- ✓上桥下桥定位后缝合
- ✓合并线性，总代价 O(n log n)
延伸主题：手动追一次边对比与公切线法的异同
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1追边法淘汰的「镰刀段」为什么一定不在新凸包上？
参考答案两子凸包之间的公切线（桥）把两包子集分开，桥之间的旧边界被两个子凸包的并「包」在中间，任何来自另一侧的点都比它更靠外。被包围的边界必是内部结构。
2追边法与「公切线查找法」在合并凸包时的效率对比如何？
参考答案两者都线性合并，差别在定位桥的方式：公切线法轮换试探切点，追边法沿边逐条前进。常数与实现复杂度有差，渐近阶相同，选熟悉的实现即可。
3镰刀段淘汰的判定条件是什么？
参考答案某子凸包的一段边界，若其两个端点都能被另一子凸包的对应点「看见」（即被推入内部），则该段是镰刀段。判定用 ToLeft 与距离配合完成。