How do I find all polygons in an undirected graph?

Question

Given an undirected graph, what would be an algorithm to find all polygons within such graph? Here is an example graph with polygons in colour.

Note that there is a polygon ABCIHGJKLMLKA, which includes the nodes KLM, but the polygon CDEG does not include F.

I have read of solutions to this problem, but without the leaf requirement that I have. Some axioms that exist in previous solutions is that each edge is only used twice, however dead-end edges would need to be traversed four times in total. That is, there exists a polygon that contains all the outer nodes ABCDEFGJKLMLKA, however it is discarded as it would be outward facing.

One solution to a similar problem, sans the leafs, is described here: http://blog.reactoweb.com/2012/04/algorithm-101-finding-all-polygons-in-an-undirected-graph/

UPDATE

It seems that the solution linked does not work as intended, an example of this is illustrated:

problem

The algorithm would traverse the graph A-B-C-A-E-D-C, identifying the triangle ABC, but also the polygon CAEDC, which is not intended

UPDATE2

There is a simple solution to this problem actually: remove larger polygons which contain other polygon's points.

1. Remove the leaves (i.e. check for in/out-degree); 2. Use the algorithm you found which can handle it without leaves. — Sebastian Höffner
But you can exclude them for your algorithm, such that it will find your polygons CIHG, CGED and AKJGHICB without having problems. Unless you really need to find the weird polygon which includes l and m - but then you could do a similar approach by not checking in-/out-degrees but by checking the outer boundaries. — Sebastian Höffner
But if I only remove the F node the algorithm I found won't work as it will have to re-traverse KL and LM four times instead of two. — user975989
@user975989: Well, a properly built DCEL will, by definition, contain your regions as edge-cycles, already prepared for you. So, basically the task of building DCEL implicitly includes solving your problem as well. That's why once you have DCEL, your problem becomes trivial. I understand that this is not a very helpful response, but if I were you, I'd spend some time reading about DCEL, which is, again, a de-facto standard data structure for such problems. — AnT

Sebastian Höffner Sebastian Höffner · Accepted Answer · 2014-08-16T00:21:39

step | description
1a   | while vertices with deg(v) = 0 exist
1b   |    mark vertices with deg(v) = 0 as leaf
     | 
2    | run algorithm on all vertices which are not marked as leaf
     | 
3a   | for each vertex marked as leaf 
3b   |    if vertex is inside a polygon
3c   |       check its edges // you have to decide what to do in which case
3d   |       adjust polygon

I will illustrate this with your example:

step | result
1a   | find F and M
1b   |   mark F and M as leaf
1a   | find L
1b   |   mark L as leaf
1a   | find nothing: go to step 2
     |
2    | finds polygons: AKJGHICB (1), CIHG (2), and CGED (3)
     |
3a   | we have F, M, and L
3b   |   check F: 
     |     poly (1): cast ray: even result -> outside
     |     poly (2): cast ray: even result -> outside
     |     poly (3): cast ray: even result -> outside
     |     since F is always outside: no further action needed, unmark F
3b*  |   check M:
     |     poly (1): cast ray: odd result -> inside
     |     since M is inside a polygon: check how to add it
3c   |   check edge M-L:
     |     check if L is part of poly (1)
     |       if yes: add path to poly (1) (step 3d)
     |       if no: check if L is inside poly (1)
     |       -> no check L: odd result -> inside
     |         if inside: follow path, i.e. step 3c with edge L-K
     |         if outside: undefined behaviour
     |           -> inside
3c   |   check edge L-K:
     |     check if K is part of poly (1)
     |       -> yes: add path to poly
3d   |   Take poly (1) AKJGHICB
     |     replace K with KLK
     |     unmark K // note that K was never marked)
     |     remove K from path
     |     replace L with LML
     |     unmark L
     |     remove L from path
     |     unmark M // note that you should check if there are more
     |              // vertices to come for the replacement
     |     remove M from path 
     |   poly (1) is now AKLMLKJGHICB
3a   | we have no marked vertices left
     | finish


* note that in step 3b we could first have found L/checked L. Then it would be like this:

3b   |   check L:
     |     poly (1): cast ray: odd result -> inside
     |     since L is inside a polygon: check how to add it
3c   |   check L-K (or M-L, that would work as above and eventually try L-K)
     |     check if K is part of poly (1)
     |     if yes: add path to poly (1)
     |     -> yes
3d   |   Take poly (1) AKJGHICB
     |     replace K with KLK
     |     unmark K
     |     remove K from path
     |     unmark L
     |     remove L from path
     |   poly (1) is now AKLKJGHICB
3a   | we have M left // from now on a bit less detailed because it's the same again
3b   |   check M:
     |     poly (1): cast ray: odd result -> inside
     |   ...
3c   |   check M-L
     |     L is part of poly (1)
3d   |   replace L in the poly with LML and unmark L and M
     | finish

This should be a rough idea of how an algorithm with the one you are already familiar with should work. However, it's probably open for many improvements.

How do I find all polygons in an undirected graph?

2 Answers