Ich suche nach einer Möglichkeit, Stadtteile in Städten automatisch als Polygone in einem Diagramm zu definieren.
Meine Definition einer Nachbarschaft besteht aus zwei Teilen:
- Ein Block : Ein Bereich zwischen mehreren Straßen, in dem die Anzahl der Straßen (Kanten) und Kreuzungen (Knoten) mindestens drei beträgt (ein Dreieck).
- Eine Nachbarschaft : Für jeden Block alle Blöcke direkt neben diesem Block und den Block selbst.
In dieser Abbildung finden Sie ein Beispiel:
ZB ist B4 ein Block, der durch 7 Knoten und 6 Kanten definiert ist, die sie verbinden. Wie die meisten Beispiele hier sind die anderen Blöcke durch 4 Knoten und 4 Kanten definiert, die sie verbinden. Außerdem umfasst die Nachbarschaft von B1 B2 (und umgekehrt), während B2 auch B3 enthält .
Ich verwende osmnx , um Straßendaten von OSM abzurufen .
- Wie kann ich mit osmnx und networkx ein Diagramm durchlaufen, um die Knoten und Kanten zu finden, die jeden Block definieren?
- Wie finde ich für jeden Block die benachbarten Blöcke?
Ich arbeite mich an einem Code, der einen Graphen und ein Koordinatenpaar (Breite, Länge) als Eingabe verwendet, den relevanten Block identifiziert und das Polygon für diesen Block und die Nachbarschaft wie oben definiert zurückgibt.
Hier ist der Code, mit dem die Karte erstellt wurde:
import osmnx as ox
import networkx as nx
import matplotlib.pyplot as plt
G = ox.graph_from_address('Nørrebrogade 20, Copenhagen Municipality',
network_type='all',
distance=500)
und mein Versuch, Cliquen mit unterschiedlicher Anzahl von Knoten und Graden zu finden.
def plot_cliques(graph, number_of_nodes, degree):
ug = ox.save_load.get_undirected(graph)
cliques = nx.find_cliques(ug)
cliques_nodes = [clq for clq in cliques if len(clq) >= number_of_nodes]
print("{} cliques with more than {} nodes.".format(len(cliques_nodes), number_of_nodes))
nodes = set(n for clq in cliques_nodes for n in clq)
h = ug.subgraph(nodes)
deg = nx.degree(h)
nodes_degree = [n for n in nodes if deg[n] >= degree]
k = h.subgraph(nodes_degree)
nx.draw(k, node_size=5)
Theorie, die relevant sein könnte:
Antworten:
Das Auffinden von Stadtblöcken mithilfe des Diagramms ist überraschenderweise nicht trivial. Grundsätzlich bedeutet dies, den kleinsten Satz kleinster Ringe (SSSR) zu finden, was ein NP-vollständiges Problem darstellt. Eine Übersicht über dieses Problem (und verwandte Probleme) finden Sie hier . Auf SO gibt es eine Beschreibung eines Algorithmus, um ihn hier zu lösen . Soweit ich das beurteilen kann, gibt es in
networkx
(oder in Python) keine entsprechende Implementierung . Ich habe diesen Ansatz kurz ausprobiert und ihn dann aufgegeben - mein Gehirn ist für diese Art von Arbeit heute nicht mehr auf dem neuesten Stand. That being said, werde ich eine Prämie niemandem vergeben , die diese Seite zu einem späteren Zeitpunkt besuchen könnte und eine getestete Implementierung eines Algorithmus schreiben, der die SSSR in Python findet.Ich habe stattdessen einen anderen Ansatz verfolgt und die Tatsache genutzt, dass der Graph garantiert planar ist. Kurz gesagt, anstatt dies als Diagrammproblem zu behandeln, behandeln wir dies als Bildsegmentierungsproblem. Zunächst finden wir alle verbundenen Regionen im Bild. Wir bestimmen dann die Kontur um jede Region und transformieren die Konturen in Bildkoordinaten zurück in Längen- und Breitengrade.
Angesichts der folgenden Importe und Funktionsdefinitionen:
Laden Sie die Daten. Zwischenspeichern Sie die Importe, wenn Sie dies wiederholt testen. Andernfalls kann Ihr Konto gesperrt werden. Ich spreche aus Erfahrung hier.
Beschneiden Sie Knoten und Kanten, die nicht Teil eines Zyklus sein können. Dieser Schritt ist nicht unbedingt erforderlich, führt aber zu schöneren Konturen.
Konvertieren Sie das Diagramm in ein Bild und suchen Sie nach verbundenen Regionen:
Suchen Sie für jeden beschrifteten Bereich die Kontur und konvertieren Sie die Konturpixelkoordinaten zurück in Datenkoordinaten.
Bestimmen Sie alle Punkte im Originaldiagramm, die innerhalb (oder auf) der Kontur liegen.
Es ist ziemlich einfach herauszufinden, ob zwei Blöcke Nachbarn sind. Überprüfen Sie einfach, ob sie einen Knoten gemeinsam nutzen:
quelle
Ich bin mir nicht ganz sicher, ob
cycle_basis
Sie die gewünschten Nachbarschaften erhalten, aber wenn dies der Fall ist, ist es ganz einfach, das Nachbarschaftsdiagramm daraus zu erhalten:quelle
nx.Graph(G)
ich eine Menge Informationen (Gerichtetheit und Multigraph - Typ) verliere so dass ich eine schwierige Zeit zu überprüfen Sie Ihre Antwort habe, als ich die neue Grafik beziehen kann nicht scheinenI
zu meine ursprüngliche GrafikG
.Ich habe keinen Code, aber ich denke, wenn ich auf dem Bürgersteig bin und an jeder Ecke nach rechts abbiege, fahre ich durch die Ränder meines Blocks. Ich kenne die Bibliotheken nicht, also rede ich hier nur algo.
Es ist eigentlich ein Algorithmus, um ein Labyrinth zu verlassen: Halten Sie Ihre rechte Hand an der Wand und gehen Sie. Es funktioniert nicht bei Schleifen im Labyrinth, Sie drehen sich nur um. Aber es gibt eine Lösung für Ihr Problem.
quelle
Dies ist eine Implementierung von Idee Hashemi Emad . Es funktioniert gut, solange die Startposition so gewählt ist, dass es eine Möglichkeit gibt, in einem engen Kreis gegen den Uhrzeigersinn zu treten. Bei einigen Kanten, insbesondere außerhalb der Karte, ist dies nicht möglich. Ich habe keine Ahnung, wie man gute Startpositionen auswählt oder wie man Lösungen filtert - aber vielleicht hat jemand anderes eine.
Arbeitsbeispiel (beginnend mit Kante (1204573687, 4555480822)):
Beispiel, bei dem dieser Ansatz nicht funktioniert (beginnend mit edge (1286684278, 5818325197)):
Code
quelle