计算几何实战 —— 扫描线算法在矩形面积并问题中的应用

1. 从生活场景到算法思想：扫描线到底是什么？

想象一下，你正在用手机扫描一份纸质文件，把它变成电子版。你的手机摄像头就像一条“扫描线”，从上到下缓缓移动，每移动一点，就“看到”并记录下当前这一横条的内容。最后，把所有横条的内容拼接起来，就得到了完整的文档图像。

扫描线算法的核心思想和这个生活场景一模一样。在计算几何中，当我们面对一堆重叠的矩形，想要求出它们覆盖的总面积（即矩形面积并）时，直接计算这些奇形怪状的重叠区域会非常头疼。扫描线算法提供了一种“降维打击”的思路：我们不再盯着复杂的二维图形看，而是假想有一条线（通常是水平线），从下往上匀速扫描整个平面。

这条线在移动过程中，会被下方的矩形“切割”成一段一段的。关键来了：在任何一个时刻，扫描线被矩形覆盖的部分，其长度是很容易计算的。那么，从底部扫描到顶部的整个过程中，扫描线被覆盖的“总长度”随着高度“累积”起来的面积，不就是所有矩形的总面积吗？这其实就是积分思想的离散化模拟——把整个不规则图形，切成无数个细长的“小矩形条”，分别求面积再累加。

我第一次理解这个比喻时，感觉豁然开朗。原来那些ACM竞赛里看似高深莫测的算法，其内核往往就是这么直观。我们程序员要做的，就是设计好数据结构，让计算机能高效地模拟这条“扫描线”的移动，并实时回答：“嘿，当前这条线被矩形截了多长？”

2. 核心挑战与破局思路：如何动态维护“被截长度”？

思路听起来很美，但实现起来第一个拦路虎就是：扫描线在不停移动，矩形进进出出，我怎么才能快速知道，在当前这个高度，到底有哪些X坐标的区间是被覆盖的呢？

这就是整个算法的灵魂所在。我们得把二维的矩形，拆解成一维的“事件”。具体来说，每个矩形贡献两条水平的边：一条下边（当扫描线碰到它时，开始覆盖这个矩形），一条上边（当扫描线离开它时，结束覆盖）。我们给下边一个标记为+1（表示“进入”），给上边标记为-1（表示“离开”）。

把所有矩形的这些边，按照它们所在的Y坐标（高度）从小到大排序。这样，扫描线从低到高移动时，处理这些边的顺序就是自然的。现在，问题转化成了：有一系列在X轴上的区间[x1, x2]，每个区间带着一个+1或-1的权重。随着我们处理不同高度的事件，这些区间会被加入或移除。我们需要随时能查询：在当前所有活跃区间（权重叠加后>0）的作用下，X轴上被覆盖的总长度是多少？

这不就是一个区间加减、区间查询的问题吗？而且我们只关心整个X轴范围的总覆盖长度。最适合解决这个问题的数据结构之一，就是线段树。线段树可以在对数时间内完成对一个区间的“进入”（+1）或“离开”（-1）操作，并且能快速返回整个区间被覆盖的有效长度。

我最初自己尝试实现时，曾想偷懒用数组暴力维护，结果当矩形数量上去后，效率惨不忍睹。深刻体会到，好的算法必须搭配正确的数据结构，才能发挥威力。

2.1 离散化：应对坐标值过大或非整数

在实际问题中，矩形的坐标值可能很大（比如1e9），也可能不是整数。我们不可能真的去创建一个覆盖巨大范围的线段树。这时候就需要离散化登场。

离散化的本质是“只关心相对大小，不关心具体数值”。我们把所有矩形左右边界的X坐标收集起来，去重、排序。这样，每个实际的X坐标都映射到了这个有序列表中的一个索引（下标）上。线段树建立在这些索引区间上，而不是原始的巨大坐标上。查询和更新时，我们操作的是索引区间，但计算长度时，再用索引对应的真实坐标值进行换算。

举个例子，假设X坐标有[10, 20, 30, 40]，离散化后映射为下标0, 1, 2, 3。线段树节点维护区间[1, 2]，它代表的真实X轴区间是[X[1], X[2+1]] = [20, 40]。这里有个细节：线段树的叶子节点不再代表一个点，而是代表一个最小单位区间[X[i], X[i+1]]。这样处理能优雅地避免边界重合带来的麻烦。

3. 算法实现三部曲：拆边、排序、扫描

理论铺垫够了，我们来看看具体怎么用代码实现。整个过程可以清晰地分为三步，我会用通俗的语言和例子带你走一遍。

第一步：拆边与准备对于每个矩形(x1, y1, x2, y2)，我们生成两条边：

• 下边：(x1, x2, y1, +1)， 表示从y1高度开始，在x1到x2的范围内增加一层覆盖。
• 上边：(x1, x2, y2, -1)， 表示到y2高度为止，在x1到x2的范围内减少一层覆盖。 同时，把所有的x1, x2坐标收集起来，准备离散化。

第二步：离散化与排序

1. 将所有X坐标排序、去重，得到离散化后的数组X[]。
2. 将所有边（包括上下边）按照它们的Y坐标从小到大排序。如果Y坐标相同，为了处理边界情况，通常让“入边”（+1）排在“出边”（-1）前面，确保同一高度先加后减，避免面积计算误差。

第三步：扫描与计算

1. 建立线段树，覆盖的区间是[0, 离散化后X的数量-2]。因为N个点构成N-1个区间段。
2. 按顺序遍历排序后的边。对于当前边i：
   • 根据其x1, x2值，在离散化数组中找到对应的索引区间[L, R)。
   • 在线段树中，对这个索引区间执行“区间加法”，加上的值就是这条边的权重（+1或-1）。
   • 此时，线段树根节点维护的len，就是当前扫描线高度下，被矩形覆盖的X轴总长度。
   • 这条边处理完后，扫描线将移动到下一条边的高度line[i+1].h。那么，在[当前高度, 下一条边高度)这个小区间内，覆盖的形状可以近似看作一个“细长矩形”。其面积就是当前覆盖总长度 * 高度差。
   • 将这个“细长矩形”的面积累加到答案中。
3. 遍历完所有边，累加的面积总和就是所有矩形的总面积并。

下面是一个最核心的扫描循环代码示例（C++风格）：

long long ans = 0; for (int i = 1; i <= cnt; i++) { // cnt是边的总数 // 1. 更新线段树：将当前边的影响加入 int L = lower_bound(X.begin(), X.end(), line[i].l) - X.begin(); int R = lower_bound(X.begin(), X.end(), line[i].r) - X.begin(); update(1, L, R-1, line[i].mark); // mark是+1或-1 // 2. 计算当前边到下一条边之间的面积贡献 if (i < cnt) { ans += tree[1].len * (line[i+1].h - line[i].h); } }

4. 线段树节点的特殊设计：维护什么？

在标准的线段树模板中，我们通常维护区间和。但在这里，我们需要维护的是“被覆盖的长度”。这需要我们对线段树节点存储的信息进行定制。

一个节点需要存储：

1. l, r: 节点管理的离散化X索引区间。
2. cnt: 这个节点对应的整个区间被“完全覆盖”的次数（即区间加法懒标记的叠加）。
3. len: 这个节点管理的区间中，实际被覆盖的长度（根据真实坐标计算）。

最关键的是push_up函数的设计：

• 如果cnt > 0，意味着这个区间整个被至少一个矩形覆盖了，那么它的被覆盖长度len就是整个区间对应的真实长度X[r+1] - X[l]。
• 如果cnt == 0，意味着这个区间没有被整体覆盖，那么它的被覆盖长度就由它的两个子区间的len加起来得到。如果它是叶子节点，则长度为0。

void push_up(int u) { if (tree[u].cnt > 0) { // 被整体覆盖，长度为区间实际长度 tree[u].len = X[tree[u].r + 1] - X[tree[u].l]; } else { // 未被整体覆盖，长度由孩子决定 if (tree[u].l == tree[u].r) { tree[u].len = 0; // 叶子节点 } else { tree[u].len = tree[u<<1].len + tree[u<<1|1].len; } } }

这种设计巧妙地避免了传统懒标记需要下传的麻烦。因为cnt记录了覆盖次数，我们只需要在update函数中修改cnt，然后调用push_up更新len即可。len的含义是“不考虑祖先节点的覆盖，仅看当前节点自身被覆盖的次数所计算出的长度”。当cnt>0时，子节点具体如何被覆盖的细节就不重要了，因为父节点已经“一票否决”，被完全覆盖了。

5. 从面积到周长：扫描线的进阶应用

解决了面积问题，我们很自然地会想：那这些矩形合并后的图形，总周长怎么求呢？其实思路一脉相承，但需要更细致地观察。

矩形的周长由水平边和垂直边组成。扫描线从下往上扫，可以很方便地处理水平边：每次扫描线移动一个高度，被覆盖的X区间长度可能发生变化，这个变化量的绝对值，就是新增或消失的水平边长度。

那垂直边呢？垂直边出现在矩形的左右两侧。我们可以发现，在扫描线被覆盖的X区间上，每一条独立的、连续的覆盖段，其左右两端都对应着一条垂直边。连续段的条数乘以2（左右各一），再乘以扫描线移动的高度，就是这段高度内，垂直边贡献的长度。

因此，我们需要在线段树节点里额外维护两个信息：

1. num: 当前区间内，互不相交的连续覆盖段有多少段。
2. lcover, rcover: 当前区间的左端点/右端点是否被覆盖。这个信息是为了合并左右儿子区间时，判断连续段是否会连接起来。

合并左右孩子时：

• 如果左孩子的右端被覆盖，且右孩子的左端被覆盖，那么它们会连接成一段，总段数需要减一。
• 父区间的左右端点覆盖状态继承自左孩子的左端和右孩子的右端。

这样，在一次扫描过程中，我们可以同时累加水平边和垂直边的贡献。水平边贡献 =abs(上次总覆盖长度 - 本次总覆盖长度)。垂直边贡献 =2 * 当前连续段数量 * 扫描高度差。

我曾在项目中需要计算一组不规则图形的外轮廓长度，就是借鉴了这个思路。虽然原始图形不是矩形，但将其栅格化（像素化）后，近似成了无数小矩形，再用扫描线求周长并，效果非常好。

6. 实战优化与边界处理：那些容易踩的坑

纸上谈兵终觉浅，自己实现时总会遇到各种妖魔鬼怪。这里分享几个我踩过的坑和对应的解决方案。

坑1：浮点数精度问题如果坐标是浮点数，离散化时比较是否相等不能直接用==，要设定一个误差范围eps（如1e-9）。排序和去重时也要用自定义的比较函数。计算面积时，使用double类型，并注意输出格式。

坑2：区间开闭问题这是扫描线最细腻的地方。我们离散化后，线段树节点管理的是区间段[X[i], X[i+1]]。因此，当我们用原始坐标[x1, x2]去更新线段树时，找到的索引pos1, pos2，对应的更新区间应该是[pos1, pos2-1]。因为x2对应的是索引pos2，而区间段是到pos2-1为止。如果弄错，会导致覆盖范围偏差，计算结果少一条“线”的面积。

坑3：边排序的稳定性当两条边高度相同时，谁先谁后？一个稳妥的策略是：让“入边”（+1）排在“出边”（-1）前面。这样可以保证，在同一高度，先加上新矩形的覆盖，再移除旧矩形的覆盖，使得扫描线上的覆盖次数不会出现负数，也符合物理直觉。在周长问题中，这个顺序更为关键，否则可能导致同一高度水平边的重复计算或漏算。

坑4：线段树空间大小由于每个矩形产生两条边，每条边对应两个X坐标，所以离散化后的X坐标最多有2N个，线段树需要开8N（通常开4倍于叶子节点数，叶子节点是2N-1个区间段，所以4 * 2N = 8N）的空间才比较安全。我习惯直接开N<<3的数组。

7. 代码模板与使用指南

为了方便大家理解和上手，我整理了一个相对清晰、注释完整的矩形面积并的代码模板。这个模板去掉了竞赛中常见的快读等优化，专注于算法逻辑本身。

#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; const int MAXN = 100005; // 扫描线结构体 struct ScanLine { ll l, r, h; // l,r是x坐标，h是y坐标（高度） int mark; // +1 表示下边，-1表示上边 bool operator < (const ScanLine &b) const { // 按高度排序，高度相同则入边在前 if (h == b.h) return mark > b.mark; return h < b.h; } } line[MAXN << 1]; // 每个矩形两条边 // 离散化用的X坐标数组 ll X[MAXN << 1]; // 线段树节点 struct SegNode { int l, r; // 管理的离散化索引区间 [l, r] int cnt; // 区间被整体覆盖的次数 ll len; // 区间内被覆盖的实际长度 } tree[MAXN << 3]; // 8倍空间 // 根据子节点更新当前节点信息 void push_up(int u) { // 如果被整体覆盖，长度就是区间真实长度 if (tree[u].cnt > 0) { tree[u].len = X[tree[u].r + 1] - X[tree[u].l]; } else { // 否则，长度由两个孩子提供 if (tree[u].l == tree[u].r) { tree[u].len = 0; // 叶子节点 } else { tree[u].len = tree[u<<1].len + tree[u<<1|1].len; } } } // 建树 void build(int u, int l, int r) { tree[u] = {l, r, 0, 0}; if (l == r) return; int mid = (l + r) >> 1; build(u<<1, l, mid); build(u<<1|1, mid+1, r); // 这里不需要push_up，因为初始len都是0 } // 区间更新 [L, R] 区间加上c void update(int u, int L, int R, int c) { // 当前节点区间完全不在查询区间内 if (X[tree[u].r + 1] <= L || X[tree[u].l] >= R) return; // 当前节点区间完全被查询区间包含 if (L <= X[tree[u].l] && X[tree[u].r + 1] <= R) { tree[u].cnt += c; push_up(u); return; } // 部分重叠，递归更新孩子 update(u<<1, L, R, c); update(u<<1|1, L, R, c); push_up(u); } int main() { int n; cin >> n; int cnt = 0; for (int i = 1; i <= n; i++) { ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; // 记录边 line[++cnt] = {x1, x2, y1, 1}; // 下边 line[++cnt] = {x1, x2, y2, -1}; // 上边 // 记录X坐标用于离散化 X[i*2-1] = x1; X[i*2] = x2; } // 1. 对边按高度排序 sort(line + 1, line + cnt + 1); // 2. 对X坐标离散化 sort(X + 1, X + cnt + 1); int tot = unique(X + 1, X + cnt + 1) - X - 1; // 去重后数量 // 3. 建树，管理 [1, tot-1] 的区间段 build(1, 1, tot - 1); // 4. 扫描计算 ll ans = 0; for (int i = 1; i < cnt; i++) { // 最后一条边只更新，不计算面积 int L = lower_bound(X + 1, X + tot + 1, line[i].l) - X; int R = lower_bound(X + 1, X + tot + 1, line[i].r) - X; // 更新区间 [L, R-1] update(1, line[i].l, line[i].r, line[i].mark); // 累加当前边到下一条边之间的面积 ans += tree[1].len * (line[i+1].h - line[i].h); } cout << ans << endl; return 0; }

你可以把这段代码保存下来，用洛谷P5490（【模板】扫描线）这样的题目去测试。理解每一行代码的作用，比死记硬背更重要。

8. 举一反三：扫描线还能做什么？

掌握了矩形面积并这个经典模型，你会发现扫描线的思想能应用到很多其他计算几何乃至非几何的问题上。它的本质是按某一维有序扫描，在另一维上用数据结构维护状态。

1. 二维数点问题给定平面上一堆点，多次查询一个矩形区域内有多少个点。我们可以将点和查询都看作事件，按x坐标扫描，用树状数组维护y坐标上的点数。遇到点就插入，遇到查询矩形的左右边界就查询y轴区间内的点数，通过差分得到答案。

2. 天际线问题这是LeetCode上的一道经典题。给定建筑物的位置和高度，求城市的天际线轮廓。我们可以将每个建筑物看作两个事件：左边缘的“上升”和右边缘的“下降”。按x坐标扫描，用最大堆维护当前x位置所有建筑物的高度。每当最大高度发生变化时，就产生一个天际线关键点。

3. 圆的面积并虽然圆不是矩形，但我们可以用垂直扫描线，将圆与扫描线的交点转化为一段段弦。通过计算这些弦的并集长度，结合微积分思想（如辛普森积分），也能求出圆的面积并。这比矩形复杂，但核心的“扫描-维护-查询”模式是相通的。

4. 判断线段相交扫描线算法最早的应用之一就是判断平面上一组线段是否有交点。将线段的端点以及可能的交点作为事件，用有序数据结构（如平衡树）维护当前与扫描线相交的线段顺序。当线段顺序发生交换时，就可能产生了交点。

学习算法，我最深的体会是：不要孤立地记忆模板。像扫描线这样，理解了其“降维”和“事件驱动”的核心思想，你就能在遇到新问题时，自己构思出解决方案的骨架。剩下的，就是根据具体问题，选择合适的工具（数据结构）去填充这个骨架。这种能力的培养，远比AC十道题更有价值。