Làm thế nào để kiểm tra xem một điểm (x, y) có nằm trong một đa giác trong hệ tọa độ Descartes không?

Question

Câu hỏi này đã có một câu trả lời ở đây:
Point in Polygon aka hit test
C# Point in polygon

Cho một đa giác ngẫu nhiên xây dựng với phương trình dòng N trong Descartes hệ tọa độ, là có bất kỳ công thức tiêu chuẩn đó là được sử dụng để kiểm tra thành viên của một điểm (x, y)?

Giải pháp đơn giản là lấy tất cả các công thức dòng và kiểm tra xem điểm X nằm dưới dòng này, phía trên dòng đó và bên phải của dòng khác, v.v. Nhưng điều này có thể sẽ tẻ nhạt.

Tôi nên lưu ý rằng đa giác có thể có hình dạng bất kỳ với bất kỳ số cạnh nào và có thể lõm hoặc lồi.

Để thuận tiện tôi đã thêm những chức năng tiện ích:

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

Nếu bạn có các đỉnh, bạn có thể tính tổng các góc độ thực hiện giữa các điểm thử nghiệm và mỗi cặp điểm chiếm đa giác. Nếu nó là 2 * pi, thì đó là điểm nội tại. Nếu nó là 0, thì nó là một điểm bên ngoài.

Một số mã:

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

Nguồn: http://paulbourke.net/geometry/insidepoly/

nơi khác bạn có thể có một cái nhìn tại địa chỉ: 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