扫描线

What · 是什么

扫描线（Sweep Line）是一种把二维问题化为一维的通用技巧：让一条线沿某个方向扫过平面，在遇到『事件』（点的进入/离开、线段端点、矩形边）时更新一维数据结构，从而把静态二维问题转换为动态一维问题。经典应用：① 矩形面积并（横边事件+线段树维护覆盖长度）；② 矩形周长并（横纵两个方向各扫一次）；③ 二维数点/离线区间查询（扫一维、树状数组维护另一维）；④ 线段求交、最近点对。复杂度 O((n+m)log n)，是计算几何与数据结构结合的最高频套路之一。

Why · 为什么

How · 实现

伪代码

# 矩形面积并
edges = []
for each rect(x1,y1,x2,y2):
  edges.append((y1, x1, x2, +1))   # 下边
  edges.append((y2, x1, x2, -1))   # 上边
xs = sorted(set of all x1,x2)       # 离散化
sort(edges) by y
build segtree over xs intervals
ans = 0
for i in range(len(edges)):
  ans += (edges[i].y - edges[i-1].y) * segtree.len(covered>0)
  segtree.update(x-range, edges[i].delta)
return ans

Python 实现

class SegTree:
    """覆盖次数 + 覆盖长度 线段树 (区间加, 不递归下传)."""
    def __init__(self, xs):
        self.xs = xs                # 离散化坐标 (升序)
        self.cov = [0] * (4 * len(xs))
        self.len = [0.0] * (4 * len(xs))

    def _update(self, node, l, r, ql, qr, val):
        if qr <= l or r <= ql:
            return
        if ql <= l and r <= qr:
            self.cov[node] += val
        else:
            mid = (l + r) // 2
            self._update(node * 2, l, mid, ql, qr, val)
            self._update(node * 2 + 1, mid, r, ql, qr, val)
        if self.cov[node] > 0:
            self.len[node] = self.xs[r] - self.xs[l]
        elif r - l == 1:
            self.len[node] = 0.0
        else:
            self.len[node] = self.len[node * 2] + self.len[node * 2 + 1]

    def update(self, ql, qr, val):
        """对 [xs[ql], xs[qr]) 区间加 val."""
        self._update(1, 0, len(self.xs) - 1, ql, qr, val)

    def total_len(self):
        return self.len[1]


def union_area(rects):
    """矩形面积并. rects: (x1,y1,x2,y2) 左下右上."""
    xs = sorted(set([x for r in rects for x in (r[0], r[2])]))
    idx = {v: i for i, v in enumerate(xs)}
    events = []
    for x1, y1, x2, y2 in rects:
        events.append((y1, idx[x1], idx[x2], 1))
        events.append((y2, idx[x1], idx[x2], -1))
    events.sort(key=lambda e: e[0])
    seg = SegTree(xs)
    ans = 0.0
    last_y = events[0][0]
    for y, l, r, d in events:
        ans += (y - last_y) * seg.total_len()
        seg.update(l, r, d)
        last_y = y
    return ans


def union_area_brute(rects):
    """暴力网格计数(整数坐标小范围)用于交叉验证."""
    pts = set()
    for x1, y1, x2, y2 in rects:
        for x in range(x1, x2):
            for y in range(y1, y2):
                pts.add((x, y))
    return len(pts)


if __name__ == "__main__":
    # 两个重叠矩形
    rects = [(0, 0, 4, 4), (2, 2, 6, 6)]
    # 并面积 = 4*4 + 4*4 - 2*2 = 28
    assert abs(union_area(rects) - 28) < 1e-9
    # 三个矩形覆盖测试 (整数小范围暴力对照)
    rects2 = [(0, 0, 3, 3), (1, 1, 5, 4), (2, 0, 4, 5)]
    assert abs(union_area(rects2) - union_area_brute(rects2)) < 1e-9
    # 相离矩形
    rects3 = [(0, 0, 1, 1), (5, 5, 7, 8)]
    assert abs(union_area(rects3) - union_area_brute(rects3)) < 1e-9
    # 完全包含
    rects4 = [(0, 0, 6, 6), (1, 1, 3, 3)]
    assert abs(union_area(rects4) - 36) < 1e-9

    # 随机交叉验证
    import random
    random.seed(5)
    for _ in range(50):
        n = random.randint(1, 6)
        rs = []
        for _ in range(n):
            x1 = random.randint(-5, 5)
            x2 = random.randint(-5, 5)
            y1 = random.randint(-5, 5)
            y2 = random.randint(-5, 5)
            if x1 > x2: x1, x2 = x2, x1
            if y1 > y2: y1, y2 = y2, y1
            if x1 == x2 or y1 == y2:
                x2 += 1
                y2 += 1
            rs.append((x1, y1, x2, y2))
        a = union_area(rs)
        b = union_area_brute(rs)
        assert abs(a - b) < 1e-9, (rs, a, b)
    print("All tests passed.")

易错点

• 事件排序后同一 y 的多条边：面积并要先加新覆盖再算 ans 会漏/重复，标准做法是『先计算 ans 再更新』，或对同一 y 批量处理
• 线段树叶子是区间 [xs[i], xs[i+1]) 而非单点，离散化后线段数 = 点数-1
• 离散化必须去重并排序，映射到区间下标而非坐标值
• 覆盖次数 cov 用 int，覆盖长度 len 需要 double/long long；二者存储逻辑不同
• 面积并时浮点坐标用 ≤/≥ 的 EPS 边界处理要一致，否则相邻矩形边产生负宽度
• 二维数点把询问拆成 4 个前缀（容斥）别漏项

例题

信源

• OI Wiki✓ https://oi-wiki.org/geometry/scanning/
• 书籍✓ CPH ch30 Sweep-line algorithms (p305-317)