Jak sprawdzić, czy punkt (x, y) jest wewnątrz wielokąta w układzie współrzędnych kartezjańskich?

Question

To pytanie ma już odpowiedź tutaj:
Point in Polygon aka hit test
C# Point in polygon

Biorąc losowy wielokąt formułowane z równań liniowych N w kartezjańskim układzie współrzędnych, czy istnieje standardowa formuła, która jest wykorzystywane do sprawdzania członkostwa w punkcie (x, y)?

Proste rozwiązanie polega na uzyskaniu wszystkich wzorów liniowych i sprawdzeniu, czy punkt X znajduje się poniżej tej linii, powyżej tej linii i na prawo od drugiej linii itp. Prawdopodobnie będzie to jednak żmudne.

Należy zauważyć, że wielokąt może mieć dowolny kształt z dowolną liczbą boków i może być wklęsły lub wypukły.

Dla wygody już dodany te funkcje użytkowe:

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

Jeśli masz wierzchołki, można obliczyć sumę kątów wykonanych pomiędzy punktem kontrolnym i każdej pary punktów tworzących wielokąt. Jeśli jest to 2 * pi, to jest to punkt wewnętrzny. Jeśli jest 0, to jest to punkt zewnętrzny.

Niektóre kodu:

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

Źródło: http://paulbourke.net/geometry/insidepoly/

Inne miejsca, można spojrzeć na: 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