Welcome to Stratos!
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 AnguloEl 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
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;}
__________| * ________|| |_____| _____|| |_______|__________|
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;}
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; } ...}
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;}