Distancia de un punto a un segmento, primera parte
Julio 6, 2008 by luisreyUno de los problemas que he encontrado para seguir con mi programa de dibujo es ¿Como detecto que se ha hecho clic en una recta? Al principio creí encontrar la solución en la función containsPoint: de la clase NSBezierPath. Pero para mi desgracia solamente funciona con caminos cerrados (y una recta no esta muy cerrada que digamos). Para más desgracia una busqueda en google no encontro nada en castellano. Siempre aparecia como encontrar la distancia de un punto a una recta. Al final he encontrado información en inglés (que extraño ¿no?) y he decidido apuntar lo que he aprendido aquí.
Algo de matemáticas…
En este punto es importante que tengas unos conocimentos previos de matemáticas tales como puntos, vectores, rectas, producto escalar de vectores y distancias. Si no es el caso es muy difícil que puedas entender la explicación. Vuelve cuando hayas hecho los deberes.
Encontrar la distancia entre un punto y una recta es fácil:
Por ejemplo puede utilizarse la siguiente fórmula que utiliza el producto vectorial de dos vectores:
En dos dimensiones basta conocer las coordenadas de los puntos A(Ax, Ay), B(Bx, By) y C(Cx, Cy):
Nota: He “ignorado” algunos detalles, el producto vectorial solamente tiene sentido en tres dimensiones y realmente lo que interesa és el módulo del vector resultante, pero crear un vector 3D a partir de un vector 2D es trivial y puede comprobarse que el resultado funciona.
En cualquier caso lo que me interesa no es la distancia punto-recta sino punto-segmento, y si generalmente la fórmula anterior parece servir, fracasa en ejemplos como el siguiente:
En este ejemplo la fórmula proporciona una distancia a la recta, pero no al segmento. En este caso la distancia que nos interesa encontrar es entre los puntos B y C. Esto nos indica que calcular la distancia entre un punto y un segmento es algo más complicado y habrá que escoger fórmulas diferentes según la posición del punto respecto al segmento.
La solución pasa por encontrar el punto P de la recta que esta más cercano al punto C y luego comprobar si esta dentro del segmento:
En cualquier recta un punto cualquiera P(Px, Py) puede encontrarse a partir de un parámetro u y el vector que une los punto A y B, como:
Para encontrar el punto P se puede utilizar el producto escalar:
A partir de las ecuaciones anteriores (y un cierto trabajo) se puede obtener una fórmula que permite obtener el parámetro u:
- Si el valor de u esta entre 0 y 1 el punto P estará dentro del segmento. Para calcular la distancia entre el punto C y el segmento sólo hay que calcular la distancia entre P y C.
- Si es mayor que 1, C ha sobrepasado el segmento por B. La distancia entre el punto y el segmento será la distancia entre los puntos B y C.
- En cambio si u es menor que 0, el punto C no ha llegado al segmento. La distancia será la distancia entre los puntos A y C.
Fácil. No…. (Aquí uno de mis queridos profesores de la facultad decia que era “trivial”).
Un último detalle, el único problema a nivel de crear el algoritmo estará en el denominador, si A y B son el mismo punto en la fórmula nos aparecera una desagradable división por cero.
Y hasta aquí la introducción matemàtica. Próximamente el código.
Más información
- Paul Bourke, Minimum Distance Between A Point And A Line.
- Philip Nicoletti, Distance between point and line segment. Discusion sobre el tema en codeguru.com, la respuesta de Philip Nicoletti es la más interesante.
- lbackstrom, Algorithm Tutorials. Geometry Concepts: Basic Concepts, en TopCoder.com. Un forma diferente de trabajar, utiliza producto escalar para situar el punto y el producto vectorial para calcular la distancia.
Wikipedia extiende sus tentáculos en varias direcciones. Una de ellas son los 
). Como parámetros hay que enviar el objeto NSRect (rectángulo) dónde se va a hacer el seguimiento ([self visibleRect]). Quien se encarga de la gestión del seguimiento (owner:self), en este caso la propia vista, pero podría ser otro objeto. También los datos del evento para el usuario (userData: nil), en el ejemplo, nada, nil. Y cómo último parámetro si se asume que el ratón comienza estando dentro o fuera del área de seguimiento.
