Поиск лиц на графике с использованием координат точек и списка смежности ⇐ Python

[Anonymous]

Описание:
У меня есть набор координатных точек и список смежности, который описывает, как каждая точка (узел) связана с другими точками. Используя их, я построил график с помощью NetworkX в Python.
Вот точки и список смежности:

Код: Выделить всё

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 не обязательно перечисляет узлы в конкретном порядке (по часовой стрелке или против часовой стрелки).

Подробнее здесь: https://stackoverflow.com/questions/790 ... cency-list