What is an Efficient algorithm to find Area of Ove

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

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 2

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 3

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

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

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 6

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