algorithm - 如何找到无向图中的所有多边形？

Question

给定一个无向图，找到该图中所有多边形的算法是什么？这是一个带有彩色多边形的示例图。

注意有一个多边形 ABCIHGJKLMLKA，其中包含节点 KLM，但多边形 CDEG 不包含 F。

我已经阅读了此问题的解决方案，但没有我所拥有的叶要求。先前解决方案中存在的一些公理是每条边仅使用两次，但是死胡同边总共需要遍历四次。也就是说，存在一个包含所有外部节点 ABCDEFGJKLMLKA 的多边形，但它被丢弃，因为它是面向外的。

这里描述了一个类似问题的解决方案，没有叶子:http://blog.reactoweb.com/2012/04/algorithm-101-finding-all-polygons-in-an-undirected-graph/

更新

似乎链接的解决方案没有按预期工作，举例说明:

该算法将遍历图 A-B-C-A-E-D-C，识别三角形 ABC，但也不是预期的多边形 CAEDC

更新 2

这个问题实际上有一个简单的解决方案:删除包含其他多边形点的较大多边形。

Answer 1

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

我会用你的例子来说明这一点:

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

这应该是您已经熟悉的算法应该如何工作的粗略概念。但是，它可能会进行许多改进。