Databases
StackOverflow2013
Postsdbo
POWhat is an Efficient algorithm to find Area of Overlapping Rectangles
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhat is an Efficient algorithm to find Area of Overlapping Rectangles
    text
    copied!<h1>My situation</h1> <ul> <li>Input: a set of rectangles </li> <li>each rect is comprised of 4 doubles like this: (x0,y0,x1,y1)</li> <li>they are not "rotated" at any angle, all they are "normal" rectangles that go "up/down" and "left/right" with respect to the screen</li> <li>they are randomly placed - they may be touching at the edges, overlapping , or not have any contact</li> <li>I will have several hundred rectangles</li> <li>this is implemented in C#</li> </ul> <h1>I need to find</h1> <ul> <li>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)</li> <li>I don't need the geometry of the overlap - just the area (example: 4 sq inches)</li> <li>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)</li> </ul> <h1>Example</h1> <ul> <li>The image below contains thre rectangles: A,B,C</li> <li>A and B overlap (as indicated by dashes)</li> <li>B and C overlap (as indicated by dashes)</li> <li>What I am looking for is the area where the dashes are shown</li> </ul> <p>-</p> <pre><code>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 </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload