2025-09-18 20:58:55

如何计算多个矩形的重叠区域

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)，适合大规模数据场景。

💡 踩坑提醒：在实际项目中，如果矩形数量较大（如上万），一定要避免使用暴力解法，否则很容易导致性能瓶颈。

✅ 推荐优先使用扫描线 + 区间树的方式，兼顾性能与实现难度。