Intersection area of all n rectangles

Question

I have no idea how to begin this, preferably providing me with an algorithm to help. The question goes as follows, for n rectangles, an input is called to define each rectangle. Limits of n is 1000, while limits of the coordinates are 10000.

4 numbers are given,

x1, x2, y1, y2

such that the rectangle is bounded by

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

The problem arises when I am required to find the intersecting area between all these rectangles. Any idea how the algorithm should work?

My idea: I implement a loop that creates the coordinates bounding the intersected square the first time. Then for each new loop, I check if the next inputted coordinates intersect.

Answer 1

You only need to find 4 items: the maximum value of the left position and the top position, and the minimum value of the right position and the bottom position. (Assuming the positive axis of X and Y point to right and down, as is often the case in CS)

So the minimal code could be:

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);
}

Then you know if lv <= rv && tv <= bv, there's an intersection specified by those 4 values. If lv > rv || tv > bv, there's no common intersection.