1. 简介
在本文中，我们将探讨如何计算多个矩形之间的重叠面积。这种问题在多个领域都有实际应用，例如在芯片设计中，某些区域或线路不允许完全重叠，或只能在特定范围内重叠。我们的目标是给定一组矩形，计算它们之间所有重叠部分的总面积。
2. 问题描述
问题看似简单：我们有一组矩形，它们的边都与坐标轴平行（即轴对齐矩形），目标是找出它们之间的重叠区域。注意，我们只关心重叠面积的大小，而不关心重叠区域的具体几何形状。
如下图所示，我们有三个矩形。其中红色和蓝色矩形有重叠区域，面积为 1。
3. 简单解法
最直观的方法是两两比较矩形，计算每对之间的重叠面积，然后累加。
3.1 理论思路
每个矩形由两个点定义：左下角和右上角。我们可以将矩形在 x 和 y 轴上的投影看作两个区间。要判断两个矩形是否重叠，只需判断它们在 x 和 y 轴上的投影是否都存在交集。
3.2 实现代码
algorithm CalculateOverlap(l):
// INPUT
// l = a list of rectangles
// OUTPUT
// a = the area of overlap
n <- the length of l
a <- 0
for i <- 0 to n:
for j <- 0 to n:
if i != j:
a <- a + Compare(l[i], l[j])
return a
algorithm Compare(R1, R2):
// INPUT
// R1, R2 = two rectangles defined by two points A and B
// OUTPUT
// a = the area of Overlap
X <- 0
Y <- 0
if R2.A.x > R1.B.x or R2.B.x < R1.A.x:
return 0
else:
X <- min(R1.B.x, R2.B.x) - max(R1.A.x, R2.A.x)
if R2.A.y > R1.B.y or R2.B.y < R1.A.y:
return 0
else:
Y <- min(R1.B.y, R2.B.y) - max(R1.A.y, R2.A.y)
return X * Y
✅ 优点：逻辑清晰，实现简单
❌ 缺点：时间复杂度为 O(n²)，效率低，不适合大规模数据
4. 扫描线法（Sweep Line Algorithm）
为了优化性能，我们可以使用扫描线算法来减少比较次数。该算法通过一条虚拟的垂直线从左向右“扫过”所有矩形的 x 坐标，动态维护当前与扫描线相交的矩形集合。
4.1 算法原理
- 扫描线从左向右移动，遇到矩形的左边界时将其加入数据结构中。
- 遇到右边界时将其从数据结构中移除。
- 每次加入一个矩形时，与当前数据结构中的所有矩形比较，计算重叠面积。
这样我们把二维问题简化为一维问题，减少了不必要的比较。
4.2 示例：添加矩形
如下图所示，我们有四个关键点（事件）：分别是两个矩形的左边界和右边界。
- 步骤 A：加入蓝色矩形的左边界 [1,4]，记录矩形信息。
- 步骤 B：加入红色矩形的左边界 [3,7]，此时与蓝色矩形进行比较。
4.3 示例：移除矩形
- 步骤 C：遇到蓝色矩形的右边界，将其从数据结构中移除。
- 步骤 D：遇到红色矩形的右边界，也移除。
4.4 实现代码
algorithm LineSweep(l):
// INPUT
// l = a list of rectangles
// OUTPUT
// a = the area of their overlap
a <- 0
cList <- all x-coordinates from the rectangles
//each x-coordinate has a reference to its rectangle
n <- the length of cList
for i <- 0 to n:
if cList[i] = cList[i].Rectangle.left:
m <- the length of cList
for j <- 0 to m:
a <- a + Compare(l[i], cList[j])
cList.Add(l[i])
else:
cList.Remove(l[i].Rectangle)
return a
⚠️ 注意：这里我们仍然使用了
Compare()方法，但通过减少比较次数提升了效率。
5. 优化与复杂度分析
5.1 时间复杂度对比
- 暴力法：O(n²)，因为每对矩形都要比较一次。
- 扫描线法：仍为 O(n²)，因为每加入一个矩形时都要和当前所有矩形比较。
5.2 进一步优化
要真正降低时间复杂度，我们需要优化用于存储和查询矩形的数据结构。可以使用 区间树（Interval Tree） 或 平衡二叉搜索树（BST），这样插入、删除和查找操作的时间复杂度均可降至 O(log n)。
修改扫描线算法中的 cList 为区间树后，整体时间复杂度可优化为 **O(n log n)**。
✅ 优化后复杂度：O(n log n)
✅ 适用场景：大规模矩形数据集
6. 总结
本文介绍了两种计算矩形重叠面积的方法：
- 暴力法：简单直接但效率低下，适合小规模数据。
- 扫描线法：将问题降维，通过动态维护活动矩形集合减少比较次数。
- 进一步优化：使用区间树将复杂度降至 O(n log n)，适合大规模数据场景。
💡 踩坑提醒：在实际项目中，如果矩形数量较大（如上万），一定要避免使用暴力解法，否则很容易导致性能瓶颈。
✅ 推荐优先使用扫描线 + 区间树的方式，兼顾性能与实现难度。