求未被其他矩形覆盖的黑色矩形区域面积（C++实现）

问题概述 #

给定一个黑色目标矩形，以及若干覆盖它的矩形，所有矩形以[Top, Left, Bottom, Right]格式表示（坐标系中Top为y轴较大值，Bottom为y轴较小值），需要计算目标矩形内未被其他矩形覆盖的区域面积。

核心思路 #

未覆盖区域面积 = 目标矩形总面积 - 所有覆盖矩形在目标矩形内的并集面积。
多矩形场景的核心难点是高效计算多个矩形的并集面积，这里推荐两种方案：扫描线算法（高效，适用于大量矩形）、矩形切割法（直观，适用于少量矩形）。

C++实现方案 #

1. 基础数据结构定义 #

#include <vector>
#include <algorithm>
#include <iostream>
#include <tuple>
#include <iterator>

using namespace std;

// 矩形结构体，对应[Top, Left, Bottom, Right]
struct Rect {
    int top;
    int left;
    int bottom;
    int right;

    // 计算矩形有效面积（排除无效矩形）
    int area() const {
        if (top >= bottom || left >= right) return 0;
        return (bottom - top) * (right - left);
    }
};

2. 矩形交集计算 #

先判断两个矩形的重叠部分，只保留在目标矩形内的有效覆盖区域：

// 计算两个矩形的交集，无交集则返回无效矩形
Rect getIntersection(const Rect& a, const Rect& b) {
    Rect intersectRect;
    intersectRect.top = max(a.top, b.top);
    intersectRect.left = max(a.left, b.left);
    intersectRect.bottom = min(a.bottom, b.bottom);
    intersectRect.right = min(a.right, b.right);

    // 标记无效交集
    if (intersectRect.top >= intersectRect.bottom || intersectRect.left >= intersectRect.right) {
        return {0, 0, 0, 0};
    }
    return intersectRect;
}

3. 扫描线算法计算矩形并集面积 #

扫描线算法通过遍历矩形的上下边界，维护当前x轴的覆盖区间，高效计算并集面积，时间复杂度O(n log n)：

// 扫描线算法计算多个矩形的并集面积
int calculateUnionArea(const vector<Rect>& rects) {
    if (rects.empty()) return 0;

    // 存储所有边界：(y坐标, 标记(1=左边界/-1=右边界), x坐标)
    vector<tuple<int, int, int>> edges;
    for (const auto& r : rects) {
        edges.emplace_back(r.top, 1, r.left);
        edges.emplace_back(r.top, -1, r.right);
        edges.emplace_back(r.bottom, -1, r.left);
        edges.emplace_back(r.bottom, 1, r.right);
    }

    // 排序规则：按y坐标升序；同y时左边界先处理（避免区间计算错误）
    sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) {
        if (get<0>(a) != get<0>(b)) {
            return get<0>(a) < get<0>(b);
        }
        return get<1>(a) > get<1>(b);
    });

    vector<pair<int, int>> activeXIntervals;
    int prevY = get<0>(edges[0]);
    int unionArea = 0;

    for (const auto& edge : edges) {
        int currY = get<0>(edge);
        int delta = get<1>(edge);
        int x = get<2>(edge);

        // 计算当前y区间的贡献面积
        int height = currY - prevY;
        if (height > 0 && !activeXIntervals.empty()) {
            // 合并并计算当前x轴覆盖总长度
            sort(activeXIntervals.begin(), activeXIntervals.end());
            int coveredLength = 0;
            int currStart = activeXIntervals[0].first;
            int currEnd = activeXIntervals[0].second;

            for (size_t i = 1; i < activeXIntervals.size(); ++i) {
                if (activeXIntervals[i].first <= currEnd) {
                    currEnd = max(currEnd, activeXIntervals[i].second);
                } else {
                    coveredLength += currEnd - currStart;
                    currStart = activeXIntervals[i].first;
                    currEnd = activeXIntervals[i].second;
                }
            }
            coveredLength += currEnd - currStart;
            unionArea += coveredLength * height;
        }

        // 更新活跃x区间
        if (delta == 1) {
            activeXIntervals.emplace_back(x, 0); // 临时占位，后续合并
        } else {
            // 移除对应的左边界
            auto it = find_if(activeXIntervals.begin(), activeXIntervals.end(),
                [x](const auto& p) { return p.first == x; });
            if (it != activeXIntervals.end()) {
                activeXIntervals.erase(it);
            }
        }

        // 合并重叠的x区间
        if (!activeXIntervals.empty()) {
            sort(activeXIntervals.begin(), activeXIntervals.end());
            vector<pair<int, int>> merged;
            merged.push_back(activeXIntervals[0]);
            for (size_t i = 1; i < activeXIntervals.size(); ++i) {
                auto& last = merged.back();
                if (activeXIntervals[i].first <= last.second) {
                    last.second = max(last.second, activeXIntervals[i].second);
                } else {
                    merged.push_back(activeXIntervals[i]);
                }
            }
            activeXIntervals.swap(merged);
        }

        prevY = currY;
    }

    return unionArea;
}

4. 计算未覆盖区域面积 #

先过滤掉覆盖矩形中超出目标矩形的部分，再计算并集面积，最后用目标面积减去并集面积：

// 计算目标矩形内未被覆盖的面积
int getUncoveredArea(const Rect& target, const vector<Rect>& covers) {
    int targetArea = target.area();
    if (targetArea == 0) return 0;

    // 保留覆盖矩形与目标矩形的有效交集
    vector<Rect> validCovers;
    for (const auto& r : covers) {
        Rect inter = getIntersection(target, r);
        if (inter.area() > 0) {
            validCovers.push_back(inter);
        }
    }

    int unionArea = calculateUnionArea(validCovers);
    return targetArea - unionArea;
}

5. 测试示例 #

int main() {
    // 示例：目标矩形[10,10,50,50]，6个覆盖矩形
    Rect target = {10, 10, 50, 50};
    vector<Rect> covers = {
        {15, 15, 25, 25},
        {20, 30, 35, 45},
        {30, 15, 45, 25},
        {15, 35, 25, 45},
        {35, 35, 45, 45},
        {35, 10, 45, 20}
    };

    int uncoveredArea = getUncoveredArea(target, covers);
    cout << "未被覆盖的黄色区域面积：" << uncoveredArea << endl;

    return 0;
}

多矩形场景通用解法说明 #

1. 扫描线算法（推荐） #

• 适用场景：覆盖矩形数量较多（n>100），追求高效计算。
• 优势：时间复杂度O(n log n)，性能稳定，适合大规模数据。
• 核心逻辑：将矩形的上下边界作为扫描线触发点，通过维护x轴的覆盖区间，逐段计算并集面积。

2. 矩形切割法（暴力直观） #

• 适用场景：覆盖矩形数量较少（n<20），实现简单。
• 优势：逻辑直观，无需复杂的数据结构。
• 核心逻辑：从目标矩形开始，用每个覆盖矩形切割当前的未覆盖区域，将未被覆盖的部分拆分为更小的矩形，最终累加所有剩余矩形的面积。

内容的提问来源于stack exchange，提问作者John Pekl