Abstract Art

This problem asks you to determine the total area of a group of polygons, as well as the area of their union.

Finding the total area is trivial. Simply apply the polygon area algorithm and sum.

The union takes some more work. We have to walk around the hull. Choose some point (min X) and a direction (counter clockwise). Take the edge going in that direction and intersect it with each other line. Our next point is either the other endpoint of this edge, or the closest intersection point. If the former, repeat the process starting there. If the latter, we repeat the process at the intersection. How do we determine which direction to go, though? note that since we are progressing CCW around the hull, the interior must always be to our left. This means that any intersection will be a turn to the RIGHT. So use cross product to find which of the two of the new edge endpoints lie to the right of the edge we just arrived from.

Store each point we visit in a list, the intersections and polygon vertices which we determined were on the hull. Apply the polygon area algorithm.

There are at max 20 sides to a polygon, and 1000 polygons, so the O(n^2) algorithm is fast enough.