Jak uprościć routowalną sieć?

24

Mam wykres sieci, który muszę uprościć w celu zmniejszenia liczby krawędzi . Pomysł polegałby na połączeniu węzłów znajdujących się blisko siebie i usunięciu łączących krótkich krawędzi.

Jak można to osiągnąć w PostGIS lub GRASS? Czy są jakieś lepsze sposoby automatycznego uproszczenia takiej sieci?

Próbowałem już funkcji ST_SnapToGrid, ale nie jestem zadowolony z wyników (szary = oryginalny, czarny = przyciągnięty):

wprowadź opis zdjęcia tutaj

podmrok
źródło
1
Czy robisz to w celu uproszczenia analizy opartej na sieci lub do celów wyświetlania? Jeśli to pierwsze, jakie analizy zostaną wykonane?
whuber
Jest przeznaczony do analizy najkrótszej ścieżki.
podmroku
2
Ponieważ wiele algorytmów najkrótszej ścieżki to O (E + V), być może nawet nie potrzebujesz tego uproszczenia? Z drugiej strony, w przypadku takich analiz często można wprowadzić znacznie bardziej agresywne uproszczenia. Na przykład ten zestaw trzech równoległych segmentów i ich sąsiadujących segmentów po lewej stronie (wyglądających jak H-in-a-box) można zastąpić trójkątem, jeśli w tych segmentach nie ma początku ani celu. Wspominam o tym, ponieważ jestem pewien, że istnieje kod (nie GIS) do takich operacji na (abstrakcyjnych) grafach.
whuber
Czy chcesz zachować geometrię krawędzi (np. Krzywych), czy wystarczy utrzymanie topologii + węzła XY? Czy musisz także upewnić się, że węzły w różnych Z (np. Estakady) nie łączą się ze sobą?
AnserGIS
Topologia jest kluczowa. Geometria może się nieco zmienić. Zamówienie Z musi pozostać nienaruszone.
podmrok

Odpowiedzi:

7

Najbliższe, do jakiego do tej pory doszedłem, to:

v.clean input=roads output=snap5rmline tool=snap,rmline thresh=5 

Zatrzaskuje drogi z tolerancją 5 metrów i usuwa wszystkie linie zerowej długości. Nie jest to optymalne rozwiązanie, ponieważ wydaje się przyciągać raczej losowo do niektórych wierzchołków.

wprowadź opis zdjęcia tutaj

podmrok
źródło
Rzeczywiście, wynik może nie jest dokładny, ale to użycie v.clean jest interesujące, dzięki za udostępnienie
simo
Czy to zdjęcie powstało w trawie?
NetConstructor.com,
Zdjęcie pokazuje wyniki GRASS v.clean wizualizowane w QGIS.
podmrok
Masz problemy z utrzymywaniem „dziwnych skrzyżowań” lub dróg wydzielonych?
dassouki
Co powiesz na przetwarzanie ST_SnapToGrid po v.clean?
kttii
5

Czy próbowałeś już GRASS v.generalize ?

v.generalizepozwala wybrać algorytm generalizacji z atrybutem metody . Istnieje kilka: douglas, douglas_reduction, lang, redukcja, reumann, boyle, przesuwne_averaging, ważenie odległości, chaiken, pustelnik, węże, sieć, przemieszczenie .

I dodatkowe parametry jak threshold, degree_thresh, angle_thresh(w zależności od wybranego algorytmu) może pomóc uzyskać dokładny wynik.

Oto samouczek .

simo
źródło
Dziękuję za link. Próbuję, chociaż tak naprawdę nie rozumiem, która kombinacja wartości metody i wartości progowych da wynik, którego szukam.
podmroku
Naprawdę nie mogę znaleźć metody v.generalize, która zrobi to, co chcę.
podmroku
2
Szkoda, polecenie jest bogate w wiele algorytmów, ale jak powiedziano wcześniej, konfiguracja zapewniająca oczekiwany wynik jest prawdopodobnie dość skomplikowana. Może tutaj jest guru algorytów uogólnień? Czy próbowałeś także metody węży ?
simo
Nie jestem algo-guru tutaj, ale uważam, że metoda węży jest najlepsza dla niektórych z moich v.genralise, które zrobiłem w przeszłości.
obsadzony
1
Dla przypomnienia, parametry zostały uproszczone na dzień dzisiejszy w GRASS SVN. Stać się częścią GRASS 6.4.2.
markusN
4

Nie zrobiłem tego, ale myślę, że mogę zasugerować kierunek.

  1. Utwórz topologię za pomocą PostGIS dla swojego wykresu.
  2. Znajdź wszystkie węzły z tylko dwiema krawędziami.
  3. Wylecz krawędzie.

ST_ModEdgeHeal połączy jedną krawędź w drugą. ST_NewEdgeHeal zastąpi oba nowymi krawędziami.

Podręcznik topologii PostGIS

Sean
źródło
Dzięki @Sean. Czy to zrobi coś innego niż połączenie dwóch krawędzi? Masz pomysł na temat usuwania krótkich krawędzi i przyciągania ich węzłów do siebie?
podmroku
@Underdark, nie widzę nic prostego. Możesz zrobić to wszystko w PL / SQL, ale to prawdopodobnie nie pomaga. Czy możesz najpierw uruchomić ST_SnapToGrid?
Sean
1

@ w mroku, widzę, że napisałeś narzędzie do zagęszczania linii w Sextante. Dlatego sugeruję następujący algorytm, aby uniknąć „losowego” przyciągania jednego z twoich punktów.

Wybierz segmenty linii, których chcesz się pozbyć na podstawie ich długości.

Dla każdego z tych segmentów utwórz punkt w punkcie środkowym

Usuń mały segment

Teraz możesz używać ST_Snap w PostGIS (patrz przykład tutaj )

EDYCJA: pamiętaj, że w twoim przypadku możesz najpierw użyć v.net , aby usunąć pseudo-węzły (węzeł łączący tylko dwie linie)

radouxju
źródło
Wyjaśnij, w jaki sposób v.net może być użyty do usunięcia pseudo-węzłów. Dzięki
osmjit
0

Przekazywanie, w jaki sposób Michaël Michaud przeanalizował to na liście programistów OpenJUMP:

> Interesting question. There has been so much research works about
> generalization that it is surely not a simple task. I have tested the
> following approach with mitigated results :
> - make the layer planar with the noder plugin
> - detect small cycles with the graph plugin
> - merge adjacent cycles
> - create a point inside each cycles surface
> - remove network segments along these cycles (query + DE-9IM)
> - detect roads touching the cycles
> - project the center points of cycles to the road endpoints ==> replace small roundabout by simple nodes
> 
> Possible improvements (probably need a dedicated plugin)
> - make it work on non planar graph (or just remove bridges/tunnels from the graph)
> - replace small edges between two nodes with degree 3+ by a single node,    not only small cycles
> - process iteratively starting with smallest edges/cycles
użytkownik30184
źródło
Dziękujemy za opublikowanie tej odpowiedzi. Jestem trochę zdezorientowany, dlaczego zmusisz wykres do płaskiej. W końcu sieci uliczne nie są wykresami planarnymi (mosty, tunele).
podmrok
Tylko dlatego, że Michaël wykonał szybki test przy użyciu istniejących narzędzi graficznych, które napisał dla OpenJUMP i nie obsługują one obecnie wykresów niepłaskich. Pomiń pierwszy krok, jeśli QGIS i GRASS mają podobne narzędzia, które obsługują wykresy niepłaskie.
user30184
Myślę, że to jest właściwe podejście - rozdziel sieć na płaskie wykresy. Na każdym wykresie planarnym problem jest prostszy - na przykład można zastosować powyższe podejście lub po prostu triangulować i odchwaszczać TIN krótkich krawędzi drogi. Następnie ponownie wyodrębnij krawędzie drogi i połącz warstwy razem.
AnserGIS