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!