¿Cómo puedo dividir el globo terráqueo en cuadrículas pequeñas de modo que pueda asignar cada latitud/longitud a una cuadrícula?

Question

Para calcular las ubicaciones más cercanas que están representadas por latitud/longitud, estaba considerando dividir el mapa en cuadrículas pequeñas, aproximadamente cuadrículas de 100x100 metros. Esencialmente, cada punto se asignaría a una grilla.

Entiendo que podría usar también índices espaciales con MySQL, etc., pero estoy planeando usar una base de datos no relacional como Cassandra, donde sería difícil hacer indexación en objetos espaciales, y entonces algún tipo de técnica de aproximación de cuadrícula podría ser ordenado.

¿Cuál sería la mejor manera de crear un sistema de este tipo rejilla y mapear las localizaciones espaciales 2-D a ella?

Edit1: Podría estar bien si las redes no son perfectamente uniforme, más aún alrededor de los polos.

Answer 1

rejillas rectangulares pueden ser una estimación razonable, pero sólo en un área relativamente pequeña que no está demasiado cerca de los polos. Una solución de globo completo requiere un enfoque diferente.

Answer 2

No puede crear una cuadrícula rectangular que mapea uniformemente un globo. Si la cuadrícula debe ser uniforme, debe usar triángulos en su lugar. Pero, en general, dudo que esto resuelva tu problema. Lo que necesita es un 2D octree (este es un enlace de búsqueda de Google; compruebe las imágenes para una pista fácil de cómo funciona esto) de algún tipo: debe dividir sus coordenadas en jerarquías (por ejemplo, norte/sur/este/oeste del origen) para el primer nivel y luego entre 90 grados, etc.).

A continuación, puede hacer un par de selecciona cuáles producirán rápidamente el rectángulo más pequeño que no contiene coordenadas existentes. Ahora, puedes verificar el tamaño del rectángulo. Si es < 100m, entonces ha encontrado una solución. De lo contrario, solo tendrá unas pocas posiciones para verificar (generalmente una).

Google para "base de datos octree sql" para implementaciones.

Answer 3

Sin saber exactamente sus requerimientos de aplicación Geohashing podría ser una técnica adecuada:. http://en.wikipedia.org/wiki/Geohash

"es una estructura de datos espaciales jerárquica que subdivide el espacio en los cubos de forma de rejilla Geohashes ofrecen propiedades como la precisión arbitraria y la posibilidad de eliminando gradualmente los caracteres del final del código para reducir su tamaño (y perder gradualmente la precisión) ".

Answer 4

Mapeo de las coordenadas espaciales bidimensionales a su índice/geohash espacial es un problema interesante. Puede mirar this article on quadtrees, geohashes and Hilbert curves. El Hilbert curve es una curva de relleno de espacio que proporciona la localidad; para sus propósitos, eso significa que los elementos cercanos en el índice espacial unidimensional estarán cerca en el espacio bidimensional.

El objetivo (según lo descrito por otros respondedores) es reducir al mínimo el número de consultas necesarias para cubrir el espacio en cuestión sin solicitar toneladas de datos innecesarios desde el servidor. Cómo se hace el mapeo desde el espacio 2-d hasta el índice 1-d afectará ese objetivo.