Punto en polígono

Saber si un punto está dentro de un polígono en un dibujo en papel con nuestra visión es natural. Diría intrascendente, obvio. Sin embargo, si tenemos que programar un algoritmo en una computadora para que lo verifique, tiene un curioso desarrollo. Los invito a pensar cómo lo harían antes de leer la solución propuesta más abajo.

El algoritmo, como podrán imaginar, es parte del juego de herramientas que nos brinda un Sistema de Información Geográfica. Y el desarrollo de  una de las ideas que lleva a la solución es el motivo de este post.

El problema

Dado un punto P, definido por sus coordenadas ( Xp e Yp  )  y un polígono cerrado de n lados definido también por sus coordenadas ( X1, Y1, X2, Y2 ,…, Xn, Yn  coincidentes con X1, Y1 ). El problema propuesto es averiguar si el punto está dentro o fuera del polígono.

La solución

Para la solución del problema, asumimos que el punto no está contenido en ninguno de los segmentos límites del polígono.

La solución consiste en dibujar semi-líneas (o rayos) que pasen por P y contar el número de veces que el rayo intercepta con el polígono. Si el número de veces es impar, entonces el punto está dentro del polígono. Si el número es par, entonces el punto está fuera. Ver la figura siguiente.

Punto en polígono

Fig. 5.33  “Semi-line algorithm for determining whether a point is inside a polygonon”, del libro de Workboys.

Referencias:

—”GIS, A computing Perspective,” Michel F. Workboys, Editorial Taylor & Francis, London, 1995.

—”Mathematical Techniques in GIS”, Peter Dale, CRC Press, London, 2004.

Etiquetas:

Categorías: Sistemas de Información Geográfica

Autor:José María Ciampagna -

profesor, agrimensor, ingeniero, aficionado a la fotografía, escribidor, informático, blogero, aspirante a cocinero y otras yerbas .....

Para Suscribirse:

Puedes suscribirte a nuestro Blog por medio de RSS, Facebook, Linkedin, o Twitter haciendo click en los siguientes iconos:

Aún no hay comentarios.

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: