Pontos PostGIS mais próximos com ST_Distance, kNN

23

Eu preciso obter em cada elemento de uma tabela o ponto mais próximo de outra tabela. A primeira tabela contém sinais de trânsito e a segunda, os halls de entrada da cidade. O problema é que não posso usar a função ST_ClosestPoint e tenho que usar a função ST_Distance e obter o registro min (ST_distance), mas estou bastante paralisado ao criar a consulta.

CREATE TABLE traffic_signs
(
  id numeric(8,0) ),
  "GEOMETRY" geometry,
  CONSTRAINT traffic_signs_pkey PRIMARY KEY (id),
  CONSTRAINT traffic_signs_id_key UNIQUE (id)
)
WITH (
  OIDS=TRUE
);

CREATE TABLE entrance_halls
(
  id numeric(8,0) ),
  "GEOMETRY" geometry,
  CONSTRAINT entrance_halls_pkey PRIMARY KEY (id),
  CONSTRAINT entrance_halls_id_key UNIQUE (id)
)
WITH (
  OIDS=TRUE
);

Preciso obter o ID do entrnce_hall mais próximo de cada traffic_sign.

Minha consulta até agora:

SELECT senal.id,port.id,ST_Distance(port."GEOMETRY",senal."GEOMETRY")  as dist
    FROM traffic_signs As senal, entrance_halls As port   
    ORDER BY senal.id,port.id,ST_Distance(port."GEOMETRY",senal."GEOMETRY")

Com isso, estou obtendo a distância de todo sinal de tráfego para cada entrada. Mas como posso obter apenas a distância mínima?

Saudações,

Egidi
fonte
Qual versão do PostgreSQL?
Jakub Kania 23/02

Respostas:

41

Você está quase lá. Há um pequeno truque que é usar o operador distinto do Postgres , que retornará a primeira correspondência de cada combinação - conforme você solicita por ST_Distance, efetivamente ele retornará o ponto mais próximo de cada senal a cada porta.

SELECT 
   DISTINCT ON (senal.id) senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY")  as dist
FROM traffic_signs As senal, entrance_halls As port   
ORDER BY senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY");

Se você sabe que a distância mínima em cada caso não passa de uma quantidade x (e você tem um índice espacial em suas tabelas), você pode acelerar isso colocando um WHERE ST_DWithin(port."GEOMETRY", senal."GEOMETRY", distance), por exemplo, se todas as distâncias mínimas forem conhecidas como não mais que 10 km, então:

SELECT 
   DISTINCT ON (senal.id) senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY")  as dist
FROM traffic_signs As senal, entrance_halls As port  
WHERE ST_DWithin(port."GEOMETRY", senal."GEOMETRY", 10000) 
ORDER BY senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY");

Obviamente, isso precisa ser usado com cautela, como se a distância mínima fosse maior, você simplesmente não terá linha para essa combinação de senal e porto.

Nota: A ordem por ordem deve corresponder ao distinto no pedido, o que faz sentido, pois o distinto é pegar o primeiro grupo distinto com base em alguns pedidos.

Supõe-se que você tenha um índice espacial em ambas as tabelas.

EDIT 1 . Existe outra opção, que é usar os operadores <-> e <#> do Postgres (cálculos de distância do ponto central e da caixa delimitadora, respectivamente) que fazem um uso mais eficiente do índice espacial e não exigem o hack ST_DWithin para evitar n ^ 2 comparações. Há um bom artigo de blog explicando como eles funcionam. O aspecto geral a ser observado é que esses dois operadores trabalham na cláusula ORDER BY.

SELECT senal.id, 
  (SELECT port.id 
   FROM entrance_halls as port 
   ORDER BY senal.geom <#> port.geom LIMIT 1)
FROM  traffic_signs as senal;

EDIT 2 . Como essa pergunta recebeu muita atenção e o k-vizinhos mais próximos (kNN) geralmente é um problema difícil (em termos de tempo de execução algorítmico) no GIS, parece valer a pena expandir um pouco o escopo original dessa questão.

A maneira padrão de encontrar os x vizinhos mais próximos de um objeto é usar um LATERAL JOIN (conceitualmente semelhante a um para cada loop). Tomando emprestado descaradamente a resposta do dbaston , você faria algo como:

SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
 FROM traffic_signs
CROSS JOIN LATERAL 
  (SELECT
      id, 
      ST_Distance(ports.geom, signs.geom) as dist
      FROM ports
      ORDER BY signs.geom <-> ports.geom
     LIMIT 1
   ) AS closest_port

Portanto, se você deseja encontrar as 10 portas mais próximas, ordenadas por distância, basta alterar a cláusula LIMIT na subconsulta lateral. Isso é muito mais difícil sem LATERAL JOINS e envolve o uso da lógica do tipo ARRAY. Embora essa abordagem funcione bem, ela pode ser acelerada enormemente se você souber que precisa apenas procurar a uma determinada distância. Nesse caso, você pode usar ST_DWithin (signs.geom, ports.geom, 1000) na subconsulta, que devido à maneira como a indexação funciona com o operador <-> - uma das geometrias deve ser uma constante, e não uma referência de coluna - pode ser muito mais rápido. Assim, por exemplo, para obter as 3 portas mais próximas, em 10 km, você pode escrever algo como o seguinte.

 SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
 FROM traffic_signs
CROSS JOIN LATERAL 
  (SELECT
      id, 
      ST_Distance(ports.geom, signs.geom) as dist
      FROM ports
      WHERE ST_DWithin(ports.geom, signs.geom, 10000)
      ORDER BY ST_Distance(ports.geom, signs.geom)
     LIMIT 3
   ) AS closest_port;

Como sempre, o uso varia de acordo com a distribuição e as consultas de dados, portanto EXPLAIN é seu melhor amigo.

Por fim, existe uma pequena pegadinha, se você usar ESQUERDA em vez de CROSS JOIN LATERAL, precisará adicionar ON TRUE após o alias das consultas laterais, por exemplo,

SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
 FROM traffic_signs
LEFT JOIN LATERAL 
  (SELECT
      id, 
      ST_Distance(ports.geom, signs.geom) as dist
      FROM ports          
      ORDER BY signs.geom <-> ports.geom
      LIMIT 1
   ) AS closest_port
   ON TRUE;
John Powell
fonte
Note-se que isso não terá um bom desempenho com grandes quantidades de dados.
Jakub Kania 23/02
@JakubKania. Depende se você pode usar ST_DWithin ou não. Mas, sim, ponto de vista. Infelizmente, o operador Order by <-> / <#> exige que uma das geometrias seja uma constante, não?
John Powell
@ JohnPowellakaBarça alguma chance de você saber onde esse post do blog mora hoje em dia? - ou, uma explicação semelhante dos operadores <-> e <#>? Obrigado!!
precisa saber é o seguinte
@DPSSpatial, isso é chato. Não, mas há isso e isso que falam um pouco sobre essa abordagem. O segundo, usando junções laterais também, o que é outro aprimoramento interessante.
31419 John Powell
@DPSSpatial. É um pouco escorregadio esse material de junção <->, <#> e lateral. Eu fiz isso com conjuntos de dados muito grandes e o desempenho foi horrível, sem usar ST_DWithin, o que tudo isso deve evitar. Por fim, knn é um problema complicado, portanto, o uso pode variar. Boa sorte :-)
John Powell
13

Isso pode ser feito com um LATERAL JOINno PostgreSQL 9.3+:

SELECT
  signs.id,
  closest_port.id,
  closest_port.dist
FROM traffic_signs
CROSS JOIN LATERAL 
  (SELECT
     id, 
     ST_Distance(ports.geom, signs.geom) as dist
     FROM ports
     ORDER BY signs.geom <-> ports.geom
   LIMIT 1) AS closest_port
dbaston
fonte
10

A abordagem com junção cruzada não usa índices e requer muita memória. Então você basicamente tem duas opções. Antes da versão 9.3, você usaria uma subconsulta correlacionada. 9.3+ você pode usar a LATERAL JOIN.

KNN GIST com um toque lateral Em breve, em um banco de dados perto de você

(consultas exatas a seguir em breve)

Jakub Kania
fonte
1
Uso legal de uma junção lateral. Não tinha visto isso antes neste contexto.
John Powell
1
@ JohnBarça É um dos melhores contextos que eu já vi. Eu também suspeito que seria útil quando você realmente precisar usar ST_DISTANCE()para encontrar o polígono mais próximo e a junção cruzada estiver causando falta de memória no servidor. A consulta de polígono mais próxima ainda é AFAIK não resolvida.
Jakub Kania 23/02
2

@John Barça

ORDER BY está errado!

ORDER BY senal.id, port.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY");

Direita

senal.id, ST_Distance(port."GEOMETRY", senal."GEOMETRY"),port.id;

caso contrário, ele não retornará o mais próximo, apenas o que possui o pequeno ID de porta

esticar
fonte
1
O correto parece com este (eu usei pontos e linhas):SELECT DISTINCT ON (points.id) points.id, lines.id, ST_Distance(lines.geom, points.geom) as dist FROM development.passed_entries As points, development."de_muc_rawSections_cleaned" As lines ORDER BY points.id, ST_Distance(lines.geom, points.geom),lines.id;
blackgis 11/01
1
OK, eu te pego agora. Na verdade, é provavelmente melhor usar a abordagem LATERAL JOIN, como na resposta do @ dbaston, que deixa claro que coisa está sendo comparada com a outra em termos de proximidade. Não uso mais a abordagem acima.
John Powell