Wie finde ich alle inneren Zellen innerhalb eines räumlichen Netzwerks von Knoten? ⇐ Python

[Guest]

Ich habe ein beliebiges Netzwerk von Knoten. Dieses Netzwerk könnte etwa so aussehen:


Die Knoten dieses Netzwerks haben räumliche Positionen und können daher nicht verschoben oder neu organisiert werden. Jeder Knoten hat eine x-Koordinate, eine y-Koordinate und eine eindeutige ID. Ich verwende einen networkx.Graph, um die Verbindungen zwischen allen Knoten zu speichern.

Code: Select all

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

Ich möchte alle Zellen in diesem Netzwerk finden. Etwas wie:

Code: Select all

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.
"""
...

Beachten Sie, dass ich keine äußeren Zellen finden möchte, sondern nur die inneren, die nichts anderes enthalten.
Ich habe versucht, nach etwas anderem zu suchen Algorithmen, um dieses Problem zu lösen, habe aber keine gefunden. Ich habe in den Bibliotheken shapely und geonetworkx nachgesehen und auch hierfür keine Methoden gefunden.