What is an Efficient algorithm to find Area of Overlapping Rectangles

This is some quick and dirty code that I used in the TopCoder SRM 160 Div 2.

t = top
b = botttom
l = left
r = right

public class Rect
{
    public int t, b, l, r;

    public Rect(int _l, int _b, int _r, int _t)
    {
        t = _t;
        b = _b;
        l = _l;
        r = _r;
    }   

    public bool Intersects(Rect R)
    {
        return !(l > R.r || R.l > r || R.b > t || b > R.t);
    }

    public Rect Intersection(Rect R)
    {
        if(!this.Intersects(R))
            return new Rect(0,0,0,0);
        int [] horiz = {l, r, R.l, R.r};
        Array.Sort(horiz);
        int [] vert = {b, t, R.b, R.t};
        Array.Sort(vert);

        return new Rect(horiz[1], vert[1], horiz[2], vert[2]);
    } 

    public int Area()
    {
        return (t - b)*(r-l);
    }

    public override string ToString()
    {
        return l + " " + b + " " + r + " " + t;
    }
}

An efficient way of computing this area is to use a sweep algorithm. Let us assume that we sweep a vertical line L(x) through the union of rectangles U:

• first of all, you need to build an event queue Q, which is, in this case, the ordered list of all x-coordinates (left and right) of the rectangles.
• during the sweep, you should maintain a 1D datastructure, which should give you the total length of the intersection of L(x) and U. The important thing is that this length is constant between two consecutive events q and q' of Q. So, if l(q) denotes the total length of L(q+) (i.e. L just on the rightside of q) intersected with U, the area swept by L between events q and q' is exactly l(q)*(q' - q).
• you just have to sum up all these swept areas to get the total one.

We still have to solve the 1D problem. You want a 1D structure, which computes dynamically a union of (vertical) segments. By dynamically, I mean that you sometimes add a new segment, and sometimes remove one.

I already detailed in my answer to this collapsing ranges question how to do it in a static way (which is in fact a 1D sweep). So if you want something simple, you can directly apply that (by recomputing the union for each event). If you want something more efficient, you just need to adapt it a bit:

• assuming that you know the union of segments S₁...S_n consists of disjoints segments D₁...D_k. Adding S_n+1 is very easy, you just have to locate both ends of S_n+1 amongs the ends of D₁...D_k.
• assuming that you know the union of segments S₁...S_n consists of disjoints segments D₁...D_k, removing segment S_i (assuming that S_i was included in D_j) means recomputing the union of segments that D_j consisted of, except S_i (using the static algorithm).

This is your dynamic algorithm. Assuming that you will use sorted sets with log-time location queries to represent D₁...D_k, this is probably the most efficient non-specialized method you can get.

The simplest solution

import numpy as np

A = np.zeros((100, 100))
B = np.zeros((100, 100))

A[rect1.top : rect1.bottom,  rect1.left : rect1.right] = 1
B[rect2.top : rect2.bottom,  rect2.left : rect2.right] = 1

area_of_union     = np.sum((A + B) > 0)
area_of_intersect = np.sum((A + B) > 1)

In this example, we create two zero-matrices that are the size of the canvas. For each rectangle, fill one of these matrices with ones where the rectangle takes up space. Then sum the matrices. Now sum(A+B > 0) is the area of the union, and sum(A+B > 1) is the area of the overlap. This example can easily generalize to multiple rectangles.

One way-out approach is to plot it to a canvas! Draw each rectangle using a semi-transparent colour. The .NET runtime will be doing the drawing in optimised, native code - or even using a hardware accelerator.

Then, you have to read-back the pixels. Is each pixel the background colour, the rectangle colour, or another colour? The only way it can be another colour is if two or more rectangles overlapped...

If this is too much of a cheat, I'd recommend the quad-tree as another answerer did, or the r-tree.