所有n个矩形的交集面积

Question

我不知道如何开始，最好能提供一个算法来帮助我。问题如下，对于 n 个矩形，调用一个输入来定义每个矩形。 n的极限是1000，而坐标的极限是10000.

给出了4个数字，

x1, x2, y1, y2

这样矩形的边界是

x=x1, x=x2, y=y1, y=y2

当我需要找到所有这些矩形之间的相交区域时，问题就出现了。知道算法应该如何工作吗？

我的想法：我实现了一个循环，它第一次创建包围相交正方形的坐标。然后对于每个新循环，我检查下一个输入的坐标是否相交。

Answer 1

将交集矩形设置为第一个矩形，然后找到与第二个矩形的交集并更新交集，然后对剩下的所有矩形重复。

在伪代码中：

std::vector<Rect> rects;
Rect intersection = rects[0];
for( int i = 1; i < rects.size(); ++i)
{
    intersection = getIntersection( intersection, rect[i] );
}

Answer 2

你只需要找到4项：左边位置和顶部位置的最大值，右边位置和底部位置的最小值。（假设 X 和 Y 的正轴指向右下方，就像在 CS 中经常出现的情况一样）

所以最小代码可以是：

int lv = -1, tv = -1, rv = 10001, bv = 10001;
int l, t, r, b;
for (int i = 0; i < N; i++) {
    // cin >> l >> t >> r >> b; Input
    lv = max(lv, l);
    tv = max(tv, t);
    rv = min(rv, r);
    bv = min(bv, b);
}

然后你知道如果 lv <= rv && tv <= bv，这 4 个值指定了一个交集。如果lv > rv || tv > bv，没有公共交集。

所有n个矩形的交集面积

Intersection area of all n rectangles

c++

algorithm

area

c++11