Szukam sposobu automatycznego zdefiniowania dzielnic w miastach jako wielokątów na wykresie.
Moja definicja sąsiedztwa składa się z dwóch części:
- Blok : Obszar zawarty między wieloma ulicami, w którym liczba ulic (krawędzie) i skrzyżowań (węzły) wynosi co najmniej trzy (trójkąt).
- Sąsiedztwo : dla każdego bloku wszystkie bloki bezpośrednio przylegające do tego bloku i sam blok.
Zobacz tę ilustrację jako przykład:
Np. B4 to blok zdefiniowany przez 7 węzłów i 6 krawędzi łączących je. Jak większość przykładów tutaj, pozostałe bloki są zdefiniowane przez 4 węzły i 4 krawędzie łączące je. Ponadto sąsiedztwo z B1 obejmuje B2 (i vice versa), a B2 również B3 .
Korzystam z osmnx, aby uzyskać dane uliczne z OSM.
- Używając osmnx i networkx, w jaki sposób mogę przechodzić przez wykres, aby znaleźć węzły i krawędzie, które definiują każdy blok?
- Jak mogę znaleźć sąsiednie bloki dla każdego bloku?
Pracuję nad kawałkiem kodu, który przyjmuje na wejściu wykres i parę współrzędnych (szerokość, długość), identyfikuje odpowiedni blok i zwraca wielokąt dla tego bloku i sąsiedztwa, jak zdefiniowano powyżej.
Oto kod użyty do stworzenia mapy:
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)
i moja próba znalezienia klik z różną liczbą węzłów i stopni.
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)
Teoria, która może być istotna:
Odpowiedzi:
Znalezienie bloków miast za pomocą wykresu jest zaskakująco nietrywialne. Zasadniczo sprowadza się to do znalezienia najmniejszego zestawu najmniejszych pierścieni (SSSR), co stanowi problem NP-zupełny. Przegląd tego problemu (i powiązanych problemów) można znaleźć tutaj . Na tak, to jest jeden opis algorytmu rozwiązać go tutaj . O ile mi wiadomo, nie ma odpowiedniej implementacji w
networkx
(lub w Pythonie). Próbowałem krótko to podejście, a potem je porzuciłem - mój mózg nie jest dziś w stanie sprostać tego rodzaju pracy. Biorąc to pod uwagę, przyznam nagrodę każdemu, kto może odwiedzić tę stronę w późniejszym terminie i opublikować przetestowaną implementację algorytmu, który znajdzie SSSR w pythonie.Zamiast tego wybrałem inne podejście, wykorzystując fakt, że wykres ma zagwarantowaną płaskość. W skrócie, zamiast traktować to jako problem z grafem, traktujemy to jako problem z segmentacją obrazu. Najpierw znajdujemy wszystkie połączone regiony na obrazie. Następnie określamy kontur wokół każdego regionu, przekształcamy kontury we współrzędnych obrazu z powrotem na długości i szerokości geograficzne.
Biorąc pod uwagę następujące definicje importu i funkcji:
Załaduj dane. Wykonuj buforowanie importu, jeśli testujesz to wielokrotnie - w przeciwnym razie twoje konto może zostać zbanowane. Mówiąc z doświadczenia tutaj.
Przycinaj węzły i krawędzie, które nie mogą być częścią cyklu. Ten krok nie jest absolutnie konieczny, ale powoduje ładniejsze kontury.
Konwertuj wykres na obraz i znajdź połączone regiony:
Dla każdego oznaczonego regionu znajdź kontur i przekonwertuj współrzędne piksela konturu z powrotem na współrzędne danych.
Określ wszystkie punkty na oryginalnym wykresie, które mieszczą się w (lub na) konturze.
Ustalenie, czy dwa bloki są sąsiadami, jest dość łatwe. Wystarczy sprawdzić, czy współużytkują węzeł:
źródło
Nie jestem do końca pewien,
cycle_basis
czy da ci to dzielnice, których szukasz, ale jeśli tak, to łatwo jest uzyskać z niego wykres sąsiedztwa:źródło
nx.Graph(G)
tracę dużo informacji (ukierunkowanie i typ multigraficzny), więc trudno mi zweryfikować twoją odpowiedź, ponieważ nie mogę powiązać nowego wykresuI
z mój oryginalny wykresG
.Nie mam kodu, ale myślę, że gdy będę na chodniku, jeśli będę nadal skręcał w prawo na każdym rogu, będę przechodził przez krawędzie mojego bloku. Nie znam bibliotek, więc porozmawiam tutaj o algo.
W rzeczywistości jest to algorytm do wyjścia z labiryntu: trzymaj prawą rękę na ścianie i idź. To nie działa w przypadku pętli w labiryncie, po prostu się zapętlasz. Ale daje rozwiązanie twojego problemu.
źródło
To realizacja pomysłu Hashemi Emada . Działa dobrze, dopóki pozycja początkowa jest wybrana w taki sposób, że istnieje sposób, aby kroczyć w ciasnym okręgu przeciwnie do ruchu wskazówek zegara. W przypadku niektórych krawędzi, w szczególności wokół mapy, nie jest to możliwe. Nie mam pojęcia, jak wybrać dobre pozycje początkowe ani jak filtrować rozwiązania - ale może ktoś inny ma taką pozycję.
Przykład roboczy (zaczynający się od krawędzi (1204573687, 4555480822)):
Przykład, w którym to podejście nie działa (zaczynając od krawędzi (1286684278, 5818325197)):
Kod
źródło