I have a list of edges and a list of vertices. Each edge references two vertices, each vertex maintains a list of edges.
I want to find all non-overlapping polygons produced from this graph.
An example would be
0,0) (4,0) (4,2) (4,4) (2,4) (2,2) (4,2) (6,2) (6,6) (0,6) (0,0)
This path should describe each unique edge with collisions on some verticies. In the actual graph, the vertices are distinct. The two polygons I would need from this set are (0,0) (4,0) (4,2) (2,2) (2,4) (4,4) (4,2) (6,2) (6,6) (0,6) and (2,2) (2,4) (4,4) (4,2)
Well, I was thinking...
The only vertices of particular interest are ones with more than two edges. To find all vertices with more than two edges is O(n). Then to find the tighest closed loop is the same as finding the smallest theta between a given an edge and another edge at a given vertex (if the vertices are ccw, this is the smallest angle clockwise from the current edge). In order to find all tightest closed loops, I need to check all edge ccw edge pairs at a vertex where the edge count is greater than 2. This is the initialization of the trace. From that point on, the trace will always pick the next edge with the smallest theta clockwise. Once the path is returned, I move to the next edge pair in the root vertex, and path again. Once all pairs are checked, I move to the next vertex with an edge count greater than 2. Now, if I can only determine if I am falling into a known loop and not trace. Maybe if the first two vertices of a path occur in the same order in an already known polygon...
How does that sound? I know it's no djikstra, but it will work, and hopefully faster than finding all cycles brute force.