Calculate the area of the shape created by multiple paths


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:

Example Paths

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!