Como posso dividir o mundo em que pequenas grades de tal forma que me permite atribuir a cada longa localização lat / a uma grade? [fechadas]

Question

Para calcular os locais mais próximos que são representados por / longitude latitude, eu estava pensando em dividir o mapa em pequenas grades, cerca de 100x100 grades metros. Essencialmente cada ponto seria atribuído a uma grade.

Eu entendo que eu poderia, em vez também usam índices espaciais com MySQL etc, mas estou planejando usar um banco de dados não-relacional como Cassandra onde seria difícil de fazer a indexação em objetos espaciais, e assim por algum tipo de técnica de grade aproximação poderia ser puro.

Qual seria a melhor maneira de criar um tal sistema de grade e mapear as localizações espaciais 2-D para ele?

Edit1:. Pode ser tudo bem se as grades não são perfeitamente uniforme, mais ainda em torno dos pólos

Answer 1

grades retangulares pode ser uma estimativa razoável, mas apenas sobre uma área relativamente pequena que não é muito perto dos pólos. Uma solução completa de globo requer uma abordagem diferente.

Answer 2

O mapeamento das coordenadas espaciais bidimensionais para o seu espacial index / geohash é um problema interessante. Você pode olhar para este artigo sobre quadtrees, geohashes e curvas de Hilbert . O href="http://en.wikipedia.org/wiki/Hilbert_curve" rel="noreferrer"> curva é uma curva de espaço de enchimento que proporciona localização; para os seus fins, o que significa que os itens próximos no índice espacial unidimensional será próximos no espaço bidimensional.

O objetivo (como descrito por outros respondedores) é minimizar o número de consultas necessárias para cobrir o espaço em questão sem pedir toneladas de dados desnecessários do servidor. Como você faz o mapeamento de 2-d espaço para um índice de 1-d afetará esse objetivo.

Answer 3

Sem saber suas necessidades de aplicação exatas Geohashing pode ser uma técnica adequada: http: //en.wikipedia. org / wiki / Geohash

"É uma estrutura de dados espaciais hierárquica que subdivide o espaço em baldes de forma grid. Geohashes oferecer imóveis como precisão arbitrária e a possibilidade de remover gradualmente caracteres a partir do final do código para reduzir seu tamanho (e precisão perdem gradualmente). "

Answer 4

Você não pode criar uma grade retangular que mapeia uniformemente um globo. Se a grade deve ser uniforme, você deve usar triângulos vez. Mas, em geral, duvido que isso vai resolver o seu problema. O que você precisa é um 2D octree (este é um link de busca Google, verificar as imagens para uma pista fácil como funciona este) de algum tipo: Você deve dividir suas coordenadas em hierarquias (por exemplo norte / sul / leste / oeste da origem para o primeiro nível e, em seguida, entre 90 graus, etc.)

.

Em seguida, você pode fazer um par de seleciona que rapidamente produzem o menor retângulo que contém coordenadas existentes. Agora, você pode verificar o tamanho do retângulo. Se é <100m, então você encontrou uma solução. Caso contrário, você terá apenas algumas posições para verificar contra (geralmente uma).

Google por "banco de dados octree sql" para implementações.