Jak obliczyć najmniejszą sieć, która łączy wszystkie punkty za pomocą PostGIS?

Mam zestaw skryptów Postgis, który generuje dwie tabele - jedną z zestawu punktów, a drugą zestaw otaczających je dróg. Wszystkie dane są w tej samej projekcji i oba wyjścia są przechowywane w tabelach postgres 9.2 z postgis 2.1

Utworzono topologię sieci drogowej, a tabela punktów zawiera kolumnę zawierającą najbliższy odcinek drogi.

Chciałbym wtedy wygenerować podzbiór sieci drogowej, który reprezentuje najmniejszą sieć, która łączy wszystkie punkty za pomocą czegoś w rodzaju drzewa rozpinającego minimum. Sieć dróg nie jest kierowana, a koszty to po prostu długość trasy.

Mogę to zrobić w QGIS / Grass przy użyciu rodziny modułów v.net, ale idealnie chciałbym również zachować ten ostatni krok w SQL.

Spojrzałem na nową funkcję postspis apspWarshall, ale nie wiem, jak można ją zachęcić do skupienia energii na łączeniu punktów, a nie całej sieci.

Jest to krótki skrypt, który przygotowałem, próbując stworzyć platformę, aby rozwiązać ten problem, ale nie widzę, gdzie można skupić funkcję na początku z podzbiorem krawędzi.

SELECT seq, id1 AS node, id2 AS edge, cost, the_geom
FROM   pgr_apspWarshall('SELECT gid AS id, 
                                source, 
                                target, 
                                st_length(the_geom) AS cost 
                         FROM   road_network
                        ',
                        false, false
                       ) AS tree
JOIN   road_network As roads
ON     tree.id2 = roads.gid

W przypadku problemów z najkrótszą ścieżką dla pojedynczej ścieżki funkcja prosi o początek i koniec, ale najwyraźniej nie we wszystkich punktach Podobnie w Grass v.net.spanningtree i v.net.steiner oczekują zestawu punktów i linii jako połączonej sieci do pracy.

Czy ktoś ma jakieś sugestie, jak to zrobić w PostGIS?

Ta odpowiedź nie jest kompletna ani przetestowana, ale spróbuj czegoś takiego:

zgodnie z pytaniami / 39210 :

with index_query as (
SELECT
        ,ST_Distance(i.geom, i.b_geom) AS dist
        ,ST_MakeLine(i.geom, i.b_geom) as geom
FROM(
SELECT
        ,a.geom
        ,b.geom AS b_geom
        ,rank() OVER (PARTITION BY a.id ORDER BY ST_Distance(a.centroid_geom, b.the_geom)) AS pos
FROM points a, points b 
WHERE a.id <> b.id) i
WHERE pos = 1
) select ST_Union(geom) from index_query;

myślę, że to nie jest bardzo wydajne.

@Adrian, naprawdę nie jestem zaznajomiony z wynikami opracowywania, jednak dokumentacja jest bardzo szczegółowa. Moja odpowiedź opiera się na funkcji dwuetapowej, która będzie bardzo użyteczna w SQL, ale [prawdopodobnie] da wyniki. To [niesprawdzone] rozwiązanie NIE zoptymalizuje, który jest najlepszy punkt początkowy, ale zredukuje całą sieć tras do samych krawędzi, które łączą wszystkie przystanki, a następnie trasy skutecznie do wszystkich przystanków.

Krok 1 (podselekcja podzbioru sieci drogowej, który łączy wszystkie przystanki) Korzysta z funkcji routingu do wielu miejsc docelowych (ścieżka K Dijkstr), aby zwrócić zbiór ścieżek, które (gdy koszt <> -1) faktycznie łączą wszystkie przystanki.

SELECT id1 as path, st_astext(st_linemerge(st_union(b.the_geom))) as the_geom
FROM pgr_kdijkstraPath(
’SELECT id, source, target, cost FROM edge_table’,
min(all_your_stop_ids), [array_of_all_your_stop_ids], false, false
) a,
edge_table b
WHERE a.id3=b.id
GROUP by id1
ORDER by id1

Problem, który mam tutaj, to składnia do zestawiania tablicy z tablicy zatrzymania, ponieważ tak naprawdę nie została opisana w pytaniu. Załóżmy jednak, że składnia SQL może złożyć tę tablicę i że minimalne id stop powinno być punktem początkowym dla wszystkich ścieżek K do pozostałych przystanków docelowych.

Krok 2 (ostateczny wybór minimalnych ścieżek w oparciu o powyższe podzbiory ścieżek sieci drogowej, które łączą wszystkie przystanki) Zasadniczo od tego zacząłeś, ale proponuję, abyś dołączył do sieci dróg równorzędnych do początkowego wyniku na id1 (ścieżka) tak, że tylko końcowy odcinek dróg jest używany w końcowym trasowaniu Field-Warshal :

SELECT seq, id1 AS node, id2 AS edge, cost, the_geom
FROM   pgr_apspWarshall('SELECT R.gid AS id, 
                                R.source, 
                                R.target, 
                                st_length(R.the_geom) AS cost 
             FROM   road_network AS R JOIN
                   (SELECT id1 as path
                     FROM pgr_kdijkstraPath(
                            ’SELECT id, source, target, cost FROM edge_table’,
                            min(all_your_stop_ids), 
                            [array_of_all_your_stop_ids], false, false
                           ) a,
                     edge_table b
                    WHERE a.id3=b.id
                    GROUP by id1
                    ORDER by id1
                        ',
                        false, false
                  ) AS  Just_K_Paths
         on R.id1 = just_K_paths.id1',       /* this join reduces R down to K paths */
         false, false
        ) AS tree
  JOIN   road_network As roads
  ON     tree.id2 = roads.gid

Podsumowując ... wewnętrzne zapytanie routingu k_dijkstra_path zmniejsza całkowitą sieć drogową tylko do ścieżek łączących wszystkie Twoje przystanki, wtedy zewnętrzne routing fField_Warshal używa tylko tych identyfikatorów krawędzi do rozwiązania zapytania o optymalizację ścieżki .... może.