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

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 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.