Agrupando cadeias de linhas conectadas no PostGIS?

12

Eu tenho uma tabela de ruas que selecionei com base em um conjunto de atributos (digamos que seja speed_limit < 25). Existem grupos de ruas localmente contíguas; Gostaria de agrupar esses conjuntos de cadeias de linhas conectadas em GeometryCollections. Na imagem abaixo, haveria duas GeometryCollections: uma com as linhas vermelhas e outra com as linhas azuis.

insira a descrição da imagem aqui

Tentei executar algumas consultas "dissolver, desagregar" ao longo das linhas de:

SELECT (ST_Dump(st_union)).geom
FROM 
    (SELECT ST_Union(geom) FROM roads) sq

Com tudo o que tentei, acabei com um único recurso ( ST_Union) ou minha geometria original ( ST_Dumpde ST_Union).

Talvez seja possível fazer isso com algum tipo de WITH RECURSIVEmágica?

dbaston
fonte
Algo não parece certo com "(ST_Dump (ST_Union)) geom"
Martin F
Como ele não aliasou ST_Union (geom), o nome do novo geom herdou o nome da função para se tornar st_union. É por isso que parece um pouco engraçado
LR1234567

Respostas:

19

Então, por exemplo. Aqui está uma tabela simples com dois grupos de arestas conectados:

drop table lines;
create table lines ( id integer primary key, geom geometry(linestring) );
insert into lines (id, geom) values ( 1, 'LINESTRING(0 0, 0 1)');
insert into lines (id, geom) values ( 2, 'LINESTRING(0 1, 1 1)');
insert into lines (id, geom) values ( 3, 'LINESTRING(1 1, 1 2)');
insert into lines (id, geom) values ( 4, 'LINESTRING(1 2, 2 2)');
insert into lines (id, geom) values ( 11, 'LINESTRING(10 10, 10 11)');
insert into lines (id, geom) values ( 12, 'LINESTRING(10 11, 11 11)');
insert into lines (id, geom) values ( 13, 'LINESTRING(11 11, 11 12)');
insert into lines (id, geom) values ( 14, 'LINESTRING(11 12, 12 12)');
create index lines_gix on lines using gist(geom);

Agora, aqui está uma função recursiva que, dada a identificação de uma aresta, acumula todas as arestas que tocam:

CREATE OR REPLACE FUNCTION find_connected(integer) returns integer[] AS
$$
WITH RECURSIVE lines_r AS (
  SELECT ARRAY[id] AS idlist, geom, id
  FROM lines 
  WHERE id = $1
  UNION ALL
  SELECT array_append(lines_r.idlist, lines.id) AS idlist, 
         lines.geom AS geom, 
         lines.id AS id
  FROM lines, lines_r
  WHERE ST_Touches(lines.geom, lines_r.geom)
  AND NOT lines_r.idlist @> ARRAY[lines.id]
)
SELECT 
  array_agg(id) AS idlist
  FROM lines_r
$$ 
LANGUAGE 'sql';

Isso nos deixa precisando encontrar, após a acumulação de cada grupo, o id de uma borda que ainda não faz parte de um grupo. O que, tragicamente, requer uma segunda consulta recursiva.

WITH RECURSIVE groups_r AS (
  (SELECT find_connected(id) AS idlist, 
          find_connected(id) AS grouplist, 
          id FROM lines WHERE id = 1)
  UNION ALL
  (SELECT array_cat(groups_r.idlist,find_connected(lines.id)) AS idlist,
         find_connected(lines.id) AS grouplist,
         lines.id
  FROM lines, groups_r
  WHERE NOT idlist @> ARRAY[lines.id]
  LIMIT 1)
)
SELECT id, grouplist
FROM groups_r;   

Juntos, eles retornam um bom conjunto com o ID da semente e cada grupo que ela acumulou. Deixo como um exercício para o leitor transformar as matrizes de id novamente em uma consulta para criar geometria para mapeamento.

 id |   grouplist   
----+---------------
  1 | {1,2,3,4}
 11 | {11,12,13,14}
(2 rows)
Paul Ramsey
fonte
Eu acho que esse código pode ser mais simples, se o tipo de geometria suportar o hash no PostgreSQL (quando você escreve um RCTE mais simples que não envolve a acumulação de matrizes de IDs, você recebe um erro "Todos os tipos de dados da coluna devem ser laváveis"), então há um pequeno pedido de melhoria para mim.
Paul Ramsey
Essa é uma abordagem realmente impressionante. Estou percebendo alguns resultados estranhos ao aplicá-lo a um conjunto de testes maior; Vou ver se consigo reduzir o problema para um exemplo simples. 100 linhas: 85 clusters, maior cluster = 3, 0,03 s //// 200 linhas: 144 clusters, maior cluster = 9, 0,08 s //// 300 linhas: 180 clusters, maior cluster = 51, 0,16 s /// / 400 linhas: 188 clusters, maior cluster = 41, 0,27 s //// 500 linhas: 176 clusters, maior cluster = 112, 0,56 s //// 600 linhas: 143 clusters, maior cluster = 449, 1,0 s // // 650 linhas: 133 clusters, maior cluster = 7601, 6,8 s
dbaston
A adição deste para os dados de teste causará ID duplicados na grouplistmatriz: insert into lines (id, geom) values ( 15, 'LINESTRING(0 0, 10 10)');. A alteração array_agg(id)no retorno da função para array_agg(DISTINCT id)parece resolver o problema.
precisa saber é o seguinte
Esta é uma boa solução, então agora como podemos armazenar as geometrias em uma tabela para podermos ver as linhas conectadas?
Zakaria mouqcit 13/10/19
6

Aqui está uma abordagem que usa uma tabela temporária para agregar incrementalmente clusters. Eu realmente não me importo com a abordagem de tabela temporária, mas isso parece ter um desempenho muito bom à medida que o número de linhas aumenta (eu tenho 1,2 M linhas na minha entrada).

DO
$$
DECLARE
this_id bigint;
this_geom geometry;
cluster_id_match integer;

id_a bigint;
id_b bigint;

BEGIN
DROP TABLE IF EXISTS clusters;
CREATE TABLE clusters (cluster_id serial, ids bigint[], geom geometry);
CREATE INDEX ON clusters USING GIST(geom);

-- Iterate through linestrings, assigning each to a cluster (if there is an intersection)
-- or creating a new cluster (if there is not)
FOR this_id, this_geom IN SELECT id, geom FROM lines LOOP
  -- Look for an intersecting cluster.  (There may be more than one.)
  SELECT cluster_id FROM clusters WHERE ST_Intersects(this_geom, clusters.geom)
     LIMIT 1 INTO cluster_id_match;

  IF cluster_id_match IS NULL THEN
     -- Create a new cluster
     INSERT INTO clusters (ids, geom) VALUES (ARRAY[this_id], this_geom);
  ELSE
     -- Append line to existing cluster
     UPDATE clusters SET geom = ST_Union(this_geom, geom),
                          ids = array_prepend(this_id, ids)
      WHERE clusters.cluster_id = cluster_id_match;
  END IF;
END LOOP;

-- Iterate through the clusters, combining clusters that intersect each other
LOOP
    SELECT a.cluster_id, b.cluster_id FROM clusters a, clusters b 
     WHERE ST_Intersects(a.geom, b.geom)
       AND a.cluster_id < b.cluster_id
      INTO id_a, id_b;

    EXIT WHEN id_a IS NULL;
    -- Merge cluster A into cluster B
    UPDATE clusters a SET geom = ST_Union(a.geom, b.geom), ids = array_cat(a.ids, b.ids)
      FROM clusters b
     WHERE a.cluster_id = id_a AND b.cluster_id = id_b;

    -- Remove cluster B
    DELETE FROM clusters WHERE cluster_id = id_b;
END LOOP;
END;
$$ language plpgsql;
dbaston
fonte
funciona perfeitamente
zakaria mouqcit 13/10
@zakariamouqcit Fico feliz que isso funcionou para você! Eu escrevi esta resposta antes de escrever a ST_ClusterIntersectingfunção no PostGIS. Se seus dados forem pequenos o suficiente para caber na memória, sugiro que verifique se há uma solução com melhor desempenho.
Dbaston 13/10/19
procurar por esta pergunta me trouxe aqui. Tentei o iterativo e o st_clusterintersecting, mas considerou o st_clusterDBScan o mais adequado. Caso alguém seja trazido aqui também. postgis.net/docs/manual-dev/ST_ClusterDBSCAN.html
D_C
Concordado, ST_ClusterDBSCAN é quase sempre o melhor caminho a seguir para o PostGIS 2.3+
dbaston