C 언어 로 이 루어 진 PNPoly 알고리즘 코드 예

C 언어 를 쓰 는 실험 에 사용 되 는 알고리즘 으로 한 점 이 다각형 내부 에 있 는 지 판단 합 니 다.C 의 코드 는 다음 과 같다.

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  for (i = 0, j = nvert-1; i < nvert; j = i++) {
    if ( ((verty[i]>testy) != (verty[j]>testy)) && 
      (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / 
      (verty[j]-verty[i]) + vertx[i]) )
      c = !c;
    }
  return c;
}

그 중에서 nvert 는 다각형 정점 의 개수 이 고 vertx 와 verty 는 각각 다각형 정점 횡,세로 좌표 의 배열 이 며 textx 와 testy 는 측정 점 의 좌표 이다.이 알고리즘 은 W.Randolph Franklin 이 제기 한 것 이다.Jordan curve theorem 에 따 르 면 다각형 은 평면 을 내외 두 구역 으로 나 누고 측정 점 이 다각형 내부 에 있다 고 가정 하면 측정 점 에서 하나의 방사선 을 끌 어 내 면 반드시 다각형 과 적어도 하나의 교점 이 있 을 것 이다.이 방사선 은 다각형 과 처음 교차 할 때 다각형 을 뛰 쳐 나 가 고 두 번 째 교차 할 때 다각형 에 들 어 갈 것 이다.이런 유추 에 따 르 면 방사선 과 다각형 에 홀수 교점 이 있 으 면 이 점 은 다각형 내부 에 있 고 그렇지 않 으 면 외부 에 있다.
PNPoly 알고리즘 은 바로 측정 대기 점 에서 수평 에서 오른쪽으로 방사선 을 끌 어 내 고 다각형 과 의 교점 개 수 를 계산한다.이 코드 설명:for(i=0,j=nvert-1;i < nvert; j=i++)순환 의 의 미 는 j=i C 1 을 처음부터 끝까지 i=0 이면 j=nvert C 1 로 다각형 의 각 변 을 차례대로 검사 하 는 것 이다.다음 포 인 트 는 조건문,(verty[i]>testy)!=(verty[j]>testy)는 이해 하기 쉽다.바로 한 변 의 두 정점 이 각각 측정 대기 점 의 위 와 아래 에 있다 는 것 이다.이 문 구 를 통 해 측정 대기 점 에서 오른쪽으로 끌 어 내 는 방사선 이 이 변 과 교차 할 수 있다 는 것 을 알 수 있다.
구체 적 인 판단 은 해석 기하학 에 맡 겨 야 합 니 다.건 계 는 이 변 이 있 는 직선 방정식 을 쓴다.

변형:

측정 대기 점 좌 표를 대 입 하여 도형 관계 에 따라 이 부등식 을 얻 을 수 있 습 니 다.

즉,testx