You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

在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这样的闭环)。我想请教:

  1. 有没有基于NetworkX的现成方法可以直接提取这些四边形面?
  2. 如果需要手动实现的话,应该用什么思路?比如是遍历节点组合+判断是否构成4节点闭环?还是利用平面嵌入(planar embedding)的信息来处理?

希望有经验的朋友能给点思路或者代码示例,非常感谢!

备注:内容来源于stack exchange,提问作者Optical_flow_lover

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.04.15 15:45:31