Wie finde ich alle inneren Zellen innerhalb eines räumlichen Netzwerks von Knoten?
Posted: 12 Jan 2025, 10:10
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.
Ich möchte alle Zellen in diesem Netzwerk finden. Etwas wie:
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.
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
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.
"""
...
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.