Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is an Efficient algorithm to find Area of Overlapping Rectangles

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 
like image 697
namenlos Avatar asked Oct 28 '08 19:10

namenlos


People also ask

How do you find the overlapping rectangles in Python?

If we have two (axis-aligned) rectangles, we have to check whether they overlap or not. So, if the input is like R1 = [0,0,2,2], R2 = [1,1,3,3], then the output will be True. otherwise, return True.

What is overlap area?

The OverlapArea function is a Spatial Numeric measurement that calculates the total area (or length or count) of overlap between features in the current layer and features in the target layer.


2 Answers

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 S1...Sn consists of disjoints segments D1...Dk. Adding Sn+1 is very easy, you just have to locate both ends of Sn+1 amongs the ends of D1...Dk.
  • assuming that you know the union of segments S1...Sn consists of disjoints segments D1...Dk, removing segment Si (assuming that Si was included in Dj) means recomputing the union of segments that Dj consisted of, except Si (using the static algorithm).

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

like image 141
Camille Avatar answered Sep 21 '22 08:09

Camille


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.

like image 31
Will Avatar answered Sep 19 '22 08:09

Will