Calculate the area of the shape created by multiple paths

Question

I'm trying to write an algorithm to calculate the area created by multiple paths that can be overlapping or not. Here is an example:

Basics

• 4 separate paths (A,B,C,D) which are a collection of vertices (A1,A2,...)
• Area desired is represented by green

Edge Cases

• As shown with B, a path might have segments that don't contribute to a filled shape
• As shown with C, a path might be completely enclosed by other paths and therefore should basically be ignored.
• As shown with D, paths may create independent shapes
• As shown with A and B, it should be a union of all the shapes

My first question is if an algorithm for this already exists. If it does, it would save me a lot of effort :). I tried searching around but I don't even know how to describe this problem concisely.

Assuming one doesn't exist for this exact purpose I have to move on to figuring it out myself. I'm assuming the right data structure for the job is a graph. I'm thinking I will add points for each intersection (highlighted in red) as I insert paths into the graph.

Then "all I need" is an algorithm for tracing around the outside of each shape because calculating the area of those irregular polygons will be simple. Does something like that already exist? My primary hangups when I think about how to do this are:

• What vertex do I "start" at?
• How do I account for multiple shapes (D as well as A,B,C)?
• How do I account for the parts of shapes like formed by A1,A5,A5 where I'll be visiting that intersection point multiple times?

I'm not necessarily looking for a complete solution, I'd love thoughts on if you think I'm approaching this the best way so far and if you have any ideas/suggestions on how to achieve this.

Thanks in advance!

Answer 1

With the help from some of the hints on this post and elsewhere, I came up with a solution.

The Data Structure

The data structure is relatively simple. It is a collection of Nodes that are connected by Edges.

Each node stores the coordinates of where it lies in space and each segment is represented by two directional edges, one in each direction. Each intersection of line segments is broken up with a new Node. Note the coordinates of the intersections are left off the diagram but are included in the data structure.

The Algorithm

Find All Cycles

• 1. Pick any edge and choose the next edge that is closest to clockwise from the edge you entered the node on.
• 2. Record whether the angle between the connecting edges is a reflex angle (> 180 degrees) or not.
• 3. Record the series of nodes visited
• 4. Mark the edge as used
• 5. Follow that new edge to the next node and repeat until reaching the first node again.

At the end, the cycle will have the points that it is composed of and a count of reflex and non-reflex angles. If there are more reflex angles, it is considered to be an outside cycle and is thrown out. Otherwise, it is included in a preliminary list of polygons to include in the final result.

Repeat this cycle finding process until every edge has been used.

Filter Polygons

Filter out any resulting polygons that are entirely inside another. This can be done by testing only the first point of one polygon to see if it's inside another. That's because we know we will never have any intersecting polygons.

Calculate the Area of Each Remaining Polygon

At this point, we just need to calculate the area of each polygon and add them together for our solution.

Some Details

It's important to note that in the case where we get to a node and the only remaining edge is the returning edge, it counts as a 360 degree angle and therefore a reflex angle.

Also, it's important to note that each angle of each cycle must be counted towards the reflex and non-reflex count, including the first and last. Otherwise, a plus sign arrangement of simple paths (+) will result in a valid polygon.

Example

All of the cycles from my original example are represented here:

For more information on my process and a walk through of the algorithm, you can see my case study.

Answer 2

If the polygons are overlapping, you can't spare a union algorithm that will "merge" the overlaps. https://en.wikipedia.org/wiki/Boolean_operations_on_polygons. This involves the detection of intersections between the sides and a topological reorganization. Nothing really easy.

It is likely that an simpler technique is possible if you consider decomposing the domain in slices defined by horizontal lines though all vertices (this takes a sort on the vertex ordinates). Also consider the lines through the intersections. These can be obtained by a standard line intersection algorithm (https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm). Then the problem reduces to the union of trapezia in every slice, with no intersecting sides. It is easy to merge two overlapping trapezia into one.