algo melhor do que caixas limitadas?

Question

Eu tenho um cenário, onde tenho x milhões de pontos de latitude de longitude.

Quando um novo ponto longo/lat é adicionado, quero saber eficientemente Quais outros pontos estão dentro de um parâmetro de distância configurado pelo usuário, para que eu possa adicioná -los a uma lista.

Tem algo melhor do que caixas delimitadoras?

Eu adoraria ver algoritmos, referências e algumas implementações;) Obrigado gentilmente!

Answer 1

Existem algumas opções que são melhores, principalmente baseadas em partição espacial.

Uma opção comum e muitas vezes muito boa (que não é muito difícil de implementar) é usar um KD-Tree. Quadtrees são mais fáceis de implementar, mas mais lentos para a pesquisa. Dependendo da distribuição de seus dados e de seus requisitos, outros algoritmos de particionamento espacial podem ter um desempenho melhor, ter requisitos de memória mais baixos ou outros problemas relacionados.

Answer 2

Um colega me disse que tinha uma boa experiência em usar Morton-código Como um índice espacial nos dados GIS, talvez isso seja algo que valha a pena investigar.

Answer 3

Essa abordagem rápida e sincera pode economizar um pouco de dor: divida a superfície da Terra em caixas de 1 grau. Você terá uma matriz de elementos de 180x360 e precisará pesquisar apenas um pequeno número de caixas, incluindo a caixa que contém o novo ponto e todas as caixas imediatamente em torno da qual um dos cantos está dentro da distância especificada pelo usuário. Você descobrirá que existem alguns truques que você pode usar para descobrir rapidamente quais caixas usar sem considerar todas elas. Só não se esqueça de latitude e longitude.

Se o seu "somente" tiver milhões de pontos e eles não estiverem agrupados em manchas quentes, isso pode levá-lo.

Uma maneira teoricamente superior: você pode mapear cada ponto no espaço tridimensional e depois armazená -los em um Octree, o que permitiria que você encontre rapidamente pontos próximos a uma distância arbitrária. Obviamente, a distância no espaço tridimensional será ligeiramente diferente da distância de grande círculo no mundo, então você terá que calcular um fator de conversão. Isso deve ser simples, no entanto. Você não menciona um idioma de implementação, mas quase certamente haverá uma implementação Octree bem testada para qualquer idioma em que você esteja trabalhando. Se você não se importa de inserir o código de terceiros, esta solução é a maneira de vai.