Distancia de un punto a un segmento, primera parte

Uno 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

Entradas relacionadas

Etiquetas: , ,

11 comentarios to “Distancia de un punto a un segmento, primera parte”

  1. Carlos Says:

    pero solo del punto A al punto B, cuanto mide, una formula para calcular la distancia de solo dos puntos.

  2. Korosu Itai Says:

    Muy práctico, ¡gracias!

  3. KuPo Says:

    Realmente útil, muchas gracias!

  4. kenantz Says:

    Muy útil, gracias ^^!

  5. un amigo Says:

    thank apicable a tecnicas de map-maching en mapas digitales con rutas gps

    bonito contenido!

  6. natalia Says:

    ayuda si tengo cuatro numeros y dos son de a y dos de b como hago?????????

  7. Julian Perelli Says:

    Hola, muchas gracias por la info, es justamente lo que buscaba. Me ayudo mucho a visualizar el problema. Nadie mas habla de esto en internet. Buen trabajo!

    Saludos!

  8. Distancia punto a segmento, quinta parte y final « Programación Cocoa Says:

    […] Distancia punto a segmento, teoria. […]

  9. Adrián Says:

    Hola, muy claro y útil, muchas gracias!.

    Para el caso del denominador = 0 (cuando A = B “el segmento se reduce a un punto”), el punto C está contenido si C = A. Lo mismo si queremos saber el punto proyectado podemos devolver A.

  10. Mario Says:

    Saludos,

    Esta formula aplica para coordenadas de latitude y longitude

  11. www.la-cour-de-chateau.de Says:

    http://www.la-cour-de-chateau.de

    Distancia de un punto a un segmento, primera parte | Programación Cocoa

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: