扫描线算法（Sweep Line Algorithm）

字数 2210 2025-10-26 09:00:43

扫描线算法（Sweep Line Algorithm）

扫描线算法是一种用于高效处理几何问题的算法。它的核心思想是引入一条虚拟的扫描线（通常是垂直或水平的直线），让这条线按照一定顺序（例如从左到右）扫描整个平面，并在移动过程中动态维护和处理与扫描线相交的几何对象。

问题描述：矩形的面积并（Union Area of Rectangles）
计算平面上 N 个轴对齐（边平行于坐标轴）的矩形覆盖的总面积。矩形之间可能存在重叠，重叠部分只计算一次。

解题过程

问题分析
最直观的方法是使用容斥原理，但矩形数量多时，计算所有交集会非常复杂。扫描线算法可以更高效地解决这个问题。核心思路是将二维的面积计算问题，通过扫描线降维成一维的线段长度计算问题。
算法核心思想
- 想象一条垂直的扫描线，从最左边的矩形的左侧开始，向右一直扫描到最右边的矩形的右侧。
- 扫描线在移动过程中，会不断地与某些矩形的垂直边相交。这些垂直边被称为“事件点”（Event），它们标志着扫描线所处的状态发生了改变（例如，开始遇到一个新的矩形，或者离开了一个矩形）。
- 我们需要维护的是：在当前扫描线的位置，所有被矩形覆盖的y轴方向上的区间（即线段）的总长度。这个长度我们称之为“有效高度”。
- 那么，在两个相邻的事件点之间，扫描线移动的这一小段水平距离，乘以当前的“有效高度”，就是这一小段竖条矩形覆盖的面积。将所有这样的小竖条面积加起来，就是总面积。
详细步骤

步骤一：事件预处理
我们将每个矩形表示为两条垂直边：
- 入边（开始边）：(x1, y1, y2, 'start')，对应矩形的左边界 x1。
- 出边（结束边）：(x2, y1, y2, 'end')，对应矩形的右边界 x2。
  其中，y1 和 y2 分别是矩形底边和顶边的y坐标。
收集所有矩形的入边和出边，构成一个“事件列表”。然后，根据这些边的x坐标进行排序。

步骤二：扫描过程
初始化总面积为0，并创建一个数据结构（通常是有序集合或线段树）来记录当前y轴方向上被覆盖的线段。

按x坐标从小到大遍历排序后的事件列表：
1. 处理当前事件：设当前事件的x坐标为 current_x。
  - 如果事件是“入边”，则将这条边对应的y区间 [y1, y2] 加入到我们的覆盖集合中。
  - 如果事件是“出边”，则将这条边对应的y区间 [y1, y2] 从覆盖集合中移除。
2. 计算有效高度：在处理完当前事件后，我们需要计算当前覆盖集合中所有y区间的并集总长度。这就是“有效高度”。
  - 例如，当前覆盖集合中有 [1, 3] 和 [2, 4] 两个区间，它们的并集是 [1, 4]，所以有效高度是 3。
3. 计算面积：找到下一个事件的x坐标 next_x（如果存在）。那么，从 current_x 到 next_x 这段水平宽度是 (next_x - current_x)。将这段宽度乘以步骤2计算出的“有效高度”，就得到了这两个事件点之间的小竖条面积。将这块面积累加到总面积中。
4. 移动到下一个事件：继续处理事件列表中的下一个事件。
步骤三：y区间的高效管理
如何高效地维护y轴上的覆盖区间并计算其并集长度，是算法的关键。有几种方法：
- 方法A：有序列表法
  - 我们维护一个列表，存储当前所有“活跃”的y区间（即被扫描线穿过的矩形的y区间）。
  - 插入：当加入一个新的y区间 [new_y1, new_y2] 时，需要与列表中现有的区间进行合并操作，确保列表中的区间始终是不重叠且有序的。这类似于“合并区间”算法。
  - 删除：当移除一个y区间时，从列表中找到对应的区间并将其移除，可能需要拆分区间。
  - 计算长度：合并后的区间列表，将所有区间的 (y2 - y1) 相加即可得到有效高度。
  - 这种方法每次插入/删除的平均时间复杂度约为O(n)，n是当前活跃区间的数量。
- 方法B：线段树法（更高效）
  - 如果y坐标的值域很大或需要离散化，使用线段树是更优选择。
  - 我们将y坐标的可能取值进行离散化，映射到连续的整数索引上。
  - 构建一个线段树，树的每个节点代表一个y轴上的区间。节点维护两个值：
    - count：该节点代表的区间被完整覆盖的次数。
    - len：该节点代表的区间中，被覆盖部分的实际长度。
  - 更新：当处理一个事件（插入或删除一个y区间）时，我们在线段树上更新对应的区间。如果某个节点的 count 变为正数，则该节点代表的整个区间都被覆盖，其 len 就是区间的实际长度；如果 count 变为0，则其 len 由其左右子节点的 len 汇总而来。
  - 查询：有效高度就是线段树根节点的 len 值。
  - 使用线段树，每次更新和查询的时间复杂度可以优化到O(log n)。
算法总结
扫描线算法通过“事件驱动”和“降维”的思想，将复杂的二维平面问题转化为一维的区间管理问题。其通用步骤如下：
- 定义事件：确定扫描线的移动方向和触发状态改变的点（事件）。
- 排序事件：将所有事件按扫描线移动方向排序。
- 扫描处理：按顺序处理事件，在事件点更新被扫描线穿过的对象集合的状态。
- 维护信息：在扫描过程中，动态维护一个关键信息（如y轴覆盖长度）。
- 累积结果：根据关键信息计算两个事件点之间的局部解，并累积得到最终答案。

扫描线算法（Sweep Line Algorithm）扫描线算法是一种用于高效处理几何问题的算法。它的核心思想是引入一条虚拟的扫描线（通常是垂直或水平的直线），让这条线按照一定顺序（例如从左到右）扫描整个平面，并在移动过程中动态维护和处理与扫描线相交的几何对象。问题描述：矩形的面积并（Union Area of Rectangles）计算平面上 N 个轴对齐（边平行于坐标轴）的矩形覆盖的总面积。矩形之间可能存在重叠，重叠部分只计算一次。解题过程问题分析最直观的方法是使用容斥原理，但矩形数量多时，计算所有交集会非常复杂。扫描线算法可以更高效地解决这个问题。核心思路是将二维的面积计算问题，通过扫描线降维成一维的线段长度计算问题。算法核心思想想象一条垂直的扫描线，从最左边的矩形的左侧开始，向右一直扫描到最右边的矩形的右侧。扫描线在移动过程中，会不断地与某些矩形的垂直边相交。这些垂直边被称为“事件点”（Event），它们标志着扫描线所处的状态发生了改变（例如，开始遇到一个新的矩形，或者离开了一个矩形）。我们需要维护的是：在当前扫描线的位置，所有被矩形覆盖的 y轴方向上的区间（即线段）的总长度。这个长度我们称之为“有效高度”。那么，在两个相邻的事件点之间，扫描线移动的这一小段水平距离，乘以当前的“有效高度”，就是这一小段竖条矩形覆盖的面积。将所有这样的小竖条面积加起来，就是总面积。详细步骤步骤一：事件预处理我们将每个矩形表示为两条垂直边：入边（开始边）： (x1, y1, y2, 'start') ，对应矩形的左边界 x1 。出边（结束边）： (x2, y1, y2, 'end') ，对应矩形的右边界 x2 。其中， y1 和 y2 分别是矩形底边和顶边的y坐标。收集所有矩形的入边和出边，构成一个“事件列表”。然后，根据这些边的x坐标进行排序。步骤二：扫描过程初始化总面积为0，并创建一个数据结构（通常是有序集合或线段树）来记录当前y轴方向上被覆盖的线段。按x坐标从小到大遍历排序后的事件列表：处理当前事件：设当前事件的x坐标为 current_x 。如果事件是“入边”，则将这条边对应的y区间 [y1, y2] 加入到我们的覆盖集合中。如果事件是“出边”，则将这条边对应的y区间 [y1, y2] 从覆盖集合中移除。计算有效高度：在处理完当前事件后，我们需要计算当前覆盖集合中所有y区间的并集总长度。这就是“有效高度”。例如，当前覆盖集合中有 [1, 3] 和 [2, 4] 两个区间，它们的并集是 [1, 4] ，所以有效高度是 3。计算面积：找到下一个事件的x坐标 next_x （如果存在）。那么，从 current_x 到 next_x 这段水平宽度是 (next_x - current_x) 。将这段宽度乘以步骤2计算出的“有效高度”，就得到了这两个事件点之间的小竖条面积。将这块面积累加到总面积中。移动到下一个事件：继续处理事件列表中的下一个事件。步骤三：y区间的高效管理如何高效地维护y轴上的覆盖区间并计算其并集长度，是算法的关键。有几种方法：方法A：有序列表法我们维护一个列表，存储当前所有“活跃”的y区间（即被扫描线穿过的矩形的y区间）。插入：当加入一个新的y区间 [new_y1, new_y2] 时，需要与列表中现有的区间进行合并操作，确保列表中的区间始终是不重叠且有序的。这类似于“合并区间”算法。删除：当移除一个y区间时，从列表中找到对应的区间并将其移除，可能需要拆分区间。计算长度：合并后的区间列表，将所有区间的 (y2 - y1) 相加即可得到有效高度。这种方法每次插入/删除的平均时间复杂度约为O(n)，n是当前活跃区间的数量。方法B：线段树法（更高效）如果y坐标的值域很大或需要离散化，使用线段树是更优选择。我们将y坐标的可能取值进行离散化，映射到连续的整数索引上。构建一个线段树，树的每个节点代表一个y轴上的区间。节点维护两个值： count ：该节点代表的区间被完整覆盖的次数。 len ：该节点代表的区间中，被覆盖部分的实际长度。更新：当处理一个事件（插入或删除一个y区间）时，我们在线段树上更新对应的区间。如果某个节点的 count 变为正数，则该节点代表的整个区间都被覆盖，其 len 就是区间的实际长度；如果 count 变为0，则其 len 由其左右子节点的 len 汇总而来。查询：有效高度就是线段树根节点的 len 值。使用线段树，每次更新和查询的时间复杂度可以优化到O(log n)。算法总结扫描线算法通过“事件驱动”和“降维”的思想，将复杂的二维平面问题转化为一维的区间管理问题。其通用步骤如下：定义事件：确定扫描线的移动方向和触发状态改变的点（事件）。排序事件：将所有事件按扫描线移动方向排序。扫描处理：按顺序处理事件，在事件点更新被扫描线穿过的对象集合的状态。维护信息：在扫描过程中，动态维护一个关键信息（如y轴覆盖长度）。累积结果：根据关键信息计算两个事件点之间的局部解，并累积得到最终答案。