title: How to calculate the area of multiple polygons?
body: <p>I posted some days ago this question: <a href="https://stackoverflow.com/questions/9399711/how-to-intersect-multiple-polygons">How to intersect multiple polygons?</a>. Now I implemented a sweep line algorithm as recommended (concrete the one from Martinez, Rueda and Feito).</p>
  
  <p>The result is a set of polygons that do not overlap. But these polygons can contain each other (holes) or touch the boundaries (being a hole or an island polygon).</p>
  
  <p>A picture of what I mean:</p>
  
  <p><img src="https://i.stack.imgur.com/GqM2X.png" alt="a picture of what I mean"></p>
  
  <p>I think this should cover all the special cases; intersections are handled by the sweep line algorithm.</p>
  
  <p>Now I need the area of the polygons (marked gray). My first idea was to add polygon by polygon and to check if they contain each other and use some intelligent selection mechanism to only select the needed polygons. But this generates some O(n^2) algorithm: For each polygon to process, every edge has to be compared to every edge that is already processed.</p>
  
  <p>Not that good. Can you give me a hint how to calculate the total area?</p>