如何在无向图中找到所有多边形？ [英] How do I find all polygons in an undirected graph?
问题描述
请注意，多边形ABCIHGJKLMLKA，其中包含节点KLM，但多边形CDEG不包含F.
我已经读过这个问题的解决方案，但没有我的叶子要求。先前解决方案中存在的一些公理是每个边缘只使用两次，但是死端边缘总共需要遍历四次。也就是说，存在一个包含所有外部节点ABCDEFGJKLMLKA的多边形，但是它会被丢弃，因为它会面向外部。解决类似问题的一种解决方案，在这里描述： http://blog.reactoweb.com/2012/04/algorithm-101-finding-all-polygons-in-an-undirected-graph/
UPDATE
似乎解决方案并没有像预期的那样工作，举例说明：
算法将遍历图ABCAEDC，标识三角形ABC，也可以是多边形CAEDC，它不是意图
UPDATE2
实际上，这个问题有一个简单的解决方法：删除包含其他多边形的较大多边形
step |描述
1a |而deg（v）= 0的顶点存在
1b |用deg（v）= 0标记顶点为叶
|
2 |在没有标记为叶
|的所有顶点上运行算法
3a |对于标记为叶
3b |的每个顶点如果顶点位于多边形
3c |内部检查它的边缘//你必须决定在这种情况下做什么
3d |调整多边形
我将用您的示例说明这一点：
step |结果
1a |找到F和M
1b |将F和M标记为
1a |找到L
1b |将L标记为叶
a |找不到：转到步骤2
|
2 |查找多边形：AKJGHICB（1），CIHG（2）和CGED（3）
|
3a |我们有F，M和L
3b |检查F：
| poly（1）：cast ray：偶数结果 - >外
| poly（2）：cast ray：偶数结果 - >外
| poly（3）：cast ray：偶数结果 - >外
|因为F总是在外面：不需要进一步的操作，取消标记F
3b * |检查M：
| poly（1）：投射射线：奇数结果 - >内
|因为M在多边形内：请检查如何添加它
3c |检查边缘M-L：
|检查L是否是poly（1）
|的一部分如果是：将路径添加到poly（1）（步骤3d）
|如果否：检查L是否在poly（1）
|内 - >不检查L：奇数结果 - >内
|如果在里面：跟随路径，即步骤3c与边缘L-K
|如果在外面：未定义行为
| - >在
3c |内部检查边缘L-K：
|检查K是否是poly（1）
|的一部分 - >是：添加路径到poly
3d |以聚（1）AKJGHICB
|用KLK
|取代K取消标记K //注意K从未标记）
|从路径
|中删除K将L替换为LML
|取消标记L
|从路径
|中删除L. unmark M //注意你应该检查是否有更多
| //顶点来替换
|从路径
|中删除M poly（1）现在是AKLMLKJGHICB
3a |我们没有标记顶点
|完成
*注意，在步骤3b中，我们可以首先找到L / checked L.然后它会是这样的：
3b |检查L：
| poly（1）：投射射线：奇数结果 - >内
|因为L在多边形内：请检查如何添加它
3c |检查L-K（或M-L，这将工作如上，并最终尝试L-K）
|检查K是否是poly（1）
|的一部分如果是：添加到poly（1）
|的路径 - >是
3d |以聚（1）AKJGHICB
|用KLK
|取代K取消标记K
|从路径
|中删除K取消标记L
|从路径
|中删除L. poly（1）现在是AKLKJGHICB
3a |我们从现在开始有一点不太详细，因为它又是一样的
3b |检查M：
| poly（1）：投射射线：奇数结果 - >内
| ...
3c |检查M-L
| L是poly（1）
3d |的一部分用LML替换poly中的L，取消标记L和M
|完成
这应该是一个粗略的想法，说明一个你熟悉的算法应该如何工作。不过，它可能会有很多改进。
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:
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.
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.
这篇关于如何在无向图中找到所有多边形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
