¿Cómo puedo dividir el globo en cuadrículas pequeñas de modo que me permita asignar cada ubicación de lat / long a una cuadrícula? [cerrado]

Question

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

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

¿Cuál sería la mejor manera de crear un sistema de cuadrícula de este tipo y mapearle las ubicaciones espaciales 2D?

Editar1: podría estar bien si las cuadrículas no son perfectamente uniformes, más aún alrededor de los polos.

Answer 1

Las cuadrículas rectangulares pueden ser una estimación razonable, pero solo en un área relativamente pequeña que no está demasiado cerca de los polos. Una solución global requiere un enfoque diferente.

Answer 2

El mapeo desde las coordenadas espaciales bidimensionales a su índice espacial / geohash es un problema interesante. Puede mirar esto artículo sobre quadtrees, geohashes y curvas de Hilbert . La Hilbert curve es una curva que llena el espacio y proporciona localidad; para sus propósitos, eso significa que los elementos cercanos en el índice espacial unidimensional estarán cerca en un espacio bidimensional.

El objetivo (según lo descrito por otros respondedores) es minimizar la cantidad de consultas necesarias para cubrir el espacio en cuestión sin solicitar toneladas de datos innecesarios al servidor. La forma en que hace el mapeo del espacio 2-d a un índice 1-d afectará ese objetivo.

Answer 3

Sin conocer los requisitos exactos de la aplicación, Geohashing podría ser una técnica apropiada: http: //en.wikipedia. org / wiki / Geohash

" Es una estructura jerárquica de datos espaciales que subdivide el espacio en cubos de forma de cuadrícula. Los geohashes ofrecen propiedades como precisión arbitraria y la posibilidad de eliminar gradualmente caracteres del final del código para reducir su tamaño (y gradualmente perder precisión). & Quot;

Answer 4

No puede crear una cuadrícula rectangular que mapee uniformemente un globo terráqueo. Si la cuadrícula debe ser uniforme, debe usar triángulos en su lugar. Pero en general, dudo que esto resuelva su problema. Lo que necesita es un octree en 2D (este es un enlace de búsqueda de Google; consulte las imágenes para tener una idea fácil de cómo funciona) 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.).

Luego puede hacer un par de selecciones que producirán rápidamente el rectángulo más pequeño que contiene las coordenadas existentes. Ahora, puede verificar el tamaño del rectángulo. Si es & Lt; 100m, entonces has encontrado una solución. De lo contrario, tendrá solo algunas posiciones para comparar (generalmente una).

Google para " octree sql database " para implementaciones.