What is an Efficient algorithm to find Area of Overlapping Rectangles

Question

My situation

• Input: a set of rectangles
• each rect is comprised of 4 doubles like this: (x0,y0,x1,y1)
• they are not "rotated" at any angle, all they are "normal" rectangles that go "up/down" and "left/right" with respect to the screen
• they are randomly placed - they may be touching at the edges, overlapping , or not have any contact
• I will have several hundred rectangles
• this is implemented in C#

I need to find

• The area that is formed by their overlap - all the area in the canvas that more than one rectangle "covers" (for example with two rectangles, it would be the intersection)
• I don't need the geometry of the overlap - just the area (example: 4 sq inches)
• Overlaps shouldn't be counted multiple times - so for example imagine 3 rects that have the same size and position - they are right on top of each other - this area should be counted once (not three times)

Example

• The image below contains thre rectangles: A,B,C
• A and B overlap (as indicated by dashes)
• B and C overlap (as indicated by dashes)
• What I am looking for is the area where the dashes are shown

-

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
AAAAAAAAAAAAAAAA--------------BBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBBBBBBBBBBBBB
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                BBBBBB-----------CCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC
                      CCCCCCCCCCCCCCCCCCC

Answer 1

You can find the overlap on the x and on the y axis and multiply those.

int LineOverlap(int line1a, line1b, line2a, line2b) 
{
  // assume line1a <= line1b and line2a <= line2b
  if (line1a < line2a) 
  {
    if (line1b > line2b)
      return line2b-line2a;
    else if (line1b > line2a)
      return line1b-line2a;
    else 
      return 0;
  }
  else if (line2a < line1b)
    return line2b-line1a;
  else 
    return 0;
}


int RectangleOverlap(Rect rectA, rectB) 
{
  return LineOverlap(rectA.x1, rectA.x2, rectB.x1, rectB.x2) *
    LineOverlap(rectA.y1, rectA.y2, rectB.y1, rectB.y2);
}

Answer 2

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.

Answer 3

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

Answer 4

If your rectangles are going to be sparse (mostly not intersecting) then it might be worth a look at recursive dimensional clustering. Otherwise a quad-tree seems to be the way to go (as has been mentioned by other posters.

This is a common problem in collision detection in computer games, so there is no shortage of resources suggesting ways to solve it.

Here is a nice blog post summarizing RCD.

Here is a Dr.Dobbs article summarizing various collision detection algorithms, which would be suitable.

Answer 5

This type of collision detection is often called AABB (Axis Aligned Bounding Boxes), that's a good starting point for a google search.

Answer 6

Here's something that off the top of my head sounds like it might work:

1. Create a dictionary with a double key, and a list of rectangle+boolean values, like this:

   Dictionary< Double, List< KeyValuePair< Rectangle, Boolean>>> rectangles;

2. For each rectangle in your set, find the corresponding list for the x0 and the x1 values, and add the rectangle to that list, with a boolean value of true for x0, and false for x1. This way you now have a complete list of all the x-coordinates that each rectangle either enters (true) or leaves (false) the x-direction

3. Grab all the keys from that dictionary (all the distinct x-coordinates), sort them, and loop through them in order, make sure you can get at both the current x-value, and the next one as well (you need them both). This gives you individual strips of rectangles

4. Maintain a set of rectangles you're currently looking at, which starts out empty. For each x-value you iterate over in point 3, if the rectangle is registered with a true value, add it to the set, otherwise remove it.
5. For a strip, sort the rectangles by their y-coordinate
6. Loop through the rectangles in the strip, counting overlapping distances (unclear to me as of yet how to do this efficiently)
7. Calculate width of strip times height of overlapping distances to get areas

Example, 5 rectangles, draw on top of each other, from a to e:

aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaaaaaaaaaa          bbbbbbbbbbbbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
aaaaaaaadddddddddddddddddddddddddddddbbbbbb
        ddddddddddddddddddddddddddddd
        ddddddddddddddddddddddddddddd
        ddddddddddddddeeeeeeeeeeeeeeeeee
        ddddddddddddddeeeeeeeeeeeeeeeeee
        ddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
ccccccccddddddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc

Here's the list of x-coordinates:

v       v  v   v      v   v         v  v  v   
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaa|aa|aaaa      |   bbbbbbbbbb|bb|bbb
|aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb
|aaaaaaaddd|dddddddddd|ddddddddddddddbb|bbb
|       ddd|dddddddddd|dddddddddddddd  |
|       ddd|dddddddddd|dddddddddddddd  |
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
|       ddd|ddddddddddeeeeeeeeeeeeeeeeee
ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee
ccccccccddd|ddddddddddeeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc          eeeeeeeeeeeeeeeeee
cccccccccccc
cccccccccccc

The list would be (where each v is simply given a coordinate starting at 0 and going up):

0: +a, +c
1: +d
2: -c
3: -a
4: +e
5: +b
6: -d
7: -e
8: -b

Each strip would thus be (rectangles sorted from top to bottom):

0-1: a, c
1-2: a, d, c
2-3: a, d
3-4: d
4-5: d, e
5-6: b, d, e
6-7: b, e
7-8: b

for each strip, the overlap would be:

0-1: none
1-2: a/d, d/c
2-3: a/d
3-4: none
4-5: d/e
5-6: b/d, d/e
6-7: none
7-8: none

I'd imagine that a variation of the sort + enter/leave algorithm for the top-bottom check would be doable as well:

1. sort the rectangles we're currently analyzing in the strip, top to bottom, for rectangles with the same top-coordinate, sort them by bottom coordinate as well
2. iterate through the y-coordinates, and when you enter a rectangle, add it to the set, when you leave a rectangle, remove it from the set
3. whenever the set has more than one rectangle, you have overlap (and if you make sure to add/remove all rectangles that have the same top/bottom coordinate you're currently looking at, multiple overlapping rectangles would not be a problem

For the 1-2 strip above, you would iterate like this:

0. empty set, zero sum
1. enter a, add a to set (1 rectangle in set)
2. enter d, add d to set (>1 rectangles in set = overlap, store this y-coordinate)
3. leave a, remove a from set (now back from >1 rectangles in set, add to sum: y - stored_y
4. enter c, add c to set (>1 rectangles in set = overlap, store this y-coordinate)
5. leave d, remove d from set (now back from >1 rectangles in set, add to sum: y - stored_y)
6. multiply sum with width of strip to get overlapping areas

You would not actually have to maintain an actual set here either, just the count of the rectangles you're inside, whenever this goes from 1 to 2, store the y, and whenever it goes from 2 down to 1, calculate current y - stored y, and sum this difference.

Hope this was understandable, and as I said, this is off the top of my head, not tested in any way.

Answer 7

You can simplify this problem quite a bit if you split each rectangle into smaller rectangles. Collect all of the X and Y coordinates of all the rectangles, and these become your split points - if a rectangle crosses the line, split it in two. When you're done, you have a list of rectangles that overlap either 0% or 100%, if you sort them it should be easy to find the identical ones.

Answer 8

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.

Answer 9

Using the example:

   1   2   3   4   5   6

1  +---+---+
   |       |   
2  +   A   +---+---+
   |       | B     |
3  +       +   +---+---+
   |       |   |   |   |
4  +---+---+---+---+   +
               |       |
5              +   C   +
               |       |
6              +---+---+

1) collect all the x coordinates (both left and right) into a list, then sort it and remove duplicates

1 3 4 5 6

2) collect all the y coordinates (both top and bottom) into a list, then sort it and remove duplicates

1 2 3 4 6

3) create a 2D array by number of gaps between the unique x coordinates * number of gaps between the unique y coordinates.

4 * 4

4) paint all the rectangles into this grid, incrementing the count of each cell it occurs over:

   1   3   4   5   6

1  +---+
   | 1 | 0   0   0
2  +---+---+---+
   | 1 | 1 | 1 | 0
3  +---+---+---+---+
   | 1 | 1 | 2 | 1 |
4  +---+---+---+---+
     0   0 | 1 | 1 |
6          +---+---+

5) the sum total of the areas of the cells in the grid that have a count greater than one is the area of overlap. For better efficiency in sparse use-cases, you can actually keep a running total of the area as you paint the rectangles, each time you move a cell from 1 to 2.

---

In the question, the rectangles are described as being four doubles. Doubles typically contain rounding errors, and error might creep into your computed area of overlap. If the legal coordinates are at finite points, consider using an integer representation.

---

PS using the hardware accelerator as in my other answer is not such a shabby idea, if the resolution is acceptable. Its also easy to implement in a lot less code than the approach I outline above. Horses for courses.

Answer 10

what if there are 100 rectangles

Answer 11

Hey, Information provided in this blog is very intresting . I am Doing one project in finding intersecting rectangles i am using Sweeping Algorithm can i use this algorithm for my project ??? is this Algorithm efficient for my problem ??

Also , can u guys send me the link so that i can go through the sweeping algorithm throughly .....

Answer 12

Here's the code I wrote for the area sweep algorithm:

#include <iostream>
#include <vector>

using namespace std;


class Rectangle {
public:
    int x[2], y[2];

    Rectangle(int x1, int y1, int x2, int y2) {
        x[0] = x1;
        y[0] = y1;
        x[1] = x2;
        y[1] = y2; 
    };
    void print(void) {
        cout << "Rect: " << x[0] << " " << y[0] << " " << x[1] << " " << y[1] << " " <<endl;
    };
};

// return the iterator of rec in list
vector<Rectangle *>::iterator bin_search(vector<Rectangle *> &list, int begin, int end, Rectangle *rec) {
    cout << begin << " " <<end <<endl;
    int mid = (begin+end)/2;
    if (list[mid]->y[0] == rec->y[0]) {
        if (list[mid]->y[1] == rec->y[1])
            return list.begin() + mid;
        else if (list[mid]->y[1] < rec->y[1]) {
            if (mid == end)
                return list.begin() + mid+1;
            return bin_search(list,mid+1,mid,rec);
        }
        else {
            if (mid == begin)
                return list.begin()+mid;
            return bin_search(list,begin,mid-1,rec);
        }
    }
    else if (list[mid]->y[0] < rec->y[0]) {
        if (mid == end) {
            return list.begin() + mid+1;
        }
        return bin_search(list, mid+1, end, rec);
    }
    else {
        if (mid == begin) {
            return list.begin() + mid;
        }
        return bin_search(list, begin, mid-1, rec);
    }
}

// add rect to rects
void add_rec(Rectangle *rect, vector<Rectangle *> &rects) {
    if (rects.size() == 0) {
        rects.push_back(rect);
    }
    else {
        vector<Rectangle *>::iterator it = bin_search(rects, 0, rects.size()-1, rect);
        rects.insert(it, rect);
    }
}

// remove rec from rets
void remove_rec(Rectangle *rect, vector<Rectangle *> &rects) {
    vector<Rectangle *>::iterator it = bin_search(rects, 0, rects.size()-1, rect);
    rects.erase(it);
}

// calculate the total vertical length covered by rectangles in the active set
int vert_dist(vector<Rectangle *> as) {
    int n = as.size();

    int totallength = 0;
    int start, end;

    int i = 0;
    while (i < n) {
        start = as[i]->y[0];
        end = as[i]->y[1];
        while (i < n && as[i]->y[0] <= end) {
            if (as[i]->y[1] > end) {
                end = as[i]->y[1];
            }
            i++;
        }
        totallength += end-start;
    }
    return totallength;
}

bool mycomp1(Rectangle* a, Rectangle* b) {
    return (a->x[0] < b->x[0]);
}

bool mycomp2(Rectangle* a, Rectangle* b) {
    return (a->x[1] < b->x[1]);
}

int findarea(vector<Rectangle *> rects) {
    vector<Rectangle *> start = rects;
    vector<Rectangle *> end = rects;
    sort(start.begin(), start.end(), mycomp1);
    sort(end.begin(), end.end(), mycomp2);

    // active set
    vector<Rectangle *> as;

    int n = rects.size();

    int totalarea = 0;
    int current = start[0]->x[0];
    int next;
    int i = 0, j = 0;
    // big loop
    while (j < n) {
        cout << "loop---------------"<<endl;
        // add all recs that start at current
        while (i < n && start[i]->x[0] == current) {
            cout << "add" <<endl;
            // add start[i] to AS
            add_rec(start[i], as);
            cout << "after" <<endl;
            i++;
        }
        // remove all recs that end at current
        while (j < n && end[j]->x[1] == current) {
            cout << "remove" <<endl;
            // remove end[j] from AS
            remove_rec(end[j], as);
            cout << "after" <<endl;
            j++;
        }

        // find next event x
        if (i < n && j < n) {
            if (start[i]->x[0] <= end[j]->x[1]) {
                next = start[i]->x[0];
            }
            else {
                next = end[j]->x[1];
            }
        }
        else if (j < n) {
            next = end[j]->x[1];
        }

        // distance to next event
        int horiz = next - current;
        cout << "horiz: " << horiz <<endl;

        // figure out vertical dist
        int vert = vert_dist(as);
        cout << "vert: " << vert <<endl;

        totalarea += vert * horiz;

        current = next;
    }
    return totalarea;
}

int main() {
    vector<Rectangle *> rects;
    rects.push_back(new Rectangle(0,0,1,1));

    rects.push_back(new Rectangle(1,0,2,3));

    rects.push_back(new Rectangle(0,0,3,3));

    rects.push_back(new Rectangle(1,0,5,1));

    cout << findarea(rects) <<endl;
}