다각형 내의 체크 포인트

Question

int pnpoly(int npol, float *xp, float *yp, float x, float y) 
{ 
    int i, j, c = 0; 
    for (i = 0, j = npol-1; i < npol; j = i++) { 
    if ((((yp[i] <= y) && (y < yp[j])) || 
     ((yp[j] <= y) && (y < yp[i]))) && 
     (x < (xp[j] - xp[i]) * (y - yp[i])/(yp[j] - yp[i]) + xp[i])) 
     c = !c; 
    } 
    return c; 
} 

이 기능은 점이 다각형 내에 있는지 확인합니다. 네거티브 인 다각형 좌표는 어떻게 처리합니까? 예를 들어,

float x[3] = { 0.16, 1.2, -10 }; 
float y[3] = { 1.8, 10, -5.5 }; 

나는 다각형 내의 유효한 지점을 확인 시도하고 0

Answer 1

대부분의 경우에 사용되는 iSurfer

두 가지 방법에서 꽤 좋은 구현이있다 반환 (그리고 내가 아는 2)은 교차 번호 및 권선 번호입니다. 둘 다 다각형/포인트 좌표의 부호의 영향을받지 않습니다. 따라서 코드에서 버그가 발생해야합니다. 난 당신이 코드에서 교차 번호로 발생할 수

// a Point is defined by its coordinates {int x, y;} 

// isLeft(): tests if a point is Left|On|Right of an infinite line. 
// Input: three points P0, P1, and P2 
// Return: >0 for P2 left of the line through P0 and P1 
//   =0 for P2 on the line 
//   <0 for P2 right of the line 
// See: Algorithm 1 "Area of Triangles and Polygons" 
inline int isLeft(Point P0, Point P1, Point P2) 
{ 
    return ((P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y)); 
} 
//=================================================================== 

// cn_PnPoly(): crossing number test for a point in a polygon 
//  Input: P = a point, 
//    V[] = vertex points of a polygon V[n+1] with V[n]=V[0] 
//  Return: 0 = outside, 1 = inside 
// This code is patterned after [Franklin, 2000] 
int cn_PnPoly(Point P, Point* V, int n) 
{ 
    int cn = 0; // the crossing number counter 

    // loop through all edges of the polygon 
    for (int i=0; i<n; i++) { // edge from V[i] to V[i+1] 
     if (((V[i].y <= P.y) && (V[i+1].y > P.y))  // an upward crossing 
     || ((V[i].y > P.y) && (V[i+1].y <= P.y))) { // a downward crossing 
      // compute the actual edge-ray intersect x-coordinate 
      float vt = (float)(P.y - V[i].y)/(V[i+1].y - V[i].y); 
      if (P.x < V[i].x + vt * (V[i+1].x - V[i].x)) // P.x < intersect 
       ++cn; // a valid crossing of y=P.y right of P.x 
     } 
    } 
    return (cn&1); // 0 if even (out), and 1 if odd (in) 

} 
//=================================================================== 

특별한 경우를 뭘 하려는지 될 것으로 보인다 교차 번호 시험에 대한 코드를 배치하고있어 완성도를 들어

숫자 테스트는 광선이 다각형의 가장자리과 중첩 될 때입니다. 이 경우 교차로를 계산하는 방법이 다소 퍼지게됩니다. 그렇기 때문에 실제 교차로 수가 아닙니다. 반원을 가로 지른 수는입니다.

권수 테스트는이 점에 대해 더 강력합니다.