El algoritmo radial

Estoy pensando en una aplicación donde tengo que, en un momento dado, saber si un punto está fuera o dentro de un polígono que en principio puede tener cualquier cantidad de vértices y sus lados no tienen porque ser regulares.

Está claro que si dibujo el punto puedo saber si está dentro o fuera del polígono. Pero ¿y si solo se las coordenadas, es decir el valor numérico, de los vértices y el punto?



No es una respuesta, en principio trivial, la respuesta más obvia es ir comprobando si el punto es mayor o menor que las coordenadas de los vértices. Eso implica muchas condiciones que si luego tienes que programar pueden hacer que tu programa vaya más lento. Luego hay algoritmos más rápidos pero que también tienen sus pegas ya que presentan casos particulares que hay que tratar.

¿Y qué se hace entonces?¿Se resigna uno a tener programas lentos? Pues claro que no.

Imagina que tu estás dentro de un polígono y empiezas a mirar uno a uno y de forma consecutiva los vértices. A medida que lo vas haciendo te tienes que ir girando y cuando acabas vuelves al primero habrás dado una vuelta completa sobre ti mismo, es decir, habrás recorrido un ángulo de 360⁰ o $$2\pi$$ radianes.

¿Y que pasa si estás fuera?

Empezarás en el primero e irás girando a izquierda o derecha según donde esté el siguiente vértice. Lo que puedes comprobar es que no giras sobre ti mismo, que una vez que has visto todos los vértices y vuelves al primero el ángulo recorrido es cero.

Así que el algoritmo es sencillo:

Calcular el ángulo recorrido.
Si es 0 estás fuera, si es $$2\pi$$ estás dentro.

Dejo pendiente para más adelante, ahora me falta tiempo, una herramienta que ayude a visualizar este algoritmo :)

Esta entrada participa en la edición 4.12 del Carnaval de Matemáticas; en esta ocasión el  blog anfitrión High Ability Dimension






No hay comentarios:

Publicar un comentario en la entrada