在平面图/二维网格中查找四边形面

Question

描述：

我有一组坐标点和一个邻接列表，描述每个点（节点）如何连接到其他点。利用这些，我在 Python 中使用 NetworkX 绘制了一个图表。

以下是点和邻接表：

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]
]

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]
]

我使用以下 Python 代码来可视化该图：

import matplotlib.pyplot as plt
import networkx as nx

# Create a new graph
G = nx.Graph()

# Add nodes with positions
for i, point in enumerate(points):
    G.add_node(i + 1, pos=point)

# Add edges
for i, connections in enumerate(adjacency_list):
    for j in connections:
        G.add_edge(i + 1, j)

# Get node positions
pos = nx.get_node_attributes(G, 'pos')

nx.draw(G, pos, with_labels=True, node_color='green', node_size=300, font_size=8, font_color='white')

plt.axis('off')
plt.show()

结果图如下所示：

目标：

我想确定哪些面是由该图中的节点形成的。具体来说，我只对四边形的面感兴趣（即由 4 个节点/顶点形成的面）。

例如，图像中标记的人脸1由节点[1,2,5,6]表示。因此，对于这个例子，输出应该是：

faces = [
    [1,2,6,5], [2,3,7,6], [4,5,11,10], [7,8,13,12], [8,9,14,13], [10,11,16,15], [12,13,19,18],
   [13,14,20,19], [15,16,22,21], [16,17,23,22], [18,19,25,24]

]

注意事项：

面部 1（其他面部也类似）可以是任何有效面部（我选择此顺序是为了使其与图像一致）。

请注意，

adjacency_list

不一定按特定顺序（顺时针或逆时针）列出节点。

Answer 1

如果我理解得很好，你正在尝试在图中找到大小为 4 的所有简单循环。

NetworkX 非常简单：

for c in nx.simple_cycles(G):
    if len(c)==4: print(c)

您可能需要更多地了解图论（特别是cycles）或查看NetworkX关于Cycles的文档。

干杯！