Dado un conjunto de puntos P en dos dimensiones, ¿cuál es el algoritmo más eficiente para determinar el punto más cercano en P a una línea dada L?

Answer 1

Ciertamente, puede mejorar una solución que simplemente calcula la distancia para todos los puntos. En la práctica, las ganancias de una implementación particular pueden depender de la distribución de los puntos y las líneas. Sobre posible mejora:

– determine el centro C del círculo más pequeño que contendrá todos sus puntos y calcule su radio R
– determine el conjunto de puntos que son vértices del polígono convexo más pequeño que contendrá todos sus puntos, y establezca una bandera en estos puntos (márquelos como ‘perímetro’ o lo que sea)
– ahora para cualquier línea que se esté evaluando, calcule la distancia a C; si es mayor que R, entonces solo necesita iterar sobre el conjunto de puntos perimetrales para encontrar el más cercano, porque la línea pasa fuera del conjunto de puntos

Sin embargo, esta optimización puede ser inútil si su L siempre o casi siempre pasa a través de P en lugar de pasar fuera de ella.
Para una situación en la que L pasa a través de P, debería ser posible mejorar la iteración exhaustiva ordenando previamente los puntos en zonas o grupos, y descartando o eliminando conjuntos completos de puntos basados ​​en el hecho de que su grupo asignado está demasiado lejos del línea. Básicamente, si sabemos que todos los puntos P1 están dentro de cierta distancia D1 del punto central de P1, y sabemos que la distancia desde este punto a L es mayor que D1 más la distancia al candidato actual para el punto más cercano, podemos descartar todo el conjunto P1 de nuestra lista de candidatos sin más cálculos.
Una pregunta difícil, por supuesto, es exactamente qué tipo de conjunto de zonas o grupos daría como resultado el mejor rendimiento.

Answer 2

Bien, la ecuación para calcular la distancia de un solo punto P a la línea es bien conocida: distancia de un punto a una línea

Un algoritmo simple sería buscar linealmente todos los puntos en P.

Si desea lidiar con la suma y eliminación de puntos en P, entonces un enfoque obvio sería almacenar la distancia para cada punto con el punto en un montón.

Answer 3

Creo que obtener el casco convexo y calcular las distancias de los puntos de los bordes del casco no sería tan malo. Cualquier transformación en los puntos se aplicará también al casco.