扫描线范式

形式陈述 ​

扫描线算法由三部分组成：沿固定方向单调移动的 sweep line；按扫描坐标排序的 event queue；保存当前与扫描线相交对象之横向次序或其他局部关系的 status structure。核心不变量是：两个连续事件之间，所维护的组合次序不变；只有端点、交点或问题特定临界位置会触发局部更新。

在线段相交的 Bentley–Ottmann 算法中，事件队列由优先队列公理库优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。按 $x$ 坐标和明确 tie-break 顺序组织，状态用平衡搜索树公理库平衡搜索树Balanced search tree以结构不变量保证对数高度和最坏对数搜索时间的二叉搜索树族。按当前扫描位置的 $y$ 次序保存活动线段。左端点插入线段并检查新相邻对，右端点删除并检查原上下邻居，相交事件交换两线段次序并更新局部邻接。一般位置下报告 $K$ 个交点的时间为 $O((n+K)\log n)$，空间为 $O(n+K)$ 或按事件去重实现调整。

正确性来自邻接证书：若两条线段将成为下一对相交对象，在它们相交前不可能一直被第三条活动线段隔开；因此只需为状态中的相邻对安排候选事件，而非检查全部 $(\genfrac{}{}{0ex}{}{n}{2})$ 对。

直觉 ​

扫描线把二维静态图形变成一段时间演化的一维截面。事件之间没有组合变化，算法可以跳过连续坐标，只在少数临界位置更新；状态结构则保存“此刻谁与谁相邻”，把潜在全局相交压缩成局部候选。

计算几何公理库计算几何问题Computational geometry problem以点、线段、多边形等几何对象为输入并要求组合或数值几何输出的问题族。中的难点不是“从左往右扫”这句动作，而是选出足以捕获所有变化的事件，并证明状态在事件之间稳定。

例子与边界 ​

两条目前不相邻的活动线段之间若夹着第三条线段，它们不能在第三条仍夹在中间时率先相交；要么某个端点先改变活动集合，要么第三条先与其中一条交换次序。由此，插入、删除或交换后只检查新形成的邻居就足够。

状态比较器依赖当前扫描坐标，普通有序容器不会自动在比较结果变化时重排元素。算法之所以仍合法，是因为次序只在已经排入队列的相交事件处交换；若比较器随意读取全局浮点位置而没有事件不变量，树的内部顺序可能失效。

竖直线段、重合端点、三线同交点和重叠线段会让多个事件共享坐标或交集不再是单点。实现需采用精确方向测试公理库方向判定Orientation test用二维或高维行列式符号判断点组转向或仿射定向的基本谓词。、事件批处理、符号扰动或明确拒绝退化；仅靠浮点 epsilon 无法给出一致的全序保证。

推论与应用 ​

扫描线用于线段相交、矩形并面积、区间覆盖和多边形布尔运算。不同问题可以复用 event/status/invariant 框架，但事件类型和状态含义必须重新证明，不能把 Bentley–Ottmann 的邻接结论机械移植。

输出敏感界中的 $K$ 是实际报告事件数；当交点本身有平方多个时，算法不可能在线性时间输出全部结果。若只需判断是否存在相交，可在首个证书出现时提前终止并得到更小空间。

参考资料

• Jon L. Bentley and Thomas A. Ottmann, “Algorithms for Reporting and Counting Geometric Intersections,” IEEE Transactions on Computers C-28(9), 1979, pp. 643–647.
• Mark de Berg et al., Computational Geometry: Algorithms and Applications, 3rd ed., Springer, 2008, Ch. 2.