Как мне найти все внутренние ячейки в пространственной сети узлов? ⇐ Python

[Anonymous]

У меня есть произвольная сеть узлов. Эта сеть может выглядеть примерно так:


Узлы этой сети имеют пространственное положение, поэтому их нельзя перемещать или реорганизовывать. Каждый узел имеет координату x, координату y и уникальный идентификатор. Я использую networkx.Graph для хранения связей между всеми узлами.

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

import uuid
from dataclasses import dataclass

import networkx
import shapely

@dataclass
class Node:
x: float
y: float
node_id: uuid.UUID

example_node = Node(x=0, y=1, node_id: uuid.uuid4())
G = networkx.Graph()
G.add_node(example_node.node_id.hex, data=example_node)
... # more nodes added
... # connections between nodes added

Я хочу найти все ячейки в этой сети. Что-то вроде:

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

def get_graph_cells(G: networkx.Graph) -> list[list[Node]]:
"""
Returns a list of lists, where the outer list is the cells, and the inner
list is the Nodes in that cell.
"""
...

Обратите внимание, что мне не нужны внешние ячейки, а только внутренние, внутри которых больше ничего нет.
Я пробовал искать разные алгоритмы для решения этой проблемы, но их не нашел. Я просмотрел библиотеки shapely и geonetworkx и не нашел для этого никаких методов.

Подробнее здесь: https://stackoverflow.com/questions/754 ... k-of-nodes