如何檢查點（x，y）是多邊形內部的直角座標系上？

Question

這個問題已經在這裏有一個答案：
Point in Polygon aka hit test
C# Point in polygon

鑑於笛卡爾與N線方程制定座標系統隨機多邊形，有沒有標準公式是用於檢查點（x，y）的成員資格？

簡單的解決辦法是讓所有的線公式和檢查點X這條線之下，高於線和其他線路，等權但這可能會是乏味的。

我應該注意的是，多邊形可與任何數量的邊的任何形狀，並且可以凹面或凸面。

爲了方便我已經添加了這些實用的功能：

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

如果你有頂點，你可以計算測試點的每對點組成的多邊形之間所形成的角度的總和。 如果它是2 * pi，那麼它是一個內部點。如果它是0，那麼它是一個外部點。

一些代碼：

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

來源：http://paulbourke.net/geometry/insidepoly/

其它地方，你可以看看： 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