¿Cómo verificar si un punto (x, y) está dentro de un polígono en el sistema de coordenadas cartesianas?

Question

Esta cuestión ya tiene una respuesta aquí:
Point in Polygon aka hit test
C# Point in polygon

Dado un polígono aleatorio formulado con N ecuaciones de línea en el sistema de coordenadas cartesianas, hay alguna fórmula estándar que es utilizado para verificar la membresía de un punto (x, y)?

La solución simple es obtener todas las fórmulas de línea y verificar si el punto X está debajo de esta línea, encima de esa línea ya la derecha de la otra línea, etc. Pero esto probablemente sea tedioso.

Debo notar que el polígono puede tener cualquier forma con cualquier número de lados y puede ser cóncavo o convexo.

Por conveniencia ya han añadido estas funciones de utilidad:

float slope(CGPoint p1, CGPoint p2) 
{ 
    return (p2.y - p1.y)/(p2.x - p1.x); 
} 

CGPoint pointOnLineWithY(CGPoint p, float m, float y) 
{ 
    float x = (y - p.y)/m + p.x; 
    return CGPointMake(x,y); 
} 

CGPoint pointOnLineWithX(CGPoint p, float m, float x) 
{ 
    float y = m*(x - p.x) + p.y; 
    return CGPointMake(x, y); 
} 

Answer 1

Si usted tiene los vértices, se puede calcular la suma de los ángulos formados entre el punto de prueba y cada par de puntos que forman el polígono. Si es 2 * pi, entonces es un punto interior. Si es 0, entonces es un punto exterior.

Algunos código:

typedef struct { 
    int h,v; 
} Point; 

int InsidePolygon(Point *polygon,int n,Point p) 
{ 
    int i; 
    double angle=0; 
    Point p1,p2; 

    for (i=0;i<n;i++) { 
     p1.h = polygon[i].h - p.h; 
     p1.v = polygon[i].v - p.v; 
     p2.h = polygon[(i+1)%n].h - p.h; 
     p2.v = polygon[(i+1)%n].v - p.v; 
     angle += Angle2D(p1.h,p1.v,p2.h,p2.v); 
    } 

    if (ABS(angle) < PI) 
     return(FALSE); 
    else 
     return(TRUE); 
} 

/* 
    Return the angle between two vectors on a plane 
    The angle is from vector 1 to vector 2, positive anticlockwise 
    The result is between -pi -> pi 
*/ 
double Angle2D(double x1, double y1, double x2, double y2) 
{ 
    double dtheta,theta1,theta2; 

    theta1 = atan2(y1,x1); 
    theta2 = atan2(y2,x2); 
    dtheta = theta2 - theta1; 
    while (dtheta > PI) 
     dtheta -= TWOPI; 
    while (dtheta < -PI) 
     dtheta += TWOPI; 

    return(dtheta); 
} 

Fuente: http://paulbourke.net/geometry/insidepoly/

Otros lugares que puede echar un vistazo a: http://alienryderflex.com/polygon/

http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html

http://sidvind.com/wiki/Point-in-polygon:_Jordan_Curve_Theorem