Deteccion de puntos en poligonos irregulares

[Fenris78]

Saludos gente, ando entretenido tratando de mejorar la jugabilidad de Cell-Fusion, incidiendo sobre todo en la mecanica del juego.

Para ello he pensado que seria buena idea incluir la opcion de capturar a las bacterias dibujando un lazo a su alrededor.

La idea creo que es buena, pero me crea un problema complejo: La deteccion de colisiones en areas irregulares.

Aqui os dejo el link que habla sobre el tema:

http://coretex.coresecurity.com/index.php?module=talleres&id=6

http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

Investigando y preguntando a algunos amiguetes encontramos teoria y una funcion practica en C++ que podria serme tremendamente util.

El tema es que me puse manos a la obra, la transforme a GML (Lenguaje de gamemaker, si soy un muñon) y la aplique a mis propositos, pero aun no esta del todo conseguida, ya que la funcion falla con cierta frecuencia, sobre todo al situar el lazo a la derecha del punto.

A ver si alguien puede echarme un cablecillo, creo que el juego ganaria mucho si consigo implementarla.

Aqui esta la funcion en C++, creo que lo que falla es el logaritmo original.

//===================================================================

// cn_PnPoly(): crossing number test for a point in a polygon
//      Input:   P = a point,
//               V[] = vertex points of a polygon V[n+1] with V[n]=V[0]
//      Return:  0 = outside, 1 = inside
// This code is patterned after [Franklin, 2000]
//===================================================================

int
cn_PnPoly( Point P, Point* V, int n )
{
   int    cn = 0;    // the crossing number counter

   // loop through all edges of the polygon
   for (int i=0; i<n; i++) {    // edge from V to V[i+1]
      if (((V.y <P> P.y))    // an upward crossing
       || ((V.y > P.y) && (V[i+1].y <= P.y))) { // a downward crossing
           // compute the actual edge-ray intersect x-coordinate
           float vt = (float)(P.y - V.y) / (V[i+1].y - V.y);
           if (P.x < V.x + vt * (V[i+1].x - V.x)) // P.x < intersect
               ++cn;   // a valid crossing of y=P.y right of P.x
       }
   }
return (cn&1);   // 0 if even (out), and 1 if odd (in)

}

Ya de paso os dejo un video de como va. Vereis que ahora mismo falla a menudo, pero se acerca, que ya es algo. El punto a detectar esta situado justo en medio de la pantalla. Como la calidad de la grabacion es pobre cuesta un poco verlo, pero si se esfuerza uno un poco...

Ver video explicativo

Ya de paso os dejo tambien la funcion en GML

//===================================================================

// cn_PnPoly(): crossing number test for a point in a polygon
//      Input:   P = a point,
//               V[] = vertex points of a polygon V[n+1] with V[n]=V[0]
//      Return:  0 = outside, 1 = inside
// This code is patterned after [Franklin, 2000]
//===================================================================

P=argument0 //ID del objeto a localizar
//V=argument1 //Array de IDs de objetos de referencia (vertices)
n=global.max_vert-1//argument2 //numero de vertices

   cn = 0;    // contador de cruces the crossing number counter

   // bucle a traves de todos los vertices del poligono
   for (i=0; i<n; i+=1)
   {    // vertice desde V a V[i+1]
      if (((global.vertice.y <= P.y) && (global.vertice[i+1].y > P.y))    // un cruce de arriba a abajo
       || ((global.vertice.y > P.y) && (global.vertice[i+1].y <= P.y)))   // un cruce de abajo a arriba
       {
           // compute the actual edge-ray intersect x-coordinate
           vt = (P.y - global.vertice.y) / (global.vertice[i+1].y - global.vertice.y);
           
           if (P.x <  global.vertice.x + vt * (global.vertice[i+1].x - global.vertice.x) )  // P.x < intersect
           { cn=!cn; } // cada vez que es par devuelve false
           
       }
       
   }

   return cn;

[bnl]

Si no me equivoco lo que quieres es el algoritmo para detectar si un punto esta dentro de un poligono.

Yo he implementado eso en VB.NET, si estas intersado te paso el código.

Saludos

[Fenris78]

Exactamente, me harias un gran favor si me lo pasas, asi veo en que me esta fallando el algoritmo este. Te dejo mi correo:

fenris782@gmail.com

Muchas gracias BNL

[bnl]

Te pego el código, espero que te sea de ayuda.

Código [Seleccionar] Expand


   ''' <summary>
   ''' Devuelve si el punto pertenece al poligono
   ''' </summary>
   ''' <param name="pPunto"></param>
   ''' <returns></returns>
   ''' <remarks></remarks>
   Public Function Incluye(ByVal pPunto As Point) As Boolean
       Dim a As New Angulo(0)
       Dim v1 As Vector
       Dim v2 As Vector
       Dim i As Integer

       If Vertices.Count < 3 Then
           Throw New ApplicationException("El polígono debe tener al menos tres vertices y tiene " & Vertices.Count & " vertices.")
       End If

       'Trazamos un vector desde el punto a cada uno de los
       'vertices
       'Calculamos el angulo que forma cada vector con el
       'vector del vertice adyacente (el vector del ultimo
       'vertice formará un angulo con el vector primer vertice)
       'Sumamos todos los angulo
       For i = 0 To Vertices.Count - 1
           v1 = New Vector(pPunto, Vertices(i))
           v2 = New Vector(pPunto, Vertices((i + 1) Mod Vertices.Count))
           a = a + Vector.Angulo(v1, v2)
       Next

       'Si el angulo resultante es 360º entones el punto estará
       'dentro del poligono
       'Si el angulo es 0 grados estará fuera.
       'Como se han podido acumular pequeños errores al hacer
       'los calculos establecemos que si el valor absoluto
       'de los grados es menor de 180 esta fuera (realmente
       'será cercano a 0º) y si no dentro (estará cercano a 360)

       Return Math.Abs(a.Grados) > 180

   End Function


Vertices es una lista de Point. Como ves el algoritmo es muy simple.

Te copio tambien el código para calcular el angulo de dos vectores.

Código [Seleccionar] Expand



   ''' <summary>
   ''' Devuelve el angulo que forman los dos vectores expresado en radianes
   ''' </summary>
   ''' <param name="v1"></param>
   ''' <param name="v2"></param>
   ''' <returns>El angulo expresado en radianes</returns>
   ''' <remarks></remarks>
   Public Shared Function Angulo(ByVal v1 As Vector, ByVal v2 As Vector) As Angulo
       If Vector.ModuloDelProductoVectorialConSigno(v1, v2) > 0 Then
           Return New Angulo(Math.Acos((Vector.ProductoEscalar(v1, v2) / (v1.Modulo * v2.Modulo))))
       Else
           'Si el modulo del producto vectorial es negativo
           'el angulo será negativo
           Return New Angulo(-1 * Math.Acos((Vector.ProductoEscalar(v1, v2) / (v1.Modulo * v2.Modulo))))
       End If

   End Function



[Pogacha]

Detección de un punto dentro de un polígono irregular no convexo y sin agujeros.

Se asume que:
    - El polígono esta formado por una lista circular de vértices.
    - Tiene sus vértices ordenados en un sentido conocido.

Se crea una lista circular de referencia externa a los vértices manteniendo   el orden.
Mientras halla mas de tres vértices en la lista (caso contrario el punto externo no esta en el polígono).
Tomar un pivote arbitrario (el primer elemento de la lista esta bien), y sus dos siguientes para formar un triángulo manteniendo el orden.
Tomar el siguiente como pivote y sus correspondientes siguientes mientras este triángulo no tenga el mismo sentido que el polígono.
Si para todos los lados del triángulo se cumple que el triángulo formado por los dos vértices del lado y el punto externo tiene el mismo sentido que el polígono entonces se puede salir del bucle con la seguridad de que el punto esta dentro del polígono.
En caso de que no, retirar el pivote de la lista y reiterar.

Para saber el sentido de un triángulo:

Siendo A, B y C vectores en R2 para formar el triángulo ABC:
Lado = (A-C) . Ortogonal(B-C) > 0.0f
Ortogonal del vector (x,y) es igual a (y,-x) o (-y,x)

Saludos!

[gdl]

Tengo otra propuesta que podría ser más comprensible y quizás más fácil.

Se traza desde el punto una semirrecta hasta el infinito (las horizontales o verticales serán más fáciles) y se calcula el número de segmentos del polígono que corta.

Si es impar, el punto está dentro. Si es par, está fuera.

Existe un problemilla si la semirrecta pasa justamente por un vértice. En ese caso lo más fácil es mover el vértice para que no corte con la semirrecta y se obtiene el resultado correcto.

[Pogacha]

Interesante modo de verlo y bien fundado geométricamente.

Con una semirrecta, simplificas la matemática operacional ya que un producto interno tiene una componente 0.

Sean A y B el lado y C el punto en cuestión:

Intersección de lado = Lado(A,B,C) && (A.y>=C.y) == (B.y<C.y)

Comparando A.y como >= y B solo como < se evita el problema de colinealidad con un vértice.

Ahora se debería contemplar los casos especiales para los lados paralelos y colineales a la semirrecta construida (A.y == C.y && B.y == C.y).
Si la caja de contención del lado se encuentra fuera de la semirrecta el lado no suma a la cantidad de  intersecciones.
Suponiendo que la semirrecta fuese dirigida a la izquierda, con un C.x<Min(A.x, B.x) andaría.

Aquí la implementación del código de gdl, pues me ha gustado mucho:

Código [Seleccionar] Expand

struct Vector2 {
  float x, y;

  Vector2(float _x, float _y) : x(_x), y(_y) {}

  Vector2 Ortogonal() const { return Vector2(-y,x); }
  float Punto(const Vector2& v) const { return x*v.x + y*v.y; }
};

bool Lado(const Vector2& A, const Vector2& B, const Vector2& C)
{
 Vector2 i(A-B);
 Vector2 j(C-B);

 Vector2 n = j.Ortogonal();

 return i.Punto(n)>0.0f;
}

bool Punto_En_Poligono(const Vector2& C, const Vector2 Poligono[], const int n)
{
 int n_Intersecciones = 0;

 Vector2& A = Poligono[n-1];
 Vector2& B;

 for(i = 0; i<n; ++i)
 {
    B = A;
    A = Poligono[i];

    if( min(A.x, B.x) < C.x)
    {
       // en realidad esto se podria contraer en un solo if pero no quiero ofuscarlo
        if((A.y>=C.y) == (B.y<C.y) && Lado(A,B,C)) n_Intersecciones++;
           else
        if(A.y == C.y && B.y == C.y) n_Intersecciones++;
    }
 }
 return (n_Intersecciones&1)==1; // o (n_Intersecciones%2)==1
}

La precisión de éste método es ligeramente menor que el anterior. El peligro de fallar esta en cuando haya lados muy cercanos a ser colineales con la semirrecta, ahí la matemática sufre las imprecisiones y un punto en el centro del polígono puede ser considerado fuera. En el método que yo propuse dando un epsilon (arbitrario minúsculo) de error a la función Lado, el punto no escapara nunca del polígono, cuando este muy cerca (tan cerca como epsilon) también sera tomado dentro.

De todas formas, si los vértices del polígono usan números enteros ya no hay de que preocuparse.

Saludos!