Algoritmo para el punto más cercano

Question

Tengo una lista de ~ 5000 puntos (especificados como pares de longitud/latitud), y quiero encontrar los 5 más cercanos a otro punto, especificado por el usuario.

¿Alguien puede sugerir un algoritmo eficiente para resolver esto? Estoy implementando esto en Ruby, así que si hay una biblioteca adecuada, sería bueno saberlo, ¡pero aún estoy interesado en el algoritmo!

ACTUALIZACIÓN: Un par de personas han pedido más detalles específicos sobre el problema. Así que aquí va:

• Los 5000 puntos se encuentran principalmente dentro de la misma ciudad. Puede haber algunos fuera de él, pero es seguro suponer que el 99% de ellos se encuentran dentro de un radio de 75 km, y que todos ellos se encuentran dentro de un radio de 200 km.
• La lista de puntos cambia raramente. En aras de la discusión, digamos que se actualiza una vez por día, y tenemos que lidiar con unas miles de solicitudes en ese momento.

Answer 1

Puede obtener un estimador del límite superior muy rápido en distancia utilizando la distancia de Manhattan (escalado para la latitud), esto debería ser lo suficientemente bueno para rechazar el 99,9% de los candidatos si no están cerca (EDIT: desde entonces díganos que están cerca. En ese caso, su métrica debe ser de distancia al cuadrado, según el comentario de Lars H). Considere este equivalente para rechazar cualquier cosa fuera de un cuadro delimitador de rectángulo esférico (como una aproximación a un recuadro delimitador circular). no hago Rubí asi que aquí hay algoritmo con pseudocódigo:

Deje que la latitud, longitud de su punto de referencia P (pa, po) y la otro punto X (xa, xo). Precomputa ka, factor de escala de latitud para distancias longitudinales: ka (= cos (pa en °)). (Estrictamente, ka = constante es una aproximación linealizada en la proximidad de P.)

Entonces, el estimador de distancia es: D(X,P) = ka*|xa-pa| + |xo-po| = ka*da + do

donde | z | significa abs (z). En el peor de los casos, esto sobreestima la distancia real en un factor de √2 (cuando da == do), por lo tanto, lo permitimos de la siguiente manera:

Realice una búsqueda activa y mantenga Dmin, la quinta escama más pequeña-Manhattan-distance- estimar. Por lo tanto puede rechazar por adelantado todos los puntos para los que D (X, P)> √2 * Dmin (ya que deben estar al menos más lejos que √ ((ka * da) ² + do²) - eso debería eliminar el 99.9% de puntos). Guarde una lista de todos los puntos candidatos restantes con D (X, P) < = √2 * Dmin. Actualiza Dmin si encuentras una nueva quinta más pequeña D. Cola de prioridad, o bien una lista de (coord, D) son buenas estructuras de datos. Tenga en cuenta que nunca calculamos la distancia euclidiana, solo utilizamos la multiplicación y la suma flotante.

(Considere esto similar al árbol de cuatro ramas, excepto la filtración de todo, excepto la región que nos interesa, por lo tanto, no hay necesidad de calcular distancias exactas por adelantado o construir la estructura de datos.)

Sería de gran ayuda si nos dice la propagación esperada en latitudes, longitudes (grados, minutos o lo que sea) Si todos los puntos están cerca, el factor √2 en este estimador será demasiado conservador y marcará todos los puntos como candidato, un estimador de distancia basado en la tabla de búsqueda sería preferible)

Pseudocódigo:

initialize Dmin with the fifth-smallest D from the first five points in list 
for point X in list: 
    if D(X,P) <= √2 * Dmin: 
     insert the tuple (X,D) in the priority-queue of candidates 
     if (Dmin>D): Dmin = D 
# after first pass, reject candidates with D > √2 * Dmin (use the final value of Dmin) 
# ... 
# then a second pass on candidates to find lowest 5 exact distances 

Answer 2

Se podría acelerar la búsqueda mediante la partición del espacio 2D con un quad-tree o una kd-tree y luego una vez que haya llegar a un nodo hoja se comparan las distancias restantes, uno por uno hasta encontrar la coincidencia más cercana.

Ver también this blog post que hace referencia a this other blog post que analizan las búsquedas de vecinos más cercanas con kd-trees en Ruby.

Answer 3

Como su lista es bastante corta, recomiendo encarecidamente la fuerza bruta. Simplemente compare todos los 5000 con el punto especificado por el usuario. Será O (n) y te pagarán.

Aparte de eso, un quad-tree o Kd-tree son los enfoques habituales para la subdivisión espacial. Pero en su caso, terminará haciendo un número lineal de inserciones en el árbol, y luego un número constante de búsquedas logarítmicas ... un poco desperdiciado, cuando probablemente esté mejor haciendo solo un número lineal de comparaciones de distancia y hecho con eso.

Ahora, si quiere encontrar los N puntos más cercanos, está buscando ordenar las distancias calculadas y tomar la primera N, pero sigue siendo O (n log n) ish.

EDITAR: Vale la pena señalar que la construcción del árbol espacial vale la pena si va a reutilizar la lista de puntos para múltiples consultas.

Answer 4

Dado que tiene pocos puntos, recomendaría hacer una búsqueda de fuerza bruta, con el propósito de probar todos los puntos entre sí con una operación O(n^2), con n = 5000, o aproximadamente 25/2 millones de iteraciones de un adecuado algoritmo, y solo almacenando los resultados relevantes. Esto tendría un tiempo de ejecución inferior a 100 ms en C, por lo que estamos buscando un segundo o dos como máximo en Ruby.

Cuando el usuario elige un punto, puede usar los datos almacenados para obtener los resultados en tiempo constante.

EDIT He vuelto a leer su pregunta, y parece que el usuario proporciona su último punto. En ese caso, es más rápido hacer una búsqueda lineal O(n) a través de su conjunto cada vez que el usuario proporciona un punto.

Answer 5

En lugar de pura fuerza bruta, para 5000 nodos, calcularía las distancias x + y individuales para cada nodo, en lugar de la distancia en línea recta.

Una vez que haya ordenado esa lista, si, por ejemplo, x + y para el quinto nodo es 38, puede descartar cualquier nodo donde x o y la distancia sea> 38. De esta manera, puede descartar una gran cantidad de nodos sin tener que calcular la distancia en línea recta. Luego, la fuerza bruta calcula la distancia en línea recta para los nodos restantes.

Answer 6

Estos algoritmos no se explican fácilmente, por lo tanto, solo daré algunos consejos en la dirección correcta. Deberías buscar diagramas de Voronoi. Con un diagrama de Voronoi, puede calcular previamente un gráfico en tiempo O (n^2 log n) y buscar el punto más cercano en el tiempo O (log n).

La precomputación se realiza con un trabajo de cron en la noche y la búsqueda es en vivo. Esto corresponde a su especificación.

Ahora puede guardar los k closests pares de cada uno de sus 5000 puntos y luego comenzar desde el punto más cercano al diagrama de Voronoi y buscar los 4 puntos restantes.

Pero ten en cuenta que estos algoritmos no son muy fáciles de implementar.

Una buena referencia es:

• de Berg: Computational Geometry Algoritmos Aplicaciones (2008) capítulos 7.1 y 7,2

Answer 7

si es necesario repetir esta operación varias veces, con diferentes ubicaciones introducidos por el usuario , pero no desea implementar un árbol cuádruple (o no puede encontrar una implementación de biblioteca), entonces puede usar un enfoque hashing (tipo de) sensible a la localidad que es bastante intuitivo:

• tomar sus (x, y) pares y crear dos listas, una de (x, i) y uno de (Y, i), donde i es el índice del punto
• especie ambas listas

entonces , cuando se le da un punto (X, y),

• bisección tipo para X e y
• ampliar hacia el exterior en ambas listas, en busca de los índices comunes
• para los índices comunes, calcular las distancias exactas
• deja de expandirse cuando las diferencias en X e Y exceden la distancia exacta de los 5 puntos actuales más distantes.

todo lo que está haciendo es decir que un punto cercano debe tener una x similar y un valor y similares ...