cómo ordenar los datos geográficos para una búsqueda rápida

Question

Tengo algunos objetos que están geolocalizados (tengo para cada objeto la latitud + longitud). Mi aplicación necesita mostrar los objetos que están a 3 kilómetros alrededor de la posición GPS del dispositivo móvil. Tengo varios miles de objetos y están localizados en un área grande (por ejemplo, varios estados de EE. UU., Varios países pequeños), lo que significa que en mi lista de objetos puedo tener uno ubicado en Nueva York y otro en Miami, pero también puedo objetos que están muy cerca (pocos metros).

Actualmente, mi aplicación realiza una búsqueda iterativa. Para cada objeto calculo la distancia con la posición del GPS y si la distancia es < = 3KM, entonces guardo el objeto si no lo ignoro. Este algoritmo no es muy eficiente y estoy buscando un algoritmo que brinde un mejor rendimiento.

Supongo que hay una manera de ordenar mis objetos usando el geo coord y luego encontrar más rápidamente los objetos que se encuentran alrededor de la posición del GPS.

Mi idea actual es simplemente calcular el rectángulo con los "puntos extremos", Norte/Sur/Este/Oeste (desde 3km de la posición del GPS) para limitar la zona de búsqueda. A continuación, calcularé la distancia solo para los objetos dentro de este cuadro. creo que algo mejor se podría hacer, pero no tengo la idea ...

Cualquier propuesta será apreciada ;-) Gracias ,

SEB.

Answer 1

suena como un nearest neighbor search, pero no con un máximo número de vecinos (como en kNN), pero con un umbral máximo distancia.

Un enfoque común es colocar los objetos en una estructura de datos especial que permita descartar rápidamente grandes partes del espacio de búsqueda. Sin embargo, estos se suelen hacer con espacios euclidianos en mente, y no para el plano esférico (lat/lon-) (problemas de envoltura). Por lo tanto, es probable que necesitaría para convertir sus coordenadas a las coordenadas 3D en un sistema cartesiano con respecto al centro de la esfera antes de poder aplicar una de las siguientes estructuras de datos para buscar de manera eficiente para sus objetos:

• Octree
• kd-tree

Answer 2

las otras respuestas mencionan índices espaciales son correctos, pero no necesariamente la solución más fácil para usted.

Consideraría algo más simple: Agrupe los artículos por país, luego por estado, región, ciudad, y finalmente - por algunos puntos de referencia en ciudades densas (donde tiene muchos objetos).

Luego solo debe realizar algunas consultas (compruebe en qué país estoy, estado, región, etc.) para limitarse a un conjunto muy pequeño de objetos, sin implementar estructuras de datos avanzadas en su aplicación móvil .

Answer 3

Una forma de hacer esto sin una estructura de datos especializada sería ordenar dos copias de sus datos, una por longitud, una por latitud. Todo lo que las búsquedas binarias se cierran para cerrar tanto en latitud como en longitud, está cerca.

Del mismo modo, podría usar su habitual ataque (rápido) o árbol rojo-negro (baja variabilidad).

Pero probablemente haya ventajas al usar un r-tree o kd-tree. Lo que he descrito probablemente sea solo para evitar tomar nuevas dependencias o evitar codificar una nueva estructura de datos desde cero.