# 扫描线算法：计算重叠矩形的并集面积 思考这样一个问题：我们如何判断两个文本框的可见内容到底重叠了多少？ 文字渲染以后，可以拆成若干个可见片段。程序用矩形记录每个片段实际占据的位置，这些矩形可以叫作墨迹矩形。 为了算出两个文本框的重叠比例，我们需要先求 A 的墨迹矩形并集、B 的墨迹矩形并集，以及两者交集矩形的并集。三个计算最后都落到同一个问题： **一组矩形可能互相重叠，如何计算它们的并集面积？** ![文字墨迹矩形先求并集面积，再用于计算两个文本框的重叠比例](https://herblab.online/qwen-imgs/sweep-line-05-ink-application-v1.png) ## 1. 先算两个矩形 先看两个矩形： - A：X 为 0～100，Y 为 0～50，面积是 100 × 50 = 5000。 - B：X 为 60～150，Y 为 30～80，面积是 90 × 50 = 4500。 它们的交集在 X 方向宽 40，在 Y 方向高 20，交集面积是 40 × 20 = 800。如果直接计算 5000 + 4500，这 800 会出现两次。 ![直接相加会把 40×20 的交集重复计算，矩形并集面积为 8700](https://herblab.online/qwen-imgs/sweep-line-02-double-count-v1.png) 并集面积应为： ```text 5000 + 4500 - 800 = 8700 ``` 两个矩形时，减掉一次交集就够了。矩形一多，交集之间还可能继续重叠，逐项做容斥很快会失控。 ## 2. 矩形一多，怎么办？ 想象一条竖线从平面左边缓慢向右移动。只要它没有越过任何矩形的左边或右边，当前穿过的矩形集合就不会变化。 所以我们不用逐个检查平面上的点，只处理相邻 X 边界之间的竖条。每条竖条内部，问题会从二维面积变成一维长度：Y 轴上到底覆盖了多长？这就是本文使用的扫描线方法。 ![扫描线沿 X 轴切片，并在每条竖条中合并 Y 区间](https://herblab.online/qwen-imgs/sweep-line-01-cover-v1.png) 接下来分四步计算： 1. 收集 X 边界并排序去重。 2. 把相邻 X 边界之间的区域切成竖条。 3. 找出覆盖当前竖条的矩形，合并它们的 Y 区间。 4. 用“竖条宽度 × Y 覆盖长度”得到面积，再累加。 这里的矩形都与坐标轴平行，用 `left`、`top`、`width`、`height` 表示，对应区间 `[left, left + width) × [top, top + height)`。Y 轴向上还是向下不影响长度计算；宽或高为 0 的矩形没有面积。 ## 3. 第一步：收集所有 X 边界 面积的覆盖情况只会在矩形的左边或右边改变。A 提供 0、100，B 提供 60、150，排序去重后得到： ```text 0、60、100、150 ``` 相邻边界切出三条竖条：0～60、60～100、100～150，宽度分别是 60、40、50。 ![X 边界 0、60、100、150 把平面切成宽度 60、40、50 的三条竖条](https://herblab.online/qwen-imgs/sweep-line-03-x-slices-v1.png) 这种只保留关键坐标、再处理相邻区间的做法叫坐标离散化。坐标可以很大，算法真正关心的仍然只有这些边界。 ## 4. 第二步：逐条扫描 X 区间 现在依次查看三条竖条。一个矩形只有完整覆盖当前 `[x1, x2)`，才会给这条竖条贡献 Y 区间。 - 0～60：只有 A 覆盖，Y 区间是 0～50。 - 60～100：A 和 B 都覆盖，Y 区间是 0～50 与 30～80。 - 100～150：只有 B 覆盖，Y 区间是 30～80。 为什么检查“完整覆盖”就够了？因为竖条两端已经来自所有矩形的边界。任意矩形在一条竖条里要么全程存在，要么完全不存在，不会从中间突然开始。 ## 5. 第三步：合并 Y 方向的区间 中间竖条 60～100 同时拿到 0～50 和 30～80。两段在 30～50 重叠，合并后是 0～80，覆盖长度为 80。 ![Y 区间 0～50 与 30～80 合并为 0～80，覆盖长度为 80](https://herblab.online/qwen-imgs/sweep-line-04-y-merge-v1.png) 合并方法很直接： 1. 按区间起点从小到大排序。 2. 记录当前已经覆盖到的最远位置 `spanEnd`。 3. 新区间完全落在 `spanEnd` 左侧时跳过；否则只增加尚未覆盖的那一段。 对区间 `[start, end)`，新增长度可以统一写成： ```text end - max(start, spanEnd) ``` 如果两个区间分开，`spanEnd` 小于 `start`，新增的是完整区间；如果它们重叠，新增的只有右侧露出来的部分。 ## 6. 第四步：累加每条竖条的面积 三条竖条现在都能独立计算： ```text 0～60：宽 60，Y 覆盖 50，面积 60 × 50 = 3000 60～100：宽 40，Y 覆盖 80，面积 40 × 80 = 3200 100～150：宽 50，Y 覆盖 50，面积 50 × 50 = 2500 ``` 最后相加： ```text 3000 + 3200 + 2500 = 8700 ``` 每条竖条在 X 方向互不重叠，Y 方向也已经合并过，因此每一块面积只会进入结果一次。 ## 7. 三种语言的完整实现 ### 7.1 先把四步对上代码 前面的图拆了四步，代码只是把它们连起来。读完整实现前，先认清这几个变量： | 图里的动作 | 代码里看哪里 | 保存的内容 | | --- | --- | --- | | 收集 X 边界 | `xs` | 所有矩形的左、右边界，排序并去重 | | 扫描当前竖条 | `x1`、`x2` | 相邻两个 X 边界 | | 合并 Y 区间 | `spans`、`covered`、`spanEnd` | 当前竖条中的 Y 区间及其并集长度 | | 累加面积 | `area` | 每条竖条的面积之和 | 外层循环每次处理一条竖条，内层循环合并这条竖条里的 Y 区间。抓住这两层，三种语言的结构就是一样的。 ### 7.2 带注释的三种实现 输入是一组矩形，输出是并集面积。注释只标出算法发生变化的位置；语法细节可以直接对照自己常用的语言。 ### TypeScript ```ts type Rect = { left: number; top: number; width: number; height: number; }; function rectUnionArea(rects: Rect[]): number { // 1. 丢掉零宽或零高的矩形，它们不贡献面积。 const validRects = rects.filter( (rect) => rect.width > 0 && rect.height > 0, ); // 2. 收集所有 X 边界，排序去重后得到竖条分界线。 const xs = [ ...new Set( validRects.flatMap((rect) => [rect.left, rect.left + rect.width]), ), ].sort((a, b) => a - b); let area = 0; // 3. 每次处理相邻 X 边界形成的一条竖条。 for (let index = 0; index + 1 < xs.length; index += 1) { const x1 = xs[index]; const x2 = xs[index + 1]; // 找出完整覆盖当前竖条的矩形，并取出它们的 Y 区间。 const spans = validRects .filter( (rect) => rect.left <= x1 && rect.left + rect.width >= x2, ) .map( (rect) => [rect.top, rect.top + rect.height] as [number, number], ) .sort((a, b) => a[0] - b[0]); // 4. 合并 Y 区间，covered 只记录真正覆盖的长度。 let covered = 0; let spanEnd = -Infinity; for (const [start, end] of spans) { if (end <= spanEnd) continue; covered += end - Math.max(start, spanEnd); spanEnd = end; } // 5. 竖条宽度 × Y 覆盖长度，就是这条竖条的面积。 area += (x2 - x1) * covered; } return area; } ``` ### Python ```python from dataclasses import dataclass @dataclass(frozen=True) class Rect: left: float top: float width: float height: float def rectUnionArea(rects: list[Rect]) -> float: # 1. 丢掉零宽或零高的矩形，它们不贡献面积。 valid_rects = [ rect for rect in rects if rect.width > 0 and rect.height > 0 ] # 2. 收集所有 X 边界，排序去重后得到竖条分界线。 xs = sorted({ x for rect in valid_rects for x in (rect.left, rect.left + rect.width) }) area = 0.0 # 3. 每次处理相邻 X 边界形成的一条竖条。 for x1, x2 in zip(xs, xs[1:]): # 找出完整覆盖当前竖条的矩形，并取出它们的 Y 区间。 spans = sorted( (rect.top, rect.top + rect.height) for rect in valid_rects if rect.left <= x1 and rect.left + rect.width >= x2 ) # 4. 合并 Y 区间，covered 只记录真正覆盖的长度。 covered = 0.0 span_end = float("-inf") for start, end in spans: if end <= span_end: continue covered += end - max(start, span_end) span_end = end # 5. 竖条宽度 × Y 覆盖长度，就是这条竖条的面积。 area += (x2 - x1) * covered return area ``` ### C++ ```cpp #include #include #include #include struct Rect { double left; double top; double width; double height; }; double rectUnionArea(const std::vector& rects) { std::vector validRects; std::vector xs; // 1. 丢掉零宽或零高的矩形，它们不贡献面积。 for (const Rect& rect : rects) { if (rect.width <= 0 || rect.height <= 0) { continue; } validRects.push_back(rect); xs.push_back(rect.left); xs.push_back(rect.left + rect.width); } // 2. 收集到的 X 边界排序去重后，就是竖条分界线。 std::sort(xs.begin(), xs.end()); xs.erase(std::unique(xs.begin(), xs.end()), xs.end()); double area = 0.0; // 3. 每次处理相邻 X 边界形成的一条竖条。 for (std::size_t index = 0; index + 1 < xs.size(); ++index) { const double x1 = xs[index]; const double x2 = xs[index + 1]; std::vector> spans; // 找出完整覆盖当前竖条的矩形，并取出它们的 Y 区间。 for (const Rect& rect : validRects) { if (rect.left <= x1 && rect.left + rect.width >= x2) { spans.push_back({rect.top, rect.top + rect.height}); } } std::sort(spans.begin(), spans.end()); // 4. 合并 Y 区间，covered 只记录真正覆盖的长度。 double covered = 0.0; double spanEnd = -std::numeric_limits::infinity(); for (const auto& [start, end] : spans) { if (end <= spanEnd) { continue; } covered += end - std::max(start, spanEnd); spanEnd = end; } // 5. 竖条宽度 × Y 覆盖长度，就是这条竖条的面积。 area += (x2 - x1) * covered; } return area; } ``` ### 7.3 三处最容易写错 #### 第一处：为什么要完整覆盖当前竖条？ ```ts rect.left <= x1 && rect.left + rect.width >= x2 ``` `x1` 和 `x2` 已经是相邻的矩形边界，中间不会再出现另一条左边或右边。因此，一个矩形在这条竖条里只有两种状态：全程存在，或者完全不存在。这里检查的是“完整覆盖当前竖条”，不能改成只看某个端点是否落在矩形内。 #### 第二处：`spanEnd` 怎样去掉重复长度？ ```ts if (end <= spanEnd) continue; covered += end - Math.max(start, spanEnd); spanEnd = end; ``` Y 区间按起点排好序后，新区间可能被完全包含、与前面重叠，或者和前面分开。完全包含时跳过；其余情况从 `start` 和 `spanEnd` 中较大的位置开始增加。这样只会加上尚未覆盖的尾部。 #### 第三处：面积为什么直接相乘？ ```ts area += (x2 - x1) * covered; ``` `x2 - x1` 是竖条宽度，`covered` 是合并后的 Y 覆盖长度。相邻竖条在 X 方向互不重叠，Y 方向也已经去重，所以每一块面积只会进入结果一次。 ## 8. 用五组情况验证代码 不要只测两个部分重叠的矩形。至少把下面五种情况跑一遍： - 空数组：没有矩形，结果是 0。 - 部分重叠：本文示例，结果是 8700。 - 完全包含：小矩形在大矩形内部，只计算外层面积。 - 边界相接：两个矩形只贴边，没有交集面积。 - 零面积矩形：宽或高为 0，不增加结果。 本文的三种实现会使用同一份测试数据运行。五组输入都在三种语言中得到相同结果，才算通过验证。 ## 9. 复杂度与适用范围 设矩形数量为 n。X 边界最多有 2n 个，因此最多扫描 2n - 1 条竖条。每条竖条会检查 n 个矩形，并对最多 n 个 Y 区间排序。 本文实现的时间复杂度是 O(n² log n)，额外空间是 O(n)。它适合中小规模输入，也很适合第一次把扫描线写清楚。 如果矩形达到数万甚至更多，常见做法是把矩形左右边变成事件，扫描到事件时用线段树维护 Y 方向覆盖长度。那一版通常可以做到 O(n log n)，数据结构和边界处理也明显更复杂。本文没有实现线段树版本。 ## 10. 回到开头：怎样计算文字重叠比例？ 现在，`rectUnionArea` 已经能算出一组矩形真正覆盖的面积。把它放回开头的文字重叠问题： 1. 把 A 的墨迹矩形交给 `rectUnionArea`，得到 `areaA`。 2. 把 B 的墨迹矩形交给同一个函数，得到 `areaB`。 3. 两两求 A、B 墨迹矩形的交集，把所有有效交集再次求并集，得到 `intersectionArea`。 4. 按业务需要计算比例，例如 `intersectionArea / min(areaA, areaB)`。 第三步仍要“再次求并集”。同一块重叠墨迹可能由多对矩形产生；如果把所有交集面积直接相加，重复计数会回来。 ## 11. 留一道可以自己完成的练习 给定 n 个轴对齐矩形，请计算它们覆盖的总面积。所有输入都是整数，答案也保证在安全整数范围内。 **输入** 第一行是整数 n，满足 0 ≤ n ≤ 300。接下来 n 行，每行四个整数 `left top width height`。`width` 和 `height` 可能为 0。 **输出** 输出一个整数，表示所有矩形的并集面积。 **示例输入** ```text 2 0 0 100 50 60 30 90 50 ``` **示例输出** ```text 8700 ``` 可以直接复用本文的四步：收集 X 边界，扫描相邻竖条，合并 Y 区间，累加面积。再补上输入解析和结果输出，这道题就完整了。