在planar graph/2D mesh中查找quad faces的技术求助
技术求助:在平面图形(Planar Graph)/2D网格中查找四边形面
大家好,我现在有一组坐标点和对应的邻接表,用来描述节点间的连接关系,并且已经用Python的NetworkX库把这个平面图画出来了。现在我卡壳了:如何从这个平面图形中找出所有的四边形面(quad faces)?
我的坐标点与邻接表
- 坐标点列表(共25个节点,对应编号1-25):
points = [ [1449, 1427], [1568, 1349], [1828, 1262], [1054, 1294], [1236, 1186], [1432, 1124], [1754, 1032], [2122, 968], [2591, 953], [790, 957], [1069, 881], [1720, 738], [2183, 691], [2633, 723], [557, 495], [878, 465], [1238, 433], [1690, 412], [2229, 395], [2705, 368], [432, 116], [772, 74], [1234, 27], [1680, 0], [2267, 21] ]
- 邻接表(索引对应节点编号-1,每个子列表是对应节点的邻居节点编号):
adjacency_list = [ [2,5], [1,3,6], [2,7], [5,10], [1,4,6,11], [2,5,7], [3,6,8,12], [7,9,13], [8,14], [4,11,15], [5,10,16], [7,13,18], [8,12,14,19], [9,13,20], [10,16,21], [11,17,15,22], [16,18,23], [12,17,19,24], [13,18,20,25], [19,14], [15,22], [21,16,23], [17,22], [18,25], [19,24] ]
我已有的可视化代码
我用下面的代码把图可视化出来了,能看到这是一个结构化的平面网格类图形,但不知道怎么提取其中的四边形面:
import networkx as nx import matplotlib.pyplot as plt # 构建图结构 G = nx.Graph() # 添加节点与坐标属性 for node_idx in range(1, len(points)+1): G.add_node(node_idx, pos=points[node_idx-1]) # 添加边 for idx, neighbors in enumerate(adjacency_list): current_node = idx + 1 for neighbor in neighbors: G.add_edge(current_node, neighbor) # 绘图展示 pos = nx.get_node_attributes(G, 'pos') nx.draw(G, pos, with_labels=True, node_size=300, font_size=8) plt.show()
我的具体问题
从可视化结果能看出来,图里有很多由4个节点围成的四边形面(比如节点1-2-6-5这样的闭环)。我想请教:
- 有没有基于NetworkX的现成方法可以直接提取这些四边形面?
- 如果需要手动实现的话,应该用什么思路?比如是遍历节点组合+判断是否构成4节点闭环?还是利用平面嵌入(planar embedding)的信息来处理?
希望有经验的朋友能给点思路或者代码示例,非常感谢!
备注:内容来源于stack exchange,提问作者Optical_flow_lover
相关产品推荐
相关产品推荐

