扫描线范式 | Codeboy's Blog

形式陈述

扫描线算法由三部分组成：沿固定方向单调移动的 sweep line；按扫描坐标排序的 event queue；保存当前与扫描线相交对象之横向次序或其他局部关系的 status structure。核心不变量是：两个连续事件之间，所维护的组合次序不变；只有端点、交点或问题特定临界位置会触发局部更新。若所有事件预先已知，排好序的数组即可逐项取出；动态产生新事件时才需要可更新的事件结构。横截面状态也应按任务选择表示。

在线段相交的 Bentley–Ottmann 算法中，事件队列由优先队列按 $x$ 坐标和明确 tie-break 顺序组织，状态用平衡搜索树按当前扫描位置的 $y$ 次序保存活动线段。左端点插入线段并检查新相邻对，右端点删除并检查原上下邻居，相交事件交换两线段次序并更新局部邻接。选取支持对数时间插入、取最小的事件队列，以及 AVL 或红黑树等支持最坏对数更新的状态结构。所有几何比较按单位成本计时，一般位置下报告 $K$ 个交点的时间为 $O((n+K)\log n)$ ，空间为 $O(n+K)$ 或按事件去重实现调整。

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

直觉

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

计算几何中的难点不是“从左往右扫”这句动作，而是选出足以捕获所有变化的事件，并证明状态在事件之间稳定。

例子与边界

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

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

竖直线段、重合端点、三线同交点和重叠线段会让多个事件共享坐标或交集不再是单点。实现需采用精确方向测试、事件批处理、符号扰动或明确拒绝退化；仅靠浮点 epsilon 无法给出一致的全序保证。

推论与应用

扫描线用于线段相交、矩形并面积、区间覆盖和多边形布尔运算。单调多边形划分只在顶点处更新活动左边界，并用 helper 记录 merge 顶点尚未完成的向下连接；它复用 event/status 框架，却需要新的可见性不变量。Bentley–Ottmann 的相邻线段交点证书不能机械移植到 helper 的正确性证明中。

输出敏感界中的 $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.

形式陈述 ​

反向链接

形式陈述