E. BO Algorithm: Implementation
数学大学
E. BO Algorithm: Impleme
计算几何 · 02. Geometric Intersection
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
E. BO Algorithm: Impleme
计算几何 · 02. Geometric Intersection
Degeneracy
退化处理：重合点使最小间隔为零，空桶造成候选间隔的跳跃。
重合点
重合点对间隔为零，可直接短路返回
空桶跳越
非空桶之间隔着空桶时，候选间隔按边界差计
Event Queue
事件队列：扫描线算法的心脏——按坐标排序的事件依次触发处理。
事件
每个输入点是一个事件
组织
优先队列或预排序数组充当队列
Events & Operations
事件与操作的对应：每个事件触发一次状态更新与一次候选间隔检验。
处理流程
弹出事件 → 更新结构 → 检验新候选
复杂度
每事件 O(log n) 的队列操作
Sweepline Status
扫描线状态：记录当前已见点中「当前点的前驱与后继」，最小间隔只在相邻点间产生。
前驱后继
新点的候选间隔只与其前驱、后继有关
结构
平衡树维护已插入点的有序序列
本节要点
- ✓重合点短路，空桶按边界差计
- ✓事件队列按坐标驱动扫描
- ✓最小间隔只在相邻点间产生
延伸主题：实现事件驱动的 Min-Gap对比桶法与扫描线法性能
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1扫描线算法中为什么新点的候选间隔只需与其前驱、后继比较？
参考答案已插入的点保持有序，新点的插入位置由前驱与后继夹定：它与更远的点之间必然隔着前驱或后继，间隔只会更大。因此相邻对的间隔是唯一需要检验的候选。
2桶法与扫描线法（事件驱动）如何选择？
参考答案一维且范围有限时桶法真线性、实现简单；点分布范围不可控或需要在线插入时，扫描线/平衡树结构更稳健。数据形态与操作类型决定选择。
3事件队列用「预排序数组」实现的前提是什么？
参考答案所有事件在算法开始前已知（离线场景）——排序一次即可。在线场景事件陆续到达，必须改用支持动态插入的优先队列（堆），操作复杂度升为对数级。