Encuentra el punto más cercano de un vector de puntos

Question

Tengo vector de punteros a una clase muy simple Point:

class Point{ 
public: 
    float x; 
    float y; 
    float z; 
}; 

¿Cómo puedo encontrar el objeto más cercano a un punto referente usando STL?
¿Debo primero ordenar primero el vector o hay una forma más eficiente?

Answer 1

La ordenación requiere O(n*log(N)), por lo que no es muy eficiente. Puede hacerlo en O(n) simplemente recorriendo los elementos y memorizando la mejor coincidencia.

Usando for_each desde <algorithm>, puede definir una función que realiza un seguimiento de los elementos más cercanos y completa en O(n).

O, probablemente también pueda usar min_element, también desde <algorithm>.

Answer 2

No puede ir más rápido que una comparación lineal si solo sabe que hay puntos en un vector. Sin embargo, si tiene conocimientos adicionales, se puede mejorar mucho. Por ejemplo, si sabes que todos los puntos están ordenados y se encuentran en la misma línea, hay una solución logarítmica.

También hay estructuras de datos mejores para resolver su problema, por ejemplo, k-d tree. No es parte de la STL; tendrá que implementarlo usted mismo, pero es LA estructura de datos que debe usar para resolver el problema que tiene.

Answer 3

La pregunta básica aquí es con qué frecuencia realizará consultas en un solo conjunto de puntos.

Si va a encontrar un punto más cercano en el conjunto una vez, entonces @Lucian tiene razón: también puede dejar los puntos sin clasificar, y hacer una búsqueda lineal para encontrar el punto correcto.

Si va a hacer una cantidad relativamente grande de consultas con el mismo conjunto de puntos, vale la pena organizar los datos del punto para mejorar la velocidad de consulta. @izomorphius ya mencionó un árbol k-d, y definitivamente es una buena sugerencia. Otra posibilidad (ciertamente, bastante similar) es un oct-tree. Entre los dos, encuentro que un árbol oct es bastante más fácil de entender. En teoría, un árbol k-d debería ser un poco más eficiente (en promedio), pero nunca he visto mucha diferencia, aunque tal vez con diferentes datos la diferencia se volvería significativa.

Tenga en cuenta, sin embargo, que la construcción de algo como un árbol k-do oct-árbol no terriblemente lenta, por lo que no tiene que hacer una gran cantidad de consultas en un conjunto de puntos para justificar la construcción de uno. Una consulta claramente no lo justifica, y dos probablemente tampoco, pero, al contrario de lo que implica Luchian, O (N log N) (solo por ejemplo) no es realmente muy lento. En términos generales, log (N) es el número de dígitos en el número N, por lo que O (N log N) no es mucho más lento que O (N). Eso, a su vez, significa que no necesita una gran cantidad de consultas para justificar la organización de los datos para acelerar cada uno.

Answer 4

se puede tratar de utilizar Quadtree http://en.wikipedia.org/wiki/Quadtree

o algo similar.