Programadores => Código de la Semana => Mensaje iniciado por: ethernet en 10 de Septiembre de 2007, 09:30:17 pm

Título: Punto contenido dentro de un polígono - bnl
Publicado por: ethernet en 10 de Septiembre de 2007, 09:30:17 pm
(http://www.stratos-ad.com/forums/style_images/1/pip.gif)         Punto contenido dentro de un polígono         (http://www.stratos-ad.com/forums/style_images/1/pip.gif)

Citar

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 (http://www.brausoft.com/2007/09/03/punto-contenido-dentro-de-un-poligono/)

Si quieres enviar un COTW, envia un PM a ethernet.
[/list]
Título: Punto contenido dentro de un polígono - bnl
Publicado por: sés en 11 de Septiembre de 2007, 08:57:48 am
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]
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 (http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/). 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.
Título: Punto contenido dentro de un polígono - bnl
Publicado por: bnl en 11 de Septiembre de 2007, 03:47:17 pm
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
Título: Punto contenido dentro de un polígono - bnl
Publicado por: Mars Attacks en 11 de Septiembre de 2007, 08:49:08 pm
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]

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


¿Eso suma 0 grados?
Título: Punto contenido dentro de un polígono - bnl
Publicado por: BeRSeRKeR en 11 de Septiembre de 2007, 10:16:06 pm
Efectivamente sólo vale para polígonos convexos.

Saludos.
Título: Punto contenido dentro de un polígono - bnl
Publicado por: bnl en 11 de Septiembre de 2007, 10:37:36 pm
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)
Título: Punto contenido dentro de un polígono - bnl
Publicado por: bnl en 11 de Septiembre de 2007, 10:58:21 pm
He hecho la prueba para confirmarlo

(http://img210.imageshack.us/img210/2871/incluyexk4.png)

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
Título: Punto contenido dentro de un polígono - bnl
Publicado por: Mars Attacks en 12 de Septiembre de 2007, 01:16:00 am
Entonces es cojonudo :)
Título: Punto contenido dentro de un polígono - bnl
Publicado por: sés en 12 de Septiembre de 2007, 09:02:41 am
¿Funciona también para polígonos con huecos?
Título: Punto contenido dentro de un polígono - bnl
Publicado por: bnl en 12 de Septiembre de 2007, 10:33:57 am
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.
Título: Punto contenido dentro de un polígono - bnl
Publicado por: sés en 12 de Septiembre de 2007, 11:40:10 am
Entonces no hay duda, me quedo con el otro :P
Título: Punto contenido dentro de un polígono - bnl
Publicado por: bnl en 12 de Septiembre de 2007, 12:32:07 pm
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
Título: Punto contenido dentro de un polígono - bnl
Publicado por: Esgaroth en 12 de Noviembre de 2007, 02:54:42 pm
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.
Título: Punto contenido dentro de un polígono - bnl
Publicado por: Pogacha en 13 de Noviembre de 2007, 02:00:38 am
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]
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]

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]
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
Título: Punto contenido dentro de un polígono - bnl
Publicado por: Pogacha en 13 de Noviembre de 2007, 05:09:28 am
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!
Título: Punto contenido dentro de un polígono - bnl
Publicado por: Pogacha en 13 de Noviembre de 2007, 05:24:00 am
Este esta bastante decente en realidad:
Código: [Seleccionar]
bool point_in_poly(int n, const float *xp, const float *yp, float x, float y)
{
     bool c = false;
     for (int i = 0, j = n-1; i < n; j = i++)
        if ((((yp[i] <= y) && (y < yp[j])) ||
           ((yp[j] <= y) && (y < yp[i]))) &&
           ((x - xp[i]) * (yp[j] - yp[i]) - (xp[j] - xp[i]) * (y - yp[i]) < 0.001f) c = !c;
   return c;
}

Igual falla con los colineales y vertices sobre vertices ...
Título: Punto contenido dentro de un polígono - bnl
Publicado por: Esgaroth en 13 de Noviembre de 2007, 08:35:19 pm
Acá les explico de manera gráfica el posible error que puede causar el método de trazar una línea para determinar si el punto está dentro o fuera del polígono.

**** Línea del polígono
____ Relleno1
....... Relleno2
------ Línea trazada
P       Punto

Número par de colisiones:

_***********************
_*______________________*
_*______*__P----*----------------*------
_*_____* *____*_*__________*
_******__*****__************

Salida ---> Está fuera.

Número impar de colisiones:

_***********************
_*______________________*
_*__P----*----------*---------------*------
_*_____* *____*_*__________*
_******__*****__************

Salida: ---> Está dentro.

Supuestamente la línea debe atravezar el vértice. Pero no podemos obviar los vértices, ya que podría llegar a suceder suceder esto:

__*******************
__*............................*
__*................P------*-----------
__*............................*
__*******************

Salida ---> Está fuera (ya que se obviaron los vértices).

Sé que no se entiende muy bien, es porque tuve que poner un "Relleno" para que el programa encargado de "corregir" no me cancele el relleno hecho con la tecla espacio (sirve para corregir el doble espacio).

Aún así me parece un método bastante simple y efectivo, solo debería solucionar el problema de los vértices.
Título: Punto contenido dentro de un polígono - bnl
Publicado por: Pogacha en 16 de Noviembre de 2007, 10:58:02 pm
OK,
Luego de repasar los libros un poco ...

La solución general es descomposición en triangulos, que es Nlg2N en el peor de los casos.
Pero no es muy práctica y tiene una constante elevada, para perfecta presición ese debes usar.

El metodo del winding number es el mas recomendado luego de esto, pero tienes que atender los casos especiales en donde el punto es colineal con algun segmento del poligono y la recta elegida y el otro caso especial cuando el punto coincide con algún vertice.

Saludos!

EDITO:
Olvide decir, y por supuesto si el poligono es estatico, y habrá muchas pruebas, el algoritmo a elegir es el arbol bsp, donde llegaras al resultado en de Log2N a N. Dependiendo de cuan convexo sea será mas cercano a N y sino mas cercano a Log2N.

Saludos!