PgRouting - Jak przycinać linki po osiągnięciu maksymalnych kosztów?

13

Mam plik kształtu polilinii reprezentujący sieć dróg i drugi plik kształtu zawierający punkty. Chciałbym użyć PostGIS (prawdopodobnie PgRouting) do identyfikacji podsieci lub obszarów usług promieniujących z tych punktów.

Zasadniczo mam nadzieję zadać pytanie: „Zaczynając od punktu X, jak daleko mogę iść w danym kierunku, biorąc pod uwagę całkowity budżet podróży 1 km, zgodnie z siecią dróg?” Rezultatem byłby zestaw przyciętych polilin reprezentujących całkowity zakres możliwości podróży, przy budżecie na 1 km.

Dla porównania, ta analiza GRASS wydaje się być dokładnie tym, co chcę zrobić (poza tym, że chcę to zrobić w PostGIS): http://www.gdf-hannover.de/lit_html/grass60_v1.2_en/node57.html#sec: optalloc

Ten następny przykład wydaje się być prawie tym, co chcę zrobić, z tym wyjątkiem, że wydaje się odpowiadać na pytanie „do jakich węzłów mogę się udać, biorąc pod uwagę budżet podróży w odległości X?” http://underdark.wordpress.com/2011/02/12/drive-time-isochrones/

Druga nie jest do końca odpowiedzią, której szukam, ponieważ chcę polilinie przycięte na moją odległość podróży - nie obchodzi mnie, czy dotrę do węzła.

Piotr
źródło
Jedną z opcji, która przychodzi mi do głowy, jest jakoś podzielić moje polilinie na wiele punktów. To przybliża mnie do właściwej odpowiedzi, ale wydaje się dość zuchwałe i wciąż nie do końca mnie tam prowadzi.
Peter

Odpowiedzi:

2

Jedną z moich myśli było: 1) uruchomienie procedury Driving_distance i 2) użycie procedury „points_as_polygon” z pgRouting (która wywołuje funkcję alphashape) w celu wygenerowania najmniejszego wielokąta (-ów) przy danych odległościach kosztów w oparciu o punkty rutyny Driving_distance zwroty. Następnie możesz wybrać wszystkie ulice w obrębie wielokątów, co dałoby ogólny pomysł na podróż.

Jeśli nie śledziłeś dyskusji na liście użytkowników pgRouting , ostatnio omawiali więcej opcji (wątki z maja i czerwca 2011 r.).

RyanKDalton
źródło
1
Ciekawe dyskusje na liście użytkowników. Szkoda, że ​​funkcja Driving_distance jest błędna.
podmrok
1

Ponieważ jest to tak naprawdę problem z grafem, potrzebna jest łączność / topologia + informacje o kosztach. W przypadku pg_routing jest to tabela wysyłana do algorytmów najkrótszej ścieżki. W tym artykule znajdują się informacje o tym, jak je zbudować (zakładam, że już je masz). Niestety nie mogę podać dokładnej funkcji w pg_routing, która to robi, ale napisanie jednej powinno być wykonalne. Mogę ci jednak powiedzieć, że jeśli ciągle powtarzasz najkrótszą ścieżkę, to ciągle robisz algorytm poniżej i niszczy wynik - w ogóle nieefektywny.

Twoje rozwiązanie staje się wtedy kroczące, dodając je do „listy kroczonej” i obliczając koszty, aż do wyczerpania budżetu (odległości). Jeśli budżet jest akceptowalny (tzn. Budżet nie został przekroczony), dodajesz również geometrię do „akceptowalnego worka geometrii listy”. Każdą krawędź trzeba przetworzyć tylko raz. W przypadku ostatniego ostrza (w przypadku przekroczenia budżetu) musisz uzyskać długość i interpolować dokładną odległość, którą chcesz pokonać , a następnie dodać wynik do „listy dopuszczalnych”. Twój wynik to połączenie tej torby z geometrią.

Ragi Yaser Burhum
źródło
1
W ostatnim kroku jest subtelność: do niektórych krawędzi można dotrzeć z dowolnego z jego punktów końcowych. Może to spowodować włączenie części obu końców lub nawet całej krawędzi, nawet jeśli przemieszczenie całej krawędzi z jednego z punktów końcowych przekroczyłoby limit budżetu. Np. Rozważ przemieszczenie od punktu a wzdłuż niekierowanego wykresu z krawędziami o jednostkowej długości {(a, b), (a, c), (b, c)} i budżetem 1,6. Możesz osiągnąć wartość b lub c kosztem 1, a pozostało 0,6 do wydania. Dzięki temu każdy punkt wzdłuż krawędzi (b, c) jest dostępny.
whuber
Masz rację :) +1
Ragi Yaser Burhum
1

„Począwszy od punktu X, jak daleko mogę iść w danym kierunku, biorąc pod uwagę całkowity budżet podróży 1 km, zgodnie z siecią dróg?”

Ponieważ musisz wziąć pod uwagę tylko niewielki region (promień 1 km maksymalnie), prawdopodobnie możesz uciec od podziału łączy na wiele małych kawałków (w zależności od dokładności, którą chcesz osiągnąć) i utworzenia niezbędnych węzłów. Powstałe sieci „wysokiej rozdzielczości” powinny być nadal możliwe do zarządzania.

podmrok
źródło