Comparação de coordenadas lat e longas

https://stackoverflow.com/questions/35870

09-06-2019
|

Pergunta

Tenho uma lista de mais de 15 mil coordenadas de latitude e longitude.Dadas quaisquer coordenadas X,Y, qual é a maneira mais rápida de encontrar as coordenadas mais próximas na lista?

Solução

Você vai querer usar uma construção geométrica chamada Diagrama de Voronoi.Isso divide o plano em várias áreas, uma para cada ponto, que abrangem todos os pontos mais próximos de cada um dos pontos fornecidos.

O código para os algoritmos exatos para criar o diagrama de Voronoi e organizar as pesquisas da estrutura de dados é muito grande para caber nesta pequena caixa de edição.:)

@Linor:Isso é essencialmente o que você faria depois de criar um diagrama de Voronoi.Mas em vez de fazer uma grade retangular, você pode escolher linhas divisórias que correspondam às linhas do diagrama de Voronoi (desta forma você obterá menos áreas que cruzam as linhas divisórias).Se você dividir recursivamente seu diagrama de Voronoi ao meio ao longo da melhor linha divisória para cada subdiagrama, poderá fazer uma pesquisa em árvore para cada ponto que deseja procurar.Isso requer um pouco de trabalho inicial, mas economiza tempo depois.Cada pesquisa seria na ordem do log N, onde N é o número de pontos.16 comparações são muito melhores que 15.000!

Outras dicas

Eu fiz isso uma vez para um site.Ou sejaencontre o revendedor dentro de 50 milhas do seu código postal.Eu usei o cálculo do grande círculo para encontrar as coordenadas de 80 quilômetros ao norte, 80 quilômetros a leste, 80 quilômetros ao sul e 80 quilômetros a oeste.Isso me deu um mínimo e um máximo de latência e um mínimo e um máximo de comprimento.A partir daí fiz uma consulta ao banco de dados:

select *
    from dealers
    where latitude  >= minlat
      and latitude  <= maxlat
      and longitude >= minlong
      and longitude <= maxlong

Como alguns desses resultados ainda estarão a mais de 80 quilômetros de distância, usei o fórmula do grande círculo mais uma vez naquela pequena lista de coordenadas.Depois imprimi a lista junto com a distância do alvo.

Claro, se você quiser procurar pontos próximos à linha internacional de data ou aos pólos, isso não funcionará.Mas funciona muito bem para pesquisas na América do Norte!

O conceito geral que você está descrevendo é pesquisa do vizinho mais próximo, e há uma série de técnicas que tratam de resolver esses tipos de consultas, de maneira exata ou aproximada.A ideia básica é usar uma técnica de particionamento espacial para reduzir a complexidade de O(n) por consulta para (aproximadamente) O( log n ) por consulta.

KD-Trees e variantes de KD-Trees parecem funcionar muito bem, mas quad-trees também funcionam.A qualidade dessas pesquisas depende se o seu conjunto de 15.000 pontos de dados é estático (você não está adicionando muitos pontos de dados ao conjunto de referência).O trabalho de Mount e Arya no Vizinho mais próximo aproximado biblioteca é fácil de usar e entender, mesmo sem uma boa base matemática.Também oferece alguma flexibilidade nos tipos e tolerâncias de suas consultas.

Depende de quantas vezes você deseja fazer isso e de quais recursos estão disponíveis - se você estiver fazendo o teste uma vez, as técnicas O (log N) serão boas.Se você estiver fazendo isso mil vezes em um servidor, construir uma tabela de pesquisa de bitmap seria mais rápido, fornecendo o resultado diretamente ou como um primeiro estágio.2 GB de bitmap podem mapear todo o mundo em latitude para um valor de 32 bits em pixels de 0,011 graus (1,2 km no equador) e devem caber na memória.Se você estiver estudando apenas um país ou puder excluir os pólos, poderá ter um mapa menor ou uma resolução mais alta.Para 15.000 pontos, você provavelmente terá um mapa muito menor - primeiro dimensionei-o como um primeiro passo para fazer pesquisas de lat-lon para código postal, que precisam de resolução mais alta.Dependendo dos requisitos, você usa o valor mapeado para apontar diretamente para o resultado ou para uma pequena lista de candidatos (o que permitiria um mapa menor, mas requer maior processamento subsequente - você não está mais no território de pesquisa O(1) ).

Você não especificou o que quis dizer com mais rápido.Se você quiser obter a resposta rapidamente sem escrever nenhum código, eu daria o filtro de raio gpsbabel atrás.

Com base em seus esclarecimentos, eu usaria uma estrutura de dados geométrica, como uma árvore KD ou uma árvore R.MySQL tem um tipo de dados SPATIAL que faz isso.Outras linguagens/frameworks/bancos de dados possuem bibliotecas para suportar isso.Basicamente, essa estrutura de dados incorpora os pontos em uma árvore de retângulos e pesquisa a árvore usando um raio.Isso deve ser rápido o suficiente e acredito que seja mais simples do que construir um diagrama de Voronoi.Acho que há algum limite acima do qual você preferiria o desempenho adicional de um diagrama de Voronoi, para estar pronto para pagar pela complexidade adicional.

Isso pode ser resolvido de várias maneiras.Eu primeiro abordaria esse problema gerando um Delaunay rede conectando os pontos mais próximos uns dos outros.Isso pode ser feito com o comando v.delaunay no aplicativo GIS de código aberto GRAMA.Você poderia resolver o problema no GRASS usando um dos muitos módulos de análise de rede na GRAMA.Alternativamente, você pode usar o RDBMS espacial gratuito PostGIS para fazer as consultas de distância.As consultas espaciais do PostGIS são consideravelmente mais poderosas que as do MySQL, pois não estão restritas às operações BBOX.Por exemplo:

SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;

Como você está usando Longitude e Latitude, provavelmente desejará usar o Funções de distância esferoide.Com um índice espacial, o PostGIS se adapta muito bem a grandes conjuntos de dados.

Mesmo se você criar um diagrama de voronoi, isso ainda significa que você precisa comparar suas coordenadas x, y com todas as 15 mil áreas criadas.Para tornar isso mais fácil, a primeira coisa que me veio à mente foi criar algum tipo de grade sobre os valores possíveis, para que você possa facilmente colocar as coordenadas e x/y em uma das caixas de uma grade, se o mesmo for feito para a lista de áreas, você deve reduzir rapidamente os possíveis candidatos para comparação (como a grade seria mais retangular, é possível que uma área esteja em múltiplas posições da grade).

Otimização prematura é a raiz de todo o mal.

Coordenadas de 15K não são muito.Por que não iterar nas coordenadas de 15K e ver se isso é realmente um problema de desempenho?Você pode economizar muito trabalho e talvez nunca fique lento demais para perceber.

Qual é o tamanho da área em que essas coordenadas estão espalhadas?Em que latitude eles estão?Quanta precisão você precisa?Se eles estiverem bem próximos, você provavelmente poderá ignorar o fato de que a Terra é redonda e apenas tratar isso como um plano cartesiano, em vez de brincar com geometria esférica e grandes distâncias circulares.É claro que, à medida que você se afasta do equador, os graus de longitude ficam menores em comparação com os graus de latitude, portanto, algum tipo de fator de escala pode ser apropriado.

Comece com uma fórmula de distância bastante simples e uma pesquisa de força bruta e veja quanto tempo isso vai levar e se os resultados são precisos o suficiente antes de você começar a imaginar.

Obrigado a todos pelas respostas.

@Tom, @Chris Upchurch:As coordenadas são bastante próximas umas das outras e situam-se numa área relativamente pequena de cerca de 800 km2.Acho que posso assumir que a superfície é plana.Preciso processar as solicitações repetidamente, e a resposta deve ser mais rápida o suficiente para proporcionar mais experiência na web.

Uma grade é muito simples e muito rápida.É basicamente apenas uma matriz 2D de listas.Cada entrada da matriz representa os pontos que estão dentro de uma célula da grade.Muito fácil de configurar a grade:

for each point p
  get cell that contains p
  add point to that cell's list

e é muito fácil pesquisar as coisas:

given a query point p
  get cell that contains p
  check points in that cell (and its 8 neighbors), against query point p

Alejo

Só para ser contrairiano, você quer dizer distância próxima ou tempo (de direção)?Em uma área urbana, eu dirigiria com prazer 5 milhas (5 minutos) na rodovia do que 6,4 milhas (20 minutos parando e andando) em outra direção.

Portanto, se você precisa de uma métrica 'mais próxima', eu examinaria os bancos de dados GIS com métricas de tempo de viagem.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow