Algoritmo para encontrar o ponto mais próximo

Eu tenho uma lista de algumas centenas de cidades com latitude / longitude. Dada outra localização (também em lat / long), preciso encontrar a cidade mais próxima.

Como eu não uso nenhum SIG, o algoritmo óbvio agora é fazer um loop para todas as cidades, calculando a distância entre os pontos.

Fazer o loop é praticável para mim, mas existe algum algoritmo fácil de implementar para realizar isso com mais eficiência? Ou alguma biblioteca Java leve que pode ajudar a resolver isso?

Notas : Não preciso / quero uma solução GIS completa ou uma biblioteca pesada / complicada. Prefiro uma solução menos boa, mas mais fácil e mais leve, porque é a única coisa que preciso resolver.

Eu investiguei exatamente essa questão há 20 anos ao projetar um GIS de desktop. Precisávamos encontrar distâncias ponto a ponto interativamente; nosso objetivo era fazer os cálculos em menos de 1/2 segundo para milhares de pontos. Os testes (em um PC 486 de 25 MHz!) Mostraram que poderíamos calcular todas as distâncias, exatamente como você descreve (com o algoritmo óbvio simples), tão rapidamente que não fazia sentido criar uma solução mais sofisticada, como uma estrutura de quadtree .

Para calcular distâncias até um único ponto de "sonda", suas opções incluem (a) projetar todos os pontos usando uma projeção equidistante centralizada no ponto de sonda ou (b) adotar um modelo de terra esférico e usar a fórmula de Haversine . O primeiro é apropriado se você precisar da precisão de um modelo elipsoidal. Em ambos os casos, os cálculos são razoavelmente rápidos, provavelmente levando menos de 1000 ticks: você pode consultar cerca de um milhão de pontos por segundo com um único processador.

Rápido o suficiente para você? Caso contrário, o método da força bruta é paralelo facilmente e é escalonado diretamente com o número de processadores: apenas divida os pontos entre os processadores e faça uma comparação final do mais próximo encontrado por cada processador.

Se você precisar ir mais rápido, poderá usar várias aproximações aos pontos da tela. Por exemplo, se você está entre -88 e +88 graus de latitude e o ponto mais próximo encontrado até agora fica a 200 km, qualquer ponto cuja latitude difere da latitude do ponto de sonda em mais de 2 graus não pode estar mais próximo (porque em qualquer lugar terra, um grau de latitude excede cerca de 110 km). Em muitos casos, esse tipo de pré-triagem pode permitir que você processe centenas de milhões de pontos por segundo.

Concordo com os outros que um loop simples deve ser eficaz para "algumas centenas de cidades".

Dada a sua aplicação, lidar com distâncias elipsoidais é provavelmente um grande exagero - você provavelmente está lidando com previsões meteorológicas cuja localidade dificilmente chega a alguns metros. A geometria esférica é simples o suficiente para que você possa fazer isso facilmente no seu loop.

Pode ser ainda mais simples (por exemplo, use delta lat como y e delta lon * cos (lat) como x e encontre o mínimo x ^ 2 + y ^ 2). Você está usando o cosseno da latitude alvo, que você calcula apenas uma vez. Isso será cada vez mais impreciso para cidades distantes, mas elas serão rejeitadas de qualquer maneira, portanto, não importa. Supondo que sua cidade mais próxima esteja geralmente dentro de algumas centenas de quilômetros, as chances de um resultado diferente (cidade mais próxima) usar isso vs usar uma fórmula mais precisa são muito pequenas e ocorreriam apenas quando as diferenças forem pequenas o suficiente para "qual previsão é mais preciso "provavelmente dependeria de outros fatores de qualquer maneira (isto é, perda de ruído).

A menos que você esteja usando um sistema incorporado ou um intérprete lento, você provavelmente pode se dar ao luxo de usar apenas os bailes esféricos que outros estão sugerindo.

Isso é um acréscimo ao que já foi dito, mas pensei em observar a importância de escolher uma estrutura de dados apropriada. Escrevi meu próprio código para uma função K no .NET e descobri que o uso de coleções eficientes acelerava substancialmente as coisas. Desculpe, não conheço a notação O para velocidades exatas. Eu usei dois dicionários para coordenadas xey com a identificação do ponto como chave. Eu não sei Java, então não poderia sugerir nada.

Cheers, David