Tengo una lista de más de 15 mil coordenadas de latitud y longitud. Dadas las coordenadas X, Y, ¿cuál es la forma más rápida de encontrar las coordenadas más cercanas en la lista?Comparación de Lat, Long Coordenadas
Querrá utilizar una construcción geométrica llamada Voronoi diagram. Esto divide el plano en un número de áreas, una para cada punto, que abarca todos los puntos que están más cerca de cada uno de sus puntos dados.
El código para los algoritmos exactos para crear el diagrama de Voronoi y organizar las búsquedas de la estructura de datos es demasiado grande para caber en este pequeño cuadro de edición. :)
@Linor: Eso es esencialmente lo que harías después de crear un diagrama de Voronoi. Pero en lugar de hacer una cuadrícula rectangular, puedes elegir líneas divisorias que coincidan con las líneas del diagrama de Voronoi (de esta forma obtendrás menos áreas que crucen las líneas divisorias). Si recursivamente divide su diagrama de Voronoi a la mitad a lo largo de la mejor línea divisoria para cada subdiagrama, puede hacer una búsqueda en árbol para cada punto que desee buscar. Esto requiere un poco de trabajo por adelantado, pero ahorra tiempo más tarde. Cada búsqueda estaría en el orden del registro N donde N es el número de puntos. ¡16 comparaciones es mucho mejor que 15,000!
Incluso si crea un diagrama voronoi, eso significa que necesita comparar sus coordenadas x, y con las 15 mil áreas creadas. Para hacerlo más fácil, lo primero que me vino a la mente fue crear una especie de cuadrícula sobre los valores posibles, para que pueda ubicar fácilmente y coordenada x/y en una de las casillas de una grilla, si la misma es hecho para la lista de áreas, debe reducir rápidamente los posibles candidatos para comparación (porque la cuadrícula sería más rectangular, es posible que un área esté en múltiples posiciones de cuadrícula).
El concepto general que está describiendo es nearest-neighbour search, y hay una gran cantidad de técnicas que se ocupan de resolver este tipo de consultas, ya sea exacta o aproximadamente. La idea básica es utilizar una técnica de partición espacial para reducir la complejidad de O (n) por consulta a (aproximadamente) O (log n) por consulta.
KD-Trees, y las variantes de KD-Trees parecen funcionar muy bien, pero los árboles cuádruples también funcionarán. La calidad de estas búsquedas depende de si su conjunto de 15,000 puntos de datos es estático (no está agregando muchos puntos de datos al conjunto de referencia). El trabajo de Mount y Arya en la biblioteca Approximate Nearest Neighbour es fácil de usar y entender, incluso sin una buena base en matemáticas. También le da cierta flexibilidad en los tipos y tolerancias de sus consultas.
Premature optimization is the root of all evil.
15K coordenadas no son mucho. ¿Por qué no iterar sobre las coordenadas 15K y ver si eso es realmente un problema de rendimiento? Podrías ahorrarte mucho trabajo y tal vez nunca sea tan lento como para darte cuenta.
No sabe exactamente dónde está haciendo su cálculo (cpu) y por qué. Podría hacerlo en una plataforma incrustada como MIPS, y podría costarle mucho tiempo de CPU. –
No especificó a qué se refería con el más rápido. Si quiere obtener la respuesta rápidamente sin escribir ningún código, le daré una oportunidad al gpsbabel radius filter.
Más bien depende de cuántas veces quieras hacerlo, y qué recursos están disponibles; si estás haciendo la prueba una vez, entonces las técnicas de O (log N) son buenas. Si lo haces mil veces en un servidor, construir una tabla de búsqueda de mapa de bits sería más rápido, ya sea dando el resultado directamente o como una primera etapa de. 2 GB de mapa de bits pueden mapear el lat-lon del mundo entero a un valor de 32 bits a 0.011 grados de píxeles (1.2 km en el ecuador), y deben caber en la memoria. Si solo está haciendo un solo país o puede excluir los polos, puede tener un mapa más pequeño o una resolución más alta. Para 15,000 puntos, probablemente tengas un mapa mucho más pequeño: primero lo evalué como un primer paso para hacer búsquedas de códigos postales de larga duración, que necesitan una resolución más alta.Dependiendo de los requisitos, utiliza el valor asignado para señalar el resultado directamente, o para una lista breve de los candidatos (lo que permitiría un mapa más pequeño, pero requiere un mayor procesamiento posterior; ya no está en el territorio de búsqueda O (1))
Lo hice una vez para un sitio web. Es decir. encuentre el distribuidor dentro de 50 millas de su código postal. Usé el great circle calculation para encontrar las coordenadas que estaban a 50 millas al norte, a 50 millas al este, a 50 millas al sur y a 50 millas al oeste. Eso me dio un lat min y max y un min y max long. A partir de ahí luego hice una consulta de base de datos:
select *
from dealers
where latitude >= minlat
and latitude <= maxlat
and longitude >= minlong
and longitude <= maxlong
Dado que algunos de esos resultados todavía habrá más de 50 millas de distancia, a continuación, he utilizado la great circle formula una vez más en que la pequeña lista de coordenadas. Luego imprimí la lista junto con la distancia desde el objetivo.
Por supuesto, si desea buscar puntos cerca de la línea de fecha internacional o los polos, entonces esto no funcionará. ¡Pero funciona muy bien para búsquedas dentro de América del Norte!
¿Qué extensión de área tienen estas coordenadas? ¿En qué latitud están? ¿Cuánta precisión necesitas? Si están bastante juntos, probablemente puedas ignorar el hecho de que la Tierra es redonda y solo tratar esto como un plano cartesiano en lugar de jugar con la geometría esférica y las grandes distancias circulares. Por supuesto, a medida que se aleja del ecuador, los grados de longitud se hacen más pequeños en comparación con los grados de latitud, por lo que puede ser apropiado algún tipo de factor de escala.
Comience con una fórmula de distancia bastante simple y una búsqueda de fuerza bruta y vea cuánto tiempo va a tomar y si los resultados son lo suficientemente precisos antes de que se sienta elegante.
Gracias a todos por las respuestas.
@Tom, @Chris Upchurch: Las coordenadas son bastante cercanas entre sí, y se encuentran en un área relativamente pequeña de aproximadamente 800 km2. Supongo que puedo suponer que la superficie es plana. Necesito procesar las solicitudes una y otra vez, y la respuesta debe ser lo suficientemente rápida para una mayor experiencia web.
Según sus aclaraciones, utilizaría una estructura de datos geométricos como un árbol KD o un árbol R. MySQL tiene un tipo de datos ESPACIAL que hace esto. Otros idiomas/marcos/bases de datos tienen bibliotecas para apoyar esto. Básicamente, una estructura de datos de este tipo incrusta los puntos en un árbol de rectángulos y busca en el árbol utilizando un radio. Esto debería ser lo suficientemente rápido, y creo que es más simple que construir un diagrama de Voronoi. Supongo que hay un umbral por encima del cual preferiría el rendimiento agregado de un diagrama de Voronoi para que esté listo para pagar la complejidad añadida.
Una cuadrícula es muy simple y muy rápida. Básicamente es solo una matriz 2D de listas. Cada entrada de la matriz representa los puntos que caen dentro de una celda de la cuadrícula. Muy fácil de configurar la red hasta:
for each point p
get cell that contains p
add point to that cell's list
y es muy fácil de ver las cosas:
given a query point p
get cell that contains p
check points in that cell (and its 8 neighbors), against query point p
Alejo
Esto se puede resolver de varias maneras. Primero abordaría este problema generando una red Delaunay que conecta los puntos más cercanos entre sí. Esto se puede lograr con el comando v.delaunay en la aplicación de código abierto GIS GRASS. Puede completar el problema en GRASS usando uno de los muchos network analysis modules en GRASS. Alternativamente, puede usar el RDBMS espacial libre PostGIS para hacer las consultas de distancia.Las consultas espaciales de PostGIS son considerablemente más potentes que las de MySQL, ya que no están limitadas a las operaciones de BBOX. Por ejemplo:
SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;
Puesto que usted está usando longitud y la latitud, es probable que desee utilizar el Spheroid-Distance functions. Con un índice espacial, PostGIS escala muy bien para grandes conjuntos de datos.
Para ser contradictorio, ¿quiere decir distancia de cerca o tiempo de conducción? En un área urbana, con gusto conduciría 5 millas (5min) en la carretera de 4 millas (20min de parada y listo) en otra dirección.
Por lo tanto, si se trata de una medida "más cercana" que necesita, buscaría en las bases de datos de GIS las métricas del tiempo de viaje.
He tenido buenos resultados con KD-Trees por hacer este problema exacto. Mientras estés contento manteniendo el árbol en RAM, funciona muy bien. –