30/1/2012

Cómo saber si un punto está dentro o fuera de una figura

Empecemos por estudiar el problema sobre una circunferencia. Una circunferencia es una curva plana cerrada, es decir que tiene un interior y un exterior. Es además una curva simple, lo que quiere decir que no se corta a sí misma.
A las curvas que cumplen estas dos condiciones, ser cerradas y simples, se las denomina curvas de Jordan. Todas las curvas de Jordan son topológicamente equivalentes, ya que se pueden obtener por deformación continua de un círculo. El que un punto sea interior o exterior a una curva es una propiedad topológica, por lo tanto, si lo estudiamos para el caso de una circunferencia, lo habremos resuelto para cualquier curva de Jordan, por complicada que ésta sea.

Supongamos que tenemos dos puntos, uno dentro y otro fuera de la circunferencia. Podemos unirlos mediante una línea de muy diferentes formas, tal como muestra la figura:
 

Cuando lo hacemos siguiendo la línea roja cortamos a la circunferencia una vez; siguiendo la verde, tres veces; siguiendo la amarilla, cinco veces. Independientemente de como lo hagamos, el número de cortes es siempre impar. Por el contrario, cuando los dos puntos están dentro, dicho número será siempre par.

Así pues, un procedimiento para saber si un punto está dentro o fuera de una curva (cerrada y simple) podría ser el siguiente: tomamos un punto arbitrario que esté situado fuera de la curva, unimos este punto con el punto dado y contamos el número de cortes. Si es par, el punto dado estará fuera de la curva; si es impar, estará dentro.

En el siguiente ejemplo vemos que al unir el punto dado con un punto exterior se obtiene un número impar de cortes; en consecuencia, el punto dado es interior a la curva: