How to calculate the area of multiple polygons?

Question

I posted some days ago this question: How to intersect multiple polygons?. Now I implemented a sweep line algorithm as recommended (concrete the one from Martinez, Rueda and Feito).

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

A picture of what I mean:

I think this should cover all the special cases; intersections are handled by the sweep line algorithm.

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.

Not that good. Can you give me a hint how to calculate the total area?

Answer 1

The standard vertex order is counterclockwise for polygons and clockwise for holes. If you store your data using this convention, just compute the area with the standard polygon area calculation method. Areas of the holes will be negative.

If you have them in some other order, then you have a problem. Better fix it now.