Punto contenido dentro de un polígono - bnl

[ethernet]

        Punto contenido dentro de un polígono        

Copio directamente del blog de bnl:

Una necesidad muy común en el desarrollo de videojuegos es la de determinar si un punto esta contenido dentro de un polígono irregular. Por ejemplo en el caso de una aventura gráfica es necesario para averiguar si el usuario ha pulsado sobre una determinada región que podría ser un objeto, otro personaje, etc.

Dentro de la librería matemática que he creado se encuentra la clase polígono que implementa dicha funcionalidad. Así como una serie de clases que también son utilizadas en el algoritmo como la clases Vector o la clase Angulo

El algoritmo para determinar si el punto esta incluido dentro del área del polígono es bastante sencillo, pero requiere algunos cálculos.

Inicialmente se une el punto que se quiere averiguar si esta dentro o fuera del polígono con cada uno de los vértices del polígono, con lo cual se obtendrán tantos segmentos como vértices tenga el polígono.
Después hay que ir sumando los ángulos que forman esos segmentos. La suma hay que realizarla en orden, es decir primero sumar el ángulo que forma el segmento del punto al vertice1 con el segmento del punto al vertice2 con el ángulo que forma el segmento del punto al vertice2 con el segmento del punto al vertice3. Y así sucesivamente en orden hasta terminar sumando el ángulo que forma el segmento del último vértice con el del primer vértice.
Si el ángulo total resultante de la suma de ángulos es 0 grados entonces el punto estará fuera del polígono, si es 2PI entonces estará dentro.
Al realizar los cálculos probablemente se acumulen errores de redondeo así que a lo mejor el resultado no es exactamente 0 o 2 PI, por lo que no se debe comparar con 0 o 2PI si no ver si esta cerca de esos valores.

El código, en VB.NET, lo podeis ver perfectamente formateado en el blog de bnl

Si quieres enviar un COTW, envia un PM a ethernet.
[/list]

[sés]

Ese método me parece algo rebuscado y pesado (senos, cosenos, módulos...).

Para mí, el método más simple y fácil de implementar es el siguiente:

1. Se traza una línea recta desde el punto a comprobar hacia cualquier dirección. Normalmente, y por simplificar, una línea horizontal hacia la derecha.

2. Se comprueban los segmentos del polígono que corta dicha línea.

3. Si la línea corta un nº par de segmentos, el punto está fuera. Si es impar, el punto está dentro.

Código [Seleccionar] Expand

public boolean contains( double px[], double py[], int n, double x, double y )
{
   boolean bInside = false;
   
   double x1, y1;
   double x2, y2;

   for( int i=0; i<n; i++ ) {
       x1 = px[i];
       y1 = py[i];
       if( i < n-1 ) {
           x2 = px[i+1];
           y2 = py[i+1];
       } else {
           x2 = px[0];
           y2 = py[0];
       }

       if( y1 != y2 ) {
           if( (y1<=y && y2>y) || (y2<=y && y1>y) ) {
               double xc = x1 + ((x2-x1)*(y-y1)) / (y2-y1);
               if( xc > x ) {
                   bInside = !bInside;
               } else if( xc == x ) {
                   return true;
               }
           }
       } else {
           if( (y==y1) && ((x>=x1 && x<=x2) || (x>=x2 && x<=x1)) ) {
               return true;
           }
       }
   }
   
   return bInside;
}

px = Array de X
px = Array de Y
n = Nº de puntos
x = X del punto a comprobar
y = Y del punto a comprobar

Más información aquí mismo. Es el primer enlace que he encontrado.

Tiene algún "problema" (en muchos casos nos da igual) si el punto coincide en un segmento o corta justo un vértice. En esos casos es cuestión de cada uno el decidir qué hacer. En mi caso, lo tomo como dentro.

[bnl]

Tu algoritmo me parece mucho más intuitivo pero no es mucho mas sencillo que el otro. Lo unico algunos calculos, pero tampoco son muy complejos

Realmente el concepto no es tan complicado, simplemente es sumar los angulos que forma el punto con los vertices del poligono. En cuanto a código tambien es bastante sencillo, no llegan a las 20 lineas de código.

Hace no mucho en otro post de stratos se estuvieron comentando otras formas de hacerlo. Dejo el enlace por si interesa

http://www.stratos-ad.com/forums3/viewtopic.php?t=9287


Saludos

[Mars Attacks]

Sin pararme a analizarlo en profundidad, el tema de los ángulos podría no funcionar para algunas figuras no convexas (imagina un polígono con forma de una E "gorda").

Código [Seleccionar] Expand


__________
| * ________|
|   |_____
|     _____|
|   |_______
|__________|


¿Eso suma 0 grados?

[BeRSeRKeR]

Efectivamente sólo vale para polígonos convexos.

Saludos.

[bnl]

Creo que vale para tanto para poligonos convexos como concavos.
En el caso de la E grande al sumar los grados a ojo a mi me sale tambien 360 (lo que indicaria que esta dentro)

[bnl]

He hecho la prueba para confirmarlo



El algoritmo devuelve que la suma de los angulos es 360.00000000000006

He hecho pruebas con la E gorda poniendo el punto en diferentes lugares, dentro y fuera y ha funcionado en todas.


El algoritmo (al igual que el otro que ha comentado ses) creo que funcionan tanto para concavos como para convexos

Saludos

[Mars Attacks]

Entonces es cojonudo :)

[sés]

¿Funciona también para polígonos con huecos?

[bnl]

No, para ese caso no valdria.
Ni se podria aplicar el algoritmo ya que recorre vertices adyacentes y si tienes huecos no estarian contectados todos los vertices, si no que si tuviera por ejemplo un hueco entonces habria dos listas de vertices.

Quiza podria adaptarse para que lo contemplara, recorriendo cada lista de vertices. Y sacando conclusiones a partir de las sumas de los angulos de las distintas listas de vertices por separado.

[sés]

Entonces no hay duda, me quedo con el otro :P

[bnl]

He estado pensando un poco sobre lo de los huecos, segun he visto en la wikipedia http://es.wikipedia.org/wiki/Pol%C3%ADgono si tiene huecos realmente no es un poligono, ya que no tiene sus lados consecutivos.

Para adaptar el algoritmo a areas que pudieran tener huecos en principio creo que bastaria con considerar cada hueco como un poligono adicional por lo que tendriamos n+1 poligonos, siendo n el numero de huecos. Habria que aplicar el algoritmo para cada poligono y si esta dentro de un numero impar de poligonos entonces esta dentro y si no esta fuera. Tampoco lo he pensado mucho ni he hecho pruebas aplicando el algoritmo, pero a simple vista parece que funcionaria. Corregidme si me equivoco.

El otro algoritmo si que funcinaria directamente con areas con huecos.

Saludos

[Esgaroth]

El algoritmo que traza una línea en una dirección determinada puede fallar, ya que si la línea atravieza un vértice, entonces se invierte el resultado:

Si está dentro --> Está fuera
Si está afuera --> Está adentro

En resumidas cuentas, si la línea atravieza un número par de vértices, el algoritmo funciona correctamente, pero si la línea atravieza un número impar de vértices, entonces el algoritmo no funciona correctamente.

Para solucionar: si la línea atravieza un vértice, entonces no sumar uno al contador de "colisiones".

PD: Muy bueno el método de las líneas y el de los ángulos: nunca me los hubiera imaginado xD.

[Pogacha]

En realidad no quiero ser pesado ni nada mas pero tengan presente que la forma clasica como se resuelve el problema es esta:

Código [Seleccionar] Expand

typedef std::vector<Math::Vector2> Poligon;
Poligon mPoligon;

bool Point_Inside_Regular_Poligon( const Poligon& poligon, const Math::Vector2& p )
{
const int n = poligon.size();
int j = n-1;

for(int i=0; i<n; ++i)
{
if(Math::Triangle_Side(p, poligon[j], poligon[i]) == Math::COUNTERCLOCKWISE) return false;
j = i;
}

return true;
}

Código [Seleccionar] Expand


namespace Math {
...
// Solo lo importante
struct Vector2 {
...
float Dot(const Vector2 &t) const { return x * t.x + y * t.y; }
Vector2 Tangent(void) const { return Vector2(y, -x); }
...
float x,y;
};

...

enum {
CLOCKWISE = -1,
COLINEAR = 0,
COUNTERCLOCKWISE = 1
};

inline int Triangle_Side(const Math::Vector2 a, const Math::Vector2 b, const Math::Vector2 c)
{
const float d = (b-a).Dot( (c-a).Tangent() );
if( d > Epsilon ) return CLOCKWISE;
if( d < -Epsilon ) return COUNTERCLOCKWISE;
return COLINEAR;
}
...
}


No tiene fallos ni singularidades, no hay divisiones escandalozas y tiene en cuenta un EPSILON de error el cual se adapta a la matematica de punto flotante con el cual podemos nosotros decir que hacer cuando la evaluación es incierta por las limitaciones del hardware.

Son 2 multiplicaciones y 5 sumas/restas por vertice y lineal con respecto a los vertices.

Si lo escribimos unrolleada como parece les gusta a ustedes, pues la vez anterior no me entendieron, claramente se ve que metodo es el mejor:

Código [Seleccionar] Expand

public boolean contains( double px[], double py[], int n, double x, double y )
{
int j = n-1;
for(int i=0; i<n; ++i)
{
if( (px[j]-x)*(y-py[i]) + (py[j]-y)*(px[i]-x) < -0.001 ) return false;
j = i;
}
return true;
}

La mas rapida, la mas sencilla, la mas compacta, la mas correcta desde el punto de vista teorico y funcional.

No hay mas que eso ... no inventen polvora plz!

Saludos

[Pogacha]

OK, antes de que me manden a la hoguera me doy yo.

SALAME, estas hablando de un codigo para poligonos convexos!

Si si, el codigo que yo puse es para poligonos convexos.  :oops:

Para poligonos irregulares el tema se complica, están, los poligonos cruzados, los con superposiciones y los huecos.

Voy a buscar mis apuntes y en un par de dias pongo el metodo clasico, que lo ví alguna vez. Pero segun recuerdo era el de subdividir en poligonos convexos, creo que bsp si mal no recuerdo.

Saludos!