algorithm - vacantes - cenapred unam
cómo ordenar los datos geográficos para una búsqueda rápida (3)
Las otras respuestas que mencionan índices espaciales son correctas, 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).
Entonces solo necesitaría realizar algunas consultas (compruebe en qué país estoy, qué 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.
Tengo algunos objetos que están geo-localizados (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 tener 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 GPS y si la distancia es <= 3KM, entonces guardo el objeto, más lo ignoro. Este algoritmo no es muy eficiente y estoy buscando un algoritmo que proporcione 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 (a partir de 3 km 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 se podría hacer algo mejor, pero no tengo la idea ...
Cualquier propuesta será apreciada ;-) Gracias,
Séb.
Una forma de hacerlo 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, puede usar su tratamiento habitual (rápido) o 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.
Suena como una búsqueda de un vecino más cercano , pero no con un número máximo de vecinos (como en kNN), pero con un umbral de distancia máximo.
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 los espacios euclidianos en mente, y no para el plano esférico (lat / lon-) (problemas de envoltura). Por lo tanto, probablemente necesite convertir sus coordenadas a coordenadas 3d en un sistema cartesiano relativo al centro de la esfera antes de que pueda aplicar una de las siguientes estructuras de datos para buscar de manera eficiente sus objetos: