El mejor algoritmo de rendimiento crítico para resolver el vecino más cercano

Question

Tenemos una lista de pares x, y. Cada par representa un punto en un espacio 2D. Quiero encontrar el punto más cercano de esta lista, a un punto específico xq, yq. ¿Cuál es el mejor algoritmo de rendimiento crítico para este problema? Lisp de puntos no va a cambiar; lo que significa que no necesito realizar la inserción y eliminación. Solo quiero encontrar el vecino más cercano de un objetivo xq, yq en este conjunto.

Edición 1: ¡Gracias a todos! Como Stephan202 ha adivinado correctamente, quiero hacer esto repetidamente; como una función Y la lista no está necesariamente ordenada (de hecho, no entiendo cómo se puede ordenar. ¿Como una tabla con una clave primaria de 2 columnas ay e? Si eso ayuda, lo ordenaré).

Construiré la estructura de datos basada en la lista una vez, y luego usaré esta estructura de datos generada en la función (si este proceso en sí es relevante).

Gracias Jacob; Parece que la estructura de datos de KD-Tree es un buen candidato para ser la respuesta (y creo que lo es. Actualizaré cuando obtenga algunos resultados relevantes).

Edición 2: He descubierto que este problema se llama "vecino más cercano"

Edición 3: El primer título fue " En busca de un algoritmo (para consulta espacial e indexación espacial) (vecino más cercano) " ;; Elegí un nuevo título: "Mejor algoritmo crítico de rendimiento para resolver el vecino más cercano". Como no quiero realizar operaciones de inserción y eliminación en mis datos iniciales y quiero solo el más cercano de ellos a un nuevo punto (que no se va a insertar), elegí (actualmente) trabajar en KD-Trees. ¡Gracias a todos!

Answer 1

Como señaló Stephan202, si planea encontrar la coincidencia más cercana para más de un punto, debe usar un árbol.

Recomendaría un árbol KD, cuya implementación se puede encontrar fácilmente en varios paquetes como OpenCV 2.0 . ¡O podría implementar uno usted mismo!

EDITAR: hice una pregunta sobre las implementaciones de kd-tree aquí - podría ser útil.

EDITAR: los árboles KD han sido ampliamente utilizados con éxito para búsquedas NN :) - Además, si está dispuesto a aceptar coincidencias aproximadas, puede usar Biblioteca rápida para el vecino más cercano aproximado (FLANN) . La implementación de FLANN está presente en OpenCV 2.0 .

Si no desea respuestas aproximadas, puede modificar los parámetros de FLANN para buscar en todo el árbol.

Answer 2

Si el punto de consulta (xq, yq) varía y la lista no, debe calcular el Diagrama de Voronoi de la lista de puntos. Esto le dará un conjunto de polígonos o '' celdas '' (algunos de los cuales son infinitos); cada polígono corresponde a un punto de la lista original, llamado el "sitio" de esa celda. Cualquier punto que se encuentre completamente dentro de un polígono está más cerca del sitio de ese polígono que de los otros sitios en la lista original. Cualquier punto en un límite entre dos polígonos se encuentra igualmente distante de cada sitio.

Una vez que haya llegado tan lejos, necesita una manera fácil de averiguar en qué polígono se encuentra. Esto se conoce como problema de ubicación del punto .

Un libro realmente bueno para este tipo de cosas es Geometría computacional: algoritmos y aplicaciones . Discuten en detalle tanto el cálculo del diagrama de Voronoi como el método de losa trapezoidal de ubicación de puntos.

Si no desea hacer el código usted mismo, y no debe hacerlo, intente obtener una biblioteca como CGAL que hará la mayor parte del trabajo por usted. Esto probablemente también se aplica a la respuesta del árbol KD, pero no lo sé específicamente.

Answer 3

Necesita un índice espacial .

Si rueda el suyo, puede hacerlo mucho peor que elegir el R-Tree o Algoritmos de cuatro árboles .

Answer 4

Yo iría con un quadtree. Es la estructura espacial más simple. En 2 dimensiones, generalmente recomendaría quadtree en lugar de kd-tree, porque es más simple, más rápido. Su inconveniente es un mayor consumo de memoria si el número de dimensiones es alto, pero en el caso de 2 dimensiones la diferencia no es significativa.

Hay un buen truco de optimización si sus coordenadas están escritas en coma flotante: En una consulta, primero tendrá que encontrar el nodo hoja que contiene el punto al que se solicita el punto más cercano. Para hacer esto, tendrá que ir al árbol desde la raíz hasta la hoja, en cada iteración para decidir qué nodo secundario debe pisar. Almacene los identificadores / direcciones de los nodos secundarios en una matriz de 4 tamaños en la estructura Node. Digitalice las coordenadas del punto en el algoritmo de consulta. Entonces podrá encontrar el subnodo adecuado simplemente indexando la matriz en 2 bits apropiados de las coordenadas de los puntos digitalizados. La digitalización es rápida: impleméntela con un simple static_cast.

Pero primero implemente el quadtree sin optimización porque es fácil hacer un error con las operaciones de bit. Incluso sin esta optimización, seguirá siendo la solución más rápida.

Answer 5

Itere a través de cualquier otro punto usando la fórmula de la distancia para encontrar la distancia mínima de Q (xq, yq).

Sin embargo, no ha proporcionado suficiente información para una respuesta crítica para el rendimiento.

Por ejemplo, si Q es un punto MUY común, es posible que desee calcular la distancia a Q y almacenarlo con cada punto.

Segundo ejemplo, si tiene una gran cantidad de puntos, puede organizar los puntos en secciones y comenzar con puntos solo en la misma sección y secciones adyacentes a la sección que contiene Q.