Dentro de un polígono
Necesitaría saber si dado un punto (x, y), está dentro o fuera de un polígono no regular conocidos sus vértices (Xi, Yi)
1 respuesta
Respuesta de sherdal
1
Con un enunciado cortito te has marcado una pregunta con tela marinera. Vamos a ver, no quiero largarte un rollo de mucho cuidado así que te daré un par de indicaciones y tú haces el resto (prefiero darte la caña antes que el pescado).
A mi modo de ver tienes dos maneras de enfocar el asunto:
- La primera es con un algoritmo de recorte reduciendo el caso de una línea a un punto, con lo que se simplifica un poco. Aun así, necesitarías trabajar bastante el algoritmo (por ejemplo, el Cyrus-Beck), ya que tienes que calcular normales, productos vectoriales, etc. Además de la complejidad, tiene la limitación de que sólo es aplicable a polígonos convexos (aquellos en los que dados dos puntos interiores, todos los puntos de la línea que los une son interiores), teniendo que programar un sistema de reducción de polígonos cóncavos a un conjunto de polígonos convexos.
- El segundo aproximación es algo más sencillo aunque no es trivial. Mediante el Teorema de Curva de Jordan, hay desarrollado un algoritmo por Eric Haines, que a grandes rasgos consiste en lo siguiente:
Trasladando el polígono de manera que el punto en cuestión esté en el origen de coordenadas, se traza una línea en una dirección arbitraria y se cuenta el número de líneas del polígono que intersectan dicha recta. Si el número de intersecciones es impar, el punto es interior. Si es par, el punto es exterior.
Este algoritmo tiene una gran ventaja y es que funciona tanto con polígonos convexos como cóncavos.
Total, que finalmente te he largado un rollo de cuidado y te he dicho poco, ¿verdad?. Vale, por si te lo quieres currar un poco, te pongo la bibliografía que conozco que te puede ayudar, y si no, me lo dices y te lo intento explicar de otra manera.
Bibliografía:
Procedural Elements for Computer Graphics, David F. Rogers, McGraw-Hill
ISBN: 0-07-053534-5
An Introduction to Ray Tracing, Andrew Glassner, Academic Press Limited
ISBN: 0-12-286160-4
A mi modo de ver tienes dos maneras de enfocar el asunto:
- La primera es con un algoritmo de recorte reduciendo el caso de una línea a un punto, con lo que se simplifica un poco. Aun así, necesitarías trabajar bastante el algoritmo (por ejemplo, el Cyrus-Beck), ya que tienes que calcular normales, productos vectoriales, etc. Además de la complejidad, tiene la limitación de que sólo es aplicable a polígonos convexos (aquellos en los que dados dos puntos interiores, todos los puntos de la línea que los une son interiores), teniendo que programar un sistema de reducción de polígonos cóncavos a un conjunto de polígonos convexos.
- El segundo aproximación es algo más sencillo aunque no es trivial. Mediante el Teorema de Curva de Jordan, hay desarrollado un algoritmo por Eric Haines, que a grandes rasgos consiste en lo siguiente:
Trasladando el polígono de manera que el punto en cuestión esté en el origen de coordenadas, se traza una línea en una dirección arbitraria y se cuenta el número de líneas del polígono que intersectan dicha recta. Si el número de intersecciones es impar, el punto es interior. Si es par, el punto es exterior.
Este algoritmo tiene una gran ventaja y es que funciona tanto con polígonos convexos como cóncavos.
Total, que finalmente te he largado un rollo de cuidado y te he dicho poco, ¿verdad?. Vale, por si te lo quieres currar un poco, te pongo la bibliografía que conozco que te puede ayudar, y si no, me lo dices y te lo intento explicar de otra manera.
Bibliografía:
Procedural Elements for Computer Graphics, David F. Rogers, McGraw-Hill
ISBN: 0-07-053534-5
An Introduction to Ray Tracing, Andrew Glassner, Academic Press Limited
ISBN: 0-12-286160-4
