El mejor algoritmo de rendimiento crítico para resolver al 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 es necesario realizar la inserción y eliminación. Solo quiero encontrar el vecino más cercano de un objetivo xq, punto yq en este conjunto.

Edit 1: ¡Gracias a todos! Como Stephan202 ha adivinado correctamente, quiero hacer esto repetidamente; como una función. La lista no está necesariamente ordenada (de hecho, no entiendo cómo se puede ordenar, como una tabla con una clave principal de 2 columnas ayy si eso ayuda, la 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 es relevante).

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

Editar 2: ¡He encontrado que, este problema se llama "vecino más cercano"!

Edición 3: El primer título fue "En busca de un algoritmo (para consultas espaciales e indexación espacial) (vecino más cercano)"; He elegido un nuevo título: "Mejor algoritmo de rendimiento crítico para resolver al vecino más cercano". Dado que 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 va a ser insertado), elegí (actualmente) trabajar en KD-Trees. ¡Gracias a todos!

Answer 1

Como se señaló Stephan202, si Si planeas buscar la pareja más cercana para más de un punto, debes usar un árbol.

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

EDIT: Hice una pregunta sobre implementaciones de kd-tree here - podría ser útil.

EDIT: KD-árboles han sido ampliamente utilizado con éxito para las búsquedas NN :) - Además, si usted está dispuesto a aceptar coincidencias aproximadas, puede utilizar Fast Library for Approximate Nearest Neigbor (FLANN). La implementación de FLANN está presente en OpenCV 2.0.

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

Answer 2

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

Sin embargo, no ha dado suficiente información para una respuesta de rendimiento crítico.

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

Segundo ejemplo, si tiene un gran número de puntos, es posible organizar los puntos en secciones y comenzar con puntos solamente en la misma sección y las secciones adyacentes a la sección que contiene P.

Answer 3

Si el punto de consulta (xq, yq) varía y la lista no lo hace, debe calcular el Voronoi diagram de la lista de puntos.Esto le dará un conjunto de polígonos o "células" (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 ha llegado tan lejos, necesita una manera fácil de averiguar en qué polígono se encuentra. Esto se conoce como point location problem.

Un libro realmente bueno para este tipo de cosas es Computational Geometry: Algorithms and Applications. Discuten en detalle el cálculo del diagrama de Voronoi y el método de la losa trapezoidal de la ubicación del punto.

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 se aplica también a la respuesta del árbol KD, pero no lo sé específicamente.

Answer 4

Necesita spatial index.

Si rueda el suyo, puede hacer mucho peor que elegir los algoritmos R-Tree o Quad-tree.

Answer 5

Me gustaría ir 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 bonito truco de optimización si sus coordenadas son de coma flotante: En una consulta, primero tendrá que encontrar el nodo hoja que contiene el punto al que se le pide el punto más cercano. Para hacer esto, tendrás que ir al árbol desde la raíz hasta la hoja, en cada iteración decidir qué nodo hijo pisar. Almacene los identificadores/direcciones de los nodos secundarios en una matriz de 4 tamaños en la estructura Nodo. Digitalice las coordenadas del punto en el algoritmo de consulta. Entonces podrá encontrar el subnodo apropiado simplemente indexando la matriz mediante 2 bits propios de las coordenadas del punto digitalizado. La digitalización es rápida: impleméntelo con un simple static_cast.

Pero primero implemente el quadtree sin optimización porque es fácil hacer un error con las operaciones de bits. Incluso sin esta optimización, todavía será la solución más rápida.