How to create closed areas (convex polygons) from set of line segments ?
- by Marten
The following problem is in 2D, so some simplifications can be made when suggesting answers.
I need to create closed areas (defined either by line segments or just set of points - convex polygon) from a set of points/line segments.
Basically I used Voronoi to generate "roads". Then I changed some of the data. Now I need a way to loop through that data (which is still line segments but doesn't comply with Voronoi anymore) and generate "neigbourhoods" that are bordered with the "roads".
I looked at some graph diagrams and shortest path theories, but I could not figure it out.
Logically it could be done by starting at left edge from one point, finding the way back to that point using the shortest path with available lines (using only clockwise directions). Then mark this line set down and remove from the data. Then you can repeat the same process and get all the areas like that.
I tried to implement that but it did not get me anywhere as I could not figure out a way to write a C++ code that could do that. Problem was with choosing the most counterclockwise line from available lines from a specific point. All angle based math I did gave wrong answers because the way sin/cos are implemented in c++.
So to summarize - if you can help me with a totally new approach to the problem its good, if not could you help me find a way to write the part of the code that finds the shortest clockwise path back to the beginning point using the line segment set as paths back.
Thank you for your help!
