Otimizando um cálculo de vizinho mais próximo usando o PostGIS

13

Estou usando o PostGIS para calcular os vizinhos mais próximos dos polígonos. O que eu quero calcular é a distância mínima de cada polígono até o polígono mais próximo.

Até agora, recebi grande ajuda da resposta de Mike Toews (que cito com uma pequena alteração) aqui:

SELECT 
  a.hgt AS a_hgt,
  b.hgt AS b_hgt,
  ST_Distance(a.the_geom, b.the_geom) AS distance_between_a_and_b
FROM 
  public."TestArea" AS a, public."TestArea" AS b
WHERE
  a.hgt !=  b.hgt AND ST_Distance(a.the_geom, b.the_geom) < 400

Então eu calculei o mínimo:

SELECT a_hgt, MIN(distance_between_a_and_b)
FROM public."lon_TestArea"
GROUP BY a_hgt

No entanto, meu desafio é calcular isso para um grande número de polígonos (1.000.000). Como o cálculo acima compara cada polígono a qualquer outro polígono, perguntei-me como poderia melhorar o cálculo para não precisar executar 10 ^ 12 cálculos.

Um pensamento que eu tinha era o buffer de cada polígono e, em seguida, calcular os vizinhos mais próximos de todos os valores dentro do buffer desse polígono e registrar o mínimo. Não tenho certeza se essa é a melhor abordagem ou se existe uma função no PostGIS que eu deveria estar usando.


EDIT: Usando uma das sugestões de Nicklas, estou experimentando ST_Dwithin():

CREATE TABLE mytable_withinRange AS SELECT 
  a.hgt AS a_hgt,
  b.hgt AS b_hgt,
  ST_DWithin(a.the_geom, b.the_geom, 400)
FROM 
  public."lon_TestArea" AS a, public."lon_TestArea" AS b

insira a descrição da imagem aqui

Isso retorna uma tabela do ID de cada polígono e se está dentro de uma certa distância ou não. É possível construir uma IF/ELSEinstrução de tipo usando SQL? (Li sobre o uso da CASEcondição) Ou devo tentar associar a tabela que produzo à tabela original e executar a consulta novamente usando ST_Distance?

djq
fonte
dê uma olhada no segundo exemplo no link boston gis na minha resposta. você deve usar st_dwithin na parte where da consulta.
Nicklas Avén

Respostas:

7

Há uma grande seção "Vizinho mais próximo" na página BostonGIS .


EDITAR:

E se

CREATE TABLE mytable_withinRange AS SELECT 
 a.hgt AS a_hgt,
 b.hgt AS b_hgt
FROM 
 public."lon_TestArea" AS a, public."lon_TestArea" AS b
WHERE 
 ST_DWithin(a.the_geom, b.the_geom, 400)

Em relação à declaração CASE :

SELECT a,
   CASE WHEN a=1 THEN 'one'
        WHEN a=2 THEN 'two'
        ELSE 'other'
   END
FROM test;
underdark
fonte
Você sabe se a linha WHERE ST_DWithin(a.the_geom, b.the_geom, 400)impedirá que distâncias maiores 400sejam calculadas ou apenas registradas? Além disso, uma declaração de caso pode ser usada para cálculos numéricos? por exemplo:CASE WHEN ST_DWithin(a.the_geom, b.the_geom, 400) == TRUE THEN ST_DWithin(a.the_geom, b.the_geom)
djq 10/07/11
1
@celenius Se a distância for superior a 400 m, nada na parte selecionada será calculado. Eu não entendo por que você quer colocar o caso na mistura.
Nicklas Avén
@ Nicklas ok - eu entendo. Eu pensei que poderia significar que apenas distâncias inferiores a 400 estavam armazenadas; isso torna muito mais fácil do que eu pensava. Obrigado!
DJQ
3

Hallo

Há algumas coisas que consideram fazer as coisas se moverem mais rapidamente e outras que podem ser possíveis no futuro.

Primeiro , você mencionou que está pensando em usar um buffer para encontrar polígonos em um intervalo mínimo para evitar o cálculo de todas as combinações.

Conforme discutido em outro link de Boston gis, a maneira correta de fazer isso no PostGIS é usando ST_Dwithin . ST_Dwithin usa o índice para encontrar os vizinhos em um determinado intervalo.

Depende do conjunto de dados, é claro, se é suficiente usar apenas um valor fixo para st_DWithin para todos os polígonos ou se você precisa fazer algo como o underdark e wildintellect estão discutindo.

Uma segunda coisa é usar o PostGIS 1.5+ aqui. Isso ocorre porque os cálculos de polígono para polígono são muito mais rápidos desde 1,5 se as caixas delimitadoras não se cruzam. Você pode ler mais sobre isso aqui. .

A terceira coisa a mencionar é o futuro.

No PostgreSQL 9.1, haverá algo chamado knn-gist. Esse é um índice que não pode apenas responder sim ou não, mas também retornar o resultado ordenado diretamente do índice. Você pode ler sobre isso aqui .

Mas ainda haverá muito trabalho a ser feito no lado do PostGIS antes que o knn gist ajude em coisas como essa. Há um ingresso para isso aqui.

Saudações

Nicklas

Nicklas Avén
fonte
Obrigado pelas sugestões Nicklas; como achei difícil colocar o pgAdmin / PostGIS em funcionamento, acho que evitarei usar o 1.5 no momento. Parece que ST_Dwithin () é uma maneira de resolver isso.
8111 djq
2
A instalação do 1.5 não afetará a relação entre o postgresql e o pgadmin. você pode ter mais de uma versão do postgis no servidor de banco de dados e depois carregar uma delas no banco de dados. para que você possa ter um banco de dados 1.4 e um 1.5 e o mesmo servidor de banco de dados.
Nicklas Avén
1

As páginas seguintes, relacionadas ao trabalho de mestrado de Nathan Kerr, fornecem uma boa visão sobre esse assunto direto. Meu colega de trabalho tentou o método Bostongis aqui e aqui , mas teve alguns problemas para fazê-lo funcionar corretamente.

Outra abordagem para pensar que é semelhante ao buffer é fazer um retângulo de expansão / contratação. Basicamente, passe 1 para fazer uma caixa delimitadora (é uma unidade reta + x para a caixa de entrada do polígono original) que você acha que capturará pelo menos uma interseção. Para os dados que obtiveram uma interseção, execute uma subconsulta que testa essas correspondências quanto mais próxima. Para os dados que falharam, expanda a caixa delimitadora e repita.

É claramente um problema de programação recursiva e pode ser melhor realizado em Python com Shapely do que 100% diretamente no postgis.

wildintellect
fonte