Come verificare se un punto (x, y) si trova all'interno di un poligono nel sistema di coordinate cartesiane?

Question

Questa domanda ha già una risposta qui:
Point in Polygon aka hit test
C# Point in polygon

Dato un poligono casuale formulato con equazioni linea n nel sistema di coordinate cartesiane, v'è alcuna formula standard che è usato per verificare l'appartenenza a un punto (x, y)?

La soluzione più semplice è quello di ottenere tutte le formule di linea e verificare se il punto X è al di sotto di questa linea, sopra quella linea ea destra dell'altra linea, ecc Ma questo sarà probabilmente noioso.

Devo notare che il poligono può essere di qualsiasi forma con qualsiasi numero di lati e può essere concavo o convesso.

Per comodità ho già aggiunto queste funzioni di utilità:

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

Se avete i vertici, è possibile calcolare la somma degli angoli realizzati tra il punto di prova e ogni coppia di punti che compongono il poligono. Se è 2 * pi, allora è un punto interno. Se è 0, allora è un punto esteriore.

Alcuni codice:

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); 
} 

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

Altri posti si può dare un'occhiata 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