data-structures - sistema - tipos de coordenadas geograficas
Índice espacial para coordenadas geográficas? (2)
¿Podría usar un algoritmo hash sensible a la localidad (LSH) en 3 dimensiones? Eso le daría rápidamente un grupo vecino aproximado que luego podría verificar la cordura calculando distancias de círculo máximo.
Aquí hay un documento que describe un algoritmo para LSH eficiente en la superficie de una unidad d -hiperesfera dimensional. Presumiblemente funciona para d = 3.
¿Qué tipo de estructura de datos podría usarse para una búsqueda eficiente de vecinos más cercanos en un gran conjunto de coordenadas geográficas? Con estructuras de índice espacial "regulares" como R-Trees que asumen coordenadas planas, veo dos problemas (¿Hay otros que he pasado por alto?):
- Wraparound en los polos y la línea de fecha internacional
- Distorsión de distancias cerca de los polos
¿Cómo se pueden permitir estos factores? Supongo que el segundo podría compensarse transformando las coordenadas. ¿Se puede modificar un R-Tree para tener en cuenta el envolvente? ¿O hay estructuras especializadas de índices geoespaciales?
Eche un vistazo a Geohash .
Además, para compensar el efecto envolvente, simplemente use no uno sino tres árboles R ortogonales, de modo que no exista un punto en la superficie de la tierra de modo que los tres árboles tengan un revestimiento en ese punto. Entonces, dos puntos están cerca si están cerca de acuerdo con al menos uno de estos árboles.