Find all non-overlapping polygons in a list of edges/vertices

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 开发者_Python百科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)

What you are describing is the problem of finding all minimal circuits in a graph. (That it happens to have a geometric model is irrelevant, I think.) There's a paper here for finding a minimal circuit. You can build on that by removing the edges of the minimal circuit and running the algorithm again.

The problem is also discussed in this thread for the case of directed graphs. You can turn your graph into a directed graph by making a copy of each edge with the vertices reversed and then treating it as directed. The only problem will be that each polygon will be found twice, once in each traversal direction. You can clean that up with a post-process step or perhaps by some clever bookkeeping while the algorithm is running.

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.