注意,有一个多边形ABCIHGJKLMLKA,它包括节点KLM,但多边形CDEG不包括F。
我读过关于这个问题的解决方案,但没有像我这样的leaf要求。在以前的解决方案中存在的一些公理是,每条边只使用两次,但是死端边总共需要遍历四次。也就是说,存在一个包含所有外部节点ABCDEFGJKLMLKA的多边形,但是它会被丢弃,因为它将朝外。
下面介绍了一种类似问题的解决方案,即sans the leafs:http://blog.reactoweb.com/2012/04/algorithm-101-finding-all-polygons-in-an-undirected-graph/
更新
链接的解决方案似乎无法按预期工作,下面举例说明:
该算法将遍历图A-B-C-A-E-D-C,识别三角形ABC,也识别多边形CAEDC,这是不需要的
最新动态
实际上,这个问题有一个简单的解决方案:删除包含其他多边形点的较大多边形。
Re AndreyT建议使用DCEL:双连通边列表表示法的显著特征是,对于每个无向边,有两个列表节点,每个方向一个。我们将这些节点称为省道,并认为它们有一个头部和一个尾部。给定一个省道(例如,H-
多边形(通常称为面)可以通过查找排列的排列循环来找到,排列循环将每个省道按逆时针顺序映射到具有相同头部的下一个省道的反面。例如,如果我们从省道C开始-
C->D (E->D is next) D->E (G->E is next) E->G (C->G is next) G->C (D->C is next) C->D
恢复面部C-D-E-G-C以A-开头
A->B B->C C->I I->H H->G G->J J->K K->L L->M M->L L->K K->A A->B,
这就是A-B-C-I-H-G-J-K-L-M-L-K-A面。
这种方法需要一个连通图。(它将在断开的图上工作,但它可能不会给出您想要的结果。)它也会产生无限的面,你已经指出这是不可取的。要在无限面上找到一个镖(可以用来识别它),找到具有最小y坐标的顶点,通过最小x坐标打破联系。然后找到最后一个飞镖,它的头部以逆时针的顺序从光线向右直射。
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
这应该是一个粗略的想法,你已经熟悉的算法应该如何工作。然而,它可能会有许多改进。
我在location _ table(point _ location geometry)中存储了位置,现在我在谷歌地图上绘制了一个多边形,并将该多边形(几何)传递给后端,我想找到该多边形内的所有位置。 当我将多边形从谷歌地图传递到后端时,这给了我随机的结果。它没有给我多边形内的所有点。它给了我甚至在多边形之外的点。 在 postgis 中准确查找多边形内所有点的正确方法是什么(也包括边界情况)
我在Python3中有一个简单的代码,使用igraph返回我添加到无向图中的边。 但是,如果按照输入源和目标的顺序设置源和目标,它会返回边缘。在这种情况下,源=0,目标=1 我的猜测是,它不是真正的无向图。 我的问题是,如何得到一个真正的无向图,即使我在g.es.find()函数中切换了源节点和目标节点,它也会返回边,就像对无向图一样?
设G=(V,E)是无向图。如果G的每个圈在F中至少有一条边,则称边集F E为反馈边集。 a)最小尺寸反馈边集:由于图是无权的,我们可以使用DFS。我们像往常一样从任意顶点开始DFS。当我们遇到一个后边时,我们将它插入反馈边集。当DFS完成时,该集将是答案。 b)最小权重反馈边集:由于图是加权的,我们可以使用Kruskal。但是Kruskal通常从最小权重的边开始。如果我们可以否定所有的边权重,然后
我需要找到一个算法来找到有向图中的所有根,在O(n m)。 我有一个寻找单个根的算法: 在v中的某些v上运行DFS(v)。如果结果是一个生成树,则v是根。否则,结果就是树木成林。然后: 在最后一棵树的根上运行DFS(u)。如果结果是一棵生成树,那么u是根。否则,图中没有根 现在,如果我想找到所有的根,最好的方法是每次在最后一棵树的不同顶点上运行上述算法O(n)次吗?假设我找到了一个根,如果另一个根
我正在编写一个使用电网格分析的程序。所以我有电路的节点[A,B,C,D]和连接节点[0,1,2,3,4,5,6,7,8]的分支。 如何在具有多条边的无向图中找到最短的循环? 图形图像(4个节点,9条边/分支): 周期: 我需要的循环数是:循环=分支-(节点-1),在本例中我需要6个循环。 我将这些数据存储在这样的数组中: 我很乐意看到任何语言的算法。
我有一个无向图,我想从一个起始节点列出所有可能的路径。2个节点之间的每个连接在列出的路径中是唯一的,例如,给出以下图表示: 我无法使用现有的算法来完成它,我知道像DFS。任何帮助都将非常感谢。