扫描线算法：计算重叠矩形的并集面积

思考这样一个问题：我们如何判断两个文本框的可见内容到底重叠了多少？

文字渲染以后，可以拆成若干个可见片段。程序用矩形记录每个片段实际占据的位置，这些矩形可以叫作墨迹矩形。

为了算出两个文本框的重叠比例，我们需要先求 A 的墨迹矩形并集、B 的墨迹矩形并集，以及两者交集矩形的并集。三个计算最后都落到同一个问题：

一组矩形可能互相重叠，如何计算它们的并集面积？

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 会出现两次。

并集面积应为：

5000 + 4500 - 800 = 8700

两个矩形时，减掉一次交集就够了。矩形一多，交集之间还可能继续重叠，逐项做容斥很快会失控。

2. 矩形一多，怎么办？

想象一条竖线从平面左边缓慢向右移动。只要它没有越过任何矩形的左边或右边，当前穿过的矩形集合就不会变化。

所以我们不用逐个检查平面上的点，只处理相邻 X 边界之间的竖条。每条竖条内部，问题会从二维面积变成一维长度：Y 轴上到底覆盖了多长？这就是本文使用的扫描线方法。

接下来分四步计算：

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，排序去重后得到：

0、60、100、150

相邻边界切出三条竖条：0～60、60～100、100～150，宽度分别是 60、40、50。

这种只保留关键坐标、再处理相邻区间的做法叫坐标离散化。坐标可以很大，算法真正关心的仍然只有这些边界。

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。

合并方法很直接：

1. 按区间起点从小到大排序。
2. 记录当前已经覆盖到的最远位置 spanEnd。
3. 新区间完全落在 spanEnd 左侧时跳过；否则只增加尚未覆盖的那一段。

对区间 [start, end)，新增长度可以统一写成：

end - max(start, spanEnd)

如果两个区间分开，spanEnd 小于 start，新增的是完整区间；如果它们重叠，新增的只有右侧露出来的部分。

6. 第四步：累加每条竖条的面积

三条竖条现在都能独立计算：

0～60：宽 60，Y 覆盖 50，面积 60 × 50 = 3000
60～100：宽 40，Y 覆盖 80，面积 40 × 80 = 3200
100～150：宽 50，Y 覆盖 50，面积 50 × 50 = 2500

最后相加：

3000 + 3200 + 2500 = 8700

每条竖条在 X 方向互不重叠，Y 方向也已经合并过，因此每一块面积只会进入结果一次。

7. 三种语言的完整实现

7.1 先把四步对上代码

前面的图拆了四步，代码只是把它们连起来。读完整实现前，先认清这几个变量：

| 图里的动作 | 代码里看哪里 | 保存的内容 | | --- | --- | --- | | 收集 X 边界 | xs | 所有矩形的左、右边界，排序并去重 | | 扫描当前竖条 | x1、x2 | 相邻两个 X 边界 | | 合并 Y 区间 | spans、covered、spanEnd | 当前竖条中的 Y 区间及其并集长度 | | 累加面积 | area | 每条竖条的面积之和 |

外层循环每次处理一条竖条，内层循环合并这条竖条里的 Y 区间。抓住这两层，三种语言的结构就是一样的。

7.2 带注释的三种实现

输入是一组矩形，输出是并集面积。注释只标出算法发生变化的位置；语法细节可以直接对照自己常用的语言。

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;
}

7.3 三处最容易写错

第一处：为什么要完整覆盖当前竖条？

rect.left <= x1 && rect.left + rect.width >= x2

x1 和 x2 已经是相邻的矩形边界，中间不会再出现另一条左边或右边。因此，一个矩形在这条竖条里只有两种状态：全程存在，或者完全不存在。这里检查的是“完整覆盖当前竖条”，不能改成只看某个端点是否落在矩形内。

第二处：spanEnd 怎样去掉重复长度？

if (end <= spanEnd) continue;
covered += end - Math.max(start, spanEnd);
spanEnd = end;

Y 区间按起点排好序后，新区间可能被完全包含、与前面重叠，或者和前面分开。完全包含时跳过；其余情况从 start 和 spanEnd 中较大的位置开始增加。这样只会加上尚未覆盖的尾部。

第三处：面积为什么直接相乘？

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。

输出

输出一个整数，表示所有矩形的并集面积。

示例输入

2
0 0 100 50
60 30 90 50

示例输出

8700

可以直接复用本文的四步：收集 X 边界，扫描相邻竖条，合并 Y 区间，累加面积。再补上输入解析和结果输出，这道题就完整了。