Como calcular a menor rede que conecta todos os pontos usando o PostGIS?

Eu tenho um conjunto de scripts postgis que gera duas tabelas - uma de um conjunto de pontos e a segunda um conjunto de estradas que as cercam. Todos os dados estão na mesma projeção e as duas saídas são armazenadas nas tabelas do postgres 9.2 com o postgis 2.1

A topologia de pgrouting da rede de estradas foi criada e a tabela de pontos possui uma coluna contendo o segmento de estrada mais próximo.

Gostaria, então, de gerar um subconjunto da rede rodoviária, que representa a menor rede que conecta todos os pontos usando algo como uma árvore de abrangência mínima. A rede rodoviária não é direcionada e os custos são simplesmente o comprimento da rota.

Posso fazer isso no QGIS / Grass usando a família de módulos v.net, mas, idealmente, também gostaria de manter esta etapa final no SQL.

Eu olhei para a nova função apspWarshall postgis, mas não sei como pode ser incentivado a concentrar sua energia na conexão dos pontos e não de toda a rede.

Este é o script curto que reuni na tentativa de criar uma estrutura para resolver isso, mas não vejo onde é possível focar a função para começar com um subconjunto das arestas.

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

Nos problemas de caminho mais curto de caminho único, a função solicita o início e o fim, mas aparentemente não nos problemas de todos os pontos. Igualmente no Grass, o v.net.spanningtree e o v.net.steiner esperam um conjunto de pontos e linhas como uma rede combinada para trabalhar.

Alguém tem alguma sugestão de como fazer isso no PostGIS?

Esta resposta não está completa ou testada, mas tente algo como isto:

de acordo com as perguntas / 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;

Eu acho que isso não é muito eficiente.

@ Adrian, eu realmente não estou familiarizado com os resultados do pgrouting, no entanto, a documentação é muito detalhada. Minha resposta é baseada em uma função de duas etapas, que será muito ineficiente em SQL, mas [provavelmente] produzirá os resultados. Essa solução [não testada] NÃO otimizará o melhor ponto de partida, mas reduzirá toda a rede de rotas apenas às arestas que conectam todas as paradas e, em seguida, encaminha com eficiência a todas as paradas.

Etapa 1 (sub-seleção de um subconjunto de rede rodoviária que conecta todas as paradas) Isso usa a função de roteamento de vários destinos (caminho K Dijkstr) para retornar uma coleção de caminhos que (quando o custo <> -1) realmente conectam todos os seus pára.

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

O problema que tenho aqui é a sintaxe para montar uma matriz da sua tabela de parada, pois ela não foi realmente descrita na pergunta. No entanto, vamos supor que a sintaxe SQL possa montar essa matriz e que a parada mínima de id seja o ponto de partida de todos os caminhos K para o destino restante.

Etapa 2 (seleção final dos caminhos mínimos com base nos caminhos da rede rodoviária do subconjunto acima, que conectam todas as paradas) Isso é basicamente o que você começou, mas proponho que você junte sua rede rodoviária ao resultado inicial no id1 (caminho) para que apenas o subconjunto de estradas seja usado no roteamento final do campo de guerra :

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

Portanto, em resumo ... a consulta de roteamento k_dijkstra_path interna reduz a rede rodoviária total apenas aos caminhos que conectam todas as suas paradas, então o roteamento fField_Warshal externo usa apenas esses IDs de borda para resolver a consulta de otimização de caminho .... talvez.