in 포스트 |

다각형 내부의 점 판단하기 (Point in Polygon)

Dan Sunday 의 저술 번역.

http://geomalgorithms.com/a03-_inclusion.html

I_Jemin 역주:

  • Edge는 (폴리곤의) 변 혹은 경계선이라고도 번역 가능. 이 문서는 방향성을 통일하기 위해 Edge를 경계선이라는 번역으로 통일함.
  • Polygon 또한 다각형 보다는, 그래픽 프로그래밍 현장에서 폴리곤이 더 흔한 표현이므로 폴리곤이라 번역.
  • Simple Polygon 간단한 폴리곤: 서로를 가로지르는 변이 없는 다각형.
  • Monotone Polygon 모노톤 폴리곤: 평행한 직선들을 열거해서 폴리곤으로 쏘았을때 각 직선들에 대한 모든 교차점이 2를 넘지 않는 폴리곤. 아래 이미지 참조.
    440px-M-polygon.svg
  • The crossing number (교차하는 횟수)는 (점에서 출발한 레이가) 경계선을 몇번 교차해 넘어가는 지, 그 횟수를 뜻함.
  • The winding number (감아도는 횟수) 는 (점의 바깥을) 몇개의 닫힌 선(= 시작점과 끝점이 일치하는 폴리곤)으로 감싸 둘러지고 있는지, 그 횟수를 뜻함.
  • 양의 레이는 수평 좌표계를 기준으로 양의 방향으로 향하는 레이를 뜻함.
  • 상승하는 경계선이란 수직 좌표계를 기준으로 경계선(변)을 그리는 벡터가 양의 방향임을 뜻함.
  • 경계선-레이 간의 교차에서 양(+1)/음(-1)이란, 수직-수평 좌표계에서 오른쪽과 위쪽이 양이며, 폴리곤을 반시계 방향으로 그려나간다고 할때:
    경계선을 그리는 방향벡터를 기준으로 봤을때 오른쪽으로 레이가 교차할 경우 양이라 판단하면 된다.
  • 결론적으로 이문서에서 the winding number를 알아내는 방법은, 위 항목의 판별법을 기준삼아, 해당 점에서 출발한 레이가 (닫힌) 폴리곤의 경계선과 교차할 때마다 해당 교차가 양(+1)인지 음(-1) 인지 판단해 그 값을 계속 누적한 결과 값이다.
  • 볼록 폴리곤 (Convex Polygon)은 모든 꼭지점 각이 180도보다 어떤 점이 안쪽으로 움푹 들어간 형상을 띄지 않는 다각형. 아래 이미지 참고.
    볼록 폴리곤은 도형을 한붓 긋기로 그린다고 할때 늘 같은 방향으로 (시계방향이든 반시계 방향이든) 그어가며 경계선들을 그릴수 있다.
    그러므로 점의 포함 여부를 판단할때 레이와의 교차 방향을 검사 하는 연산을 좀더 최적화 시킬 수 있는 여지가 있음.
    convex_concave
  • 윤곽~(Bouding XXX)에서, 윤곽 박스(Bouding Box)란 박스 모양으로, 대상 도형의 전체를 감쌀수 있는 최소한의 영역을 가진 도형을 말한다. 마찬가지로 윤곽 볼(Bounding Ball)이란 해당 도형을 최소 영역으로 감싸는 원이다. 아래 그림 참고.
    tmp74705_thumb

 

다각형 내부의 점 판단하기

(Inclusion of a Point in a Polygon)

 

2D상 평평한 폴리곤에서 점 P의 포함여부를 판단하는 것은 흥미로운 알고리즘을 나타내는 기하학 문제다. 여기서 자주 쓰이게 되는 두가지 방법은:

  1. The Crossing Number (cn) 교차한 횟수 방법
    – 점 P에서 출발한 레이(직선, 광선 ;Ray) 가 폴리곤 경계선을 몇번 교차해 가는지 세는 것. “교차해간 경계선 수”가 짝수 일때 이 점은 바깥에 존재한다; 다른 경우엔, 홀수 일땐, 점은 내부에 있다. 이 방법은 “짝-홀” 테스트라고 불리기도 한다.
  2. The Winding Number (wn) 감싸는 횟수 방법
    – 점 P를 폴리곤이 몇번 감아 도는지 세는 것. “감싸도는 횟수” wn = 0일때에만 점은 바깥에 존재한다; 다른 경우, 점은 내부에 있다.

만약 폴리곤이 간단하다면 (예로, 스스로 겹치는 경우가 없음), 이 두방법은 모든 점들에 대해 같은 결과를 줄것이다. 하지만, 복잡한 폴리곤들에 대해선, 두가지 방법들은 같은 점들에 대해 다른 답을 줄 수 있다. 예를 들어, 폴리곤이 스스로를 덮어 겹치고 있을때, 겹친 영역의 이 점들은 The Crossing Number을 사용한 경우 바깥에 있다고 나오지만, The Winding Number를 사용할시 내부에 존재한다. 아래의 다이어그램에 나타난 것 처럼.

cn0

Crossing Number Method

wn

Winding Number Method

꼭지점들에 숫자를 이렇게 매긴다 : 0 1 2 3 4 5 6 7 8 9

이 예에서, 겹친 영역에서의 점들은 wn = 2를 가지며 폴리곤안에 두번 중복해서 내부에 위치함을 나타낸다. 즉, The Winding Number은 The Crossing Number 보다 더 직관적인 답을 준다.

하지만 The Crossing Number 방법이 더 범용적으로 사용된다. 왜냐면 cn은 wn보다 (무려 20배나!) 엄청 성능이 좋다고 잘못 여겨졌기 때문이다.[O’Rourke, 1998]. 하지만 이 경우엔 그렇지 않고, 교차에 부호를 붙여(signed crossing) 셈으로서, wn은 cn과 같은 효율로 계산될 수 있다. 사실, 우리가 wn_PnPoly()에서 구현한 것은 [Franklin, 2000], [ Haines, 1994] or [O’Rourke, 1998]에서 cn을 위해 제시된 코드들 보다 빠르다.  다만 [Moller & Haines, 1999]에서의 “PointInPolygon()” 루틴으로 cn을 구하는 방법은 우리 wn 알고리즘의 경쟁상대가 될수 있겠다. 하지만 결론적으로, 기하학적 정확도와 효율성을 위해, 폴리곤 내부에 점이 위치하는지 판단할때 언제나 wn 알고리즘이 우선 선호되야 한다.

 

The Crossing Number

이 방법은 P점에서 출발한 레이가 내부와 외부를 구별해주는 폴리곤 경계를 몇번 교차해 넘는지 갯수를 센다. 만약 그 수가 짝수면,해당 점은 외부에 있고; 다른 경우, 교차 횟수가 홀수인 경우, 점은 내부에 있다. 이 방법은 쉽게 바로 이해할 수 있다. 폴리곤의 경계를 레이가 교차할때 마다, 내부-외부를 나타내는 패리티가 바뀐다. (왜냐면 경계선이라는 것은 언제나 내부와 외부 사이에 있으니까. 이해가지?) .

어떻게든 레이는 폴리곤 경계를 넘어 그 밖으로 나가게 된다. 그러니, 만약 점이 내부에 있다면, 경계 “>”를 넘나드는 것을 이렇게 나열할 수 있다: 내부 > 외부 > … > 내부 > 외부.

그리고 그 넘어간 경계”>”의 합은 홀수가 된다.

같은 원리로, 만약 점이 바깥에 있다면, 짝수번 경계를 넘나드는 시퀀스는: 외부 > 내부 > .. > 내부 > 외부 이렇게 된다.

cn1

cn 방법의 알고리즘을 구현할 때는, 한가지 명심할게 있다. 내부-외부 패리티를 뒤집어주는 교차에 대해서만 숫자를 세어야 한다. 특히, 레이가 꼭지점을 통과해버린 예외적인 경우에 대해 반드시 적절한 처리를 해야 한다. 여기엔 아래와 같은 경우의 레이 교차도 포함된다:

cn2

게다가, 폴리곤 위에 있는 점이 내부인지 외부인지 반드시 정해야 한다. 일반적인 관례로는 왼쪽이나 아래쪽 경계에 걸친 점은 내부로, 오른쪽이나 위쪽 경계에 걸친것은 바깥으로 본다. 이렇게 하면, 만약 두개의 다른 폴리곤들이 공통 경계 세그먼트를 공유한다면, 그 세그먼트에 있는 해당점은 한 폴리곤에 대해서는 내부지만, 동시에 둘 모두에 대해서는 내부에 있지 않게된다. 이런식으로 발생할수 있는 수많은 문제점들을 회피한다. 특히 컴퓨터 그래픽 표현에서.

직설적인 “교차 회수” 알고리즘은 P의 우측으로 펼쳐지는 수평 레이를 선택하고, x축 양의 방향에 평행하게 전개한다. 이 특수한 레이를 사용하면, 교차한 폴리곤 경계들을 쉽게 계산할 수 있다. 게다가 어떠한 교차도 발생할 수 없는 경우에서는 결과내기가 더욱 쉽다. 총 교차 횟수 cn을 세기 위해, 이 알고리즘은 간단하게 그저 폴리곤의 모든 경계를 루프해 넘어가면서, 각 교차에 대해 검증하고, 교차가 발생시 cn 값을 늘린다. 덧붙여, 교차에 대한 검증시, 경계선 위에 점이 있는 경우와 다른 예외적인 경우들에 대해서 반드시 적절히 처리해야 한다. 이는 아래 방법으로 할 수 있다.

경계를 교차할때 규칙

  1. 위쪽 경계선에는 처음 끝점은 포함되고 마지막 끝점은 제외된다.
  2. 아래쪽 경계선에는 처음 끝점은 제외되고 마지막 끝점은 포함된다.
  3. 수평 경계선들은 다루지 않는다.
  4. 경계선-레이의 교차 지점은 정확하게 점 P의 오른쪽 방향에서만 존재해야 한다.

이러한 규칙을 예외적인 경우를 처리하기 위해 적용할 수 있으며, 유의미한 교차들을 정확히 판단할 수 있을 것이다.  알아둘건, 4번째 규칙은 오른쪽 경계선에 걸친 점들은 외부로 취급되고, 왼쪽 경계에 걸친 점들은 내부로 취급되는 결과를 준다.

의사 코드: Crossing # Inclusion

이 알고리즘을 위한 코드는 잘 알려져 있다. 그리고 경계 교차 규칙은 표현하기도 쉽다. 폴리곤은 V[n]=V[0]인 버택스 정점들의 배열 V[n+1]로 표현하는 대표적인 구현 로직 ([Franklin, 2000], [O’Rourke, 1998]) 은 아래와 같다.

 

typedef struct {int x, y;} Point;

cn_PnPoly( Point P, Point V[], int n )
{
    int    cn = 0;    // the  crossing number counter

    // loop through all edges of the polygon
    for (each edge E[i]:V[i]V[i+1] of the polygon) {
        if (E[i] crosses upward ala Rule #1
         || E[i] crosses downward ala  Rule #2) {
            if (P.x <  x_intersect of E[i] with y=P.y)   // Rule #4
                 ++cn;   // a valid crossing to the right of P.x
        }
    }
    return (cn&1);    // 0 if even (out), and 1 if  odd (in)

}

위쪽과 아래쪽의 교차에 대한 검증이 규칙 #1과 #2를 만족한다는 사실과 수평 경계선들은 제외한다는 것(규칙 #3)에 주목해라. 모든게 여기 다 들어 있다. 많은 일들이 몇가지 테스트 만으로 수행하기에 이 알고리즘은 아름답다.

하지만, the crossing number 방법에 대한 검증이 “Jordan Curve Theorem”에 기반하는데, 이는 간단한 형태로 닫힌 곡선이 2D 평면을 정확하게 서로 접하는 두부분으로 나눈다고 본다: 경계가 존재하는 “내부”쪽과 경계가 없는 “외부” 쪽으로. 이말은 해당 곡선는 반드시 간단한 형태여야하며 (스스로를 교차하지 말아야하며), 그렇지 않다면 나누어진 부분이 2개보다 많아질것이다. 그러면 경계를 넘는 것이 내부-외부 패리티를 바꾼다고 보장할 수 없다. 닫혀있는 (그리고 경계가 존재하는) 곡선에게는, 단 하나의 경계가 없는 “외부” 부분만 달려온다; 하지만 경계가 존재하는 부분은 내부일수도 있고 외부일수도 있다. 그리고 어떤 경계를 공유하는, 경계가 있는 두개의 부분이, 둘다 내부일수도 있으며, 그리고 그들이 공유하는 경계선을 넘는 것은 내부-외부 패리티를 바꾸지 못한다.

 

The Winding Number

반면에, the winding number는 복잡한 닫힌 폴리곤 내부에 점이 있는지 정확하게 판단한다.

이는 폴리곤이 점을 감싸고 있는지 계산함으로 이루어진다.폴리곤이 점을 전혀 감싸고 있지 않을때, 즉  the winding number 인 wn=0 일때 점은 외부에 있다.

좀더 일반적으로 보면, 2D 평면에서 점 P을 두르고 있는, 어떠한 닫혀있는 연속적인 곡선 C에 대한 wn(P,C) 를 정의할 수 있다.
이 연속적인 2D 곡선 C를,  u.ge-0.le-1일때 C(0)=C(1) 인, 점들 C(u)=(x(u),y(u)) 들로 정의하자.

그리고 점 P가 C위에 있지 않다고 하자. 그러고나서, P에서 C(u)로 향하는 벡터 c(P,u) = C(u) – P 와 단위 벡터 w(P,u) = c(P,u) / |c(P,u)|  를 정의한다. 이로서 C위의 점 C(u)에서, 단위원 S1={(x,y).st.x2+y2=1}위의 w(P,u)로 향하는 C(u)를 그리는 연속 함수 W(P)=C-map-S1 를 얻을 수 있다.

theta(u)가 시계반대 방향으로의 각도가 양인 라디안인 곳에서, W(P)(u)=(cos-theta(u),sin-theta(u) 로서 보간 좌표들로 표현할수도 있다. the winding number 인 wn(P,C)는 W(P)가 S1 를 둘러 C를 감싸덮는 횟수를 나타내는 정수와 같다. 이는  S1 에 대한 연속 변형 함수 (호모토피; homotopy class)와 일치하며, 적분으로 계산할 수 있다:

wn_integral

 

곡선 C가 정점 V0,V1,…,Vn = V0 로 이루어진 폴리곤일때, 이 적분은 해당 점P와 대응하는 각각의 경계선 ViVi+1 의 (부호가 붙은) 각도들의 합으로 줄어든다. 즉, 만약 theta-i=angle(PV-i,PV-i+1) 이라면, 우리는 아래와 같은 결과를 얻는다:

wn_sumwn1

이 공식은 비싼 계산비용의 삼각 함수 acrcos() 를 사용하기에 분명이 그리 효율적이지 못하다. 하지만, 간단히 관찰해보면, 우리는 이 공식을 더 효과적인 것으로 교체할 수 있다.   S1에 있는 아무점 Q를 선택하자. 그리고 곡선 W(P)가 S1 을 감쌀때 Q를 특정 횟수 통과했을 것이다. Q를 시계 반대 방향으로 통과할때 마다 (+1)해서 세고, 시계방향으로 통과할 때는 (-1)해서 센다고 하면, 최종적인 합은 W(P)가 S1 을 감싸고 있는 횟수와 정확이 일치할 것이며, the winding number인 wn(P,C)가 된다.

게다가, 만약 우리가 무한한 레이 R을 P에서 시작해서 벡터 Q의 방향으로 확장한다면, R이 곡선 C를 교차하는 교차점들은 Q를 통과하는 W(P)와 일치할 것이다. 이런식으로 계산하기 위해선, C가 R을 교차할때 오른쪽에서 왼쪽으로 인지, 왼쪽에서 오른쪽인지, 양의 방향 교차와 음의 방향 교차를 반드시 구별해야 한다.

이는 C로 향하는 법선 벡터와 방향벡터 q = Q 를 스칼라곱(dot product)한 것의 부호를 보고 판단할 수 있다.[Foley et al, 1996, p-965]

그리고 곡선 C가 폴리곤일때, 각 변에 대해 한번씩은 이러한 판별을 해줘야 한다. P에서 출발하는 수평 레이 R에 대해서는, 경계선의 끝점이 레이 위에 있는지 아래에 있는지 테스트하면 충분하다. 만약 경계선이 아래에서 위로 양의 레이를 교차한다면, 그 교차는 양 (+1)이며, 만약 위에서 아래로 교차한다면, 해당 교차는 음(-1)이다. 그리고 나서 wn(P,C)을 구하기 위해 이들 교차 값들을 모두 더해주면 된다. 예를 들어:

wn2

추가적으로,  isLeft() 속성자를 사용하면 경계선-레이 교차점을 실제로 계산하는 비용을 회피할수있다; 하지만, 이는 경계선이 상승인지 하강인지에 따라 다르게 적용된다. 만약 상승하는 경계선이 P의 우측으로 향하는 레이를 교차한다면, P는 경계선의 왼쪽에 있는 것이다. 왜냐하면 삼각형 ViVi+1P은 시계반대 방향으로 그려지기 때문이다. 반대로, 하강하는 경계가 양의 레이를 교차할때 P는 우측에 있을것이다. 왜냐하면 삼각형 ViVi+1P은 시계방향으로 그려지니까.

 

의사코드: Winding Number Inclusion

위는 다음의 cn알고리즘 파생형인 wn 알고리즘을 도출하고, 예외적 경우를 처리하기 전에 같은 경계를 교차할때 규칙을 사용한다.

typedef struct {int x, y;} Point;

wn_PnPoly( Point P, Point V[], int n )
{
    int    wn = 0;    // the  winding number counter

    // loop through all edges of the polygon
    for (each edge E[i]:V[i]V[i+1] of the polygon) {
        if (E[i] crosses upward ala Rule #1)  {
            if (P is  strictly left of E[i])    // Rule #4
                 ++wn;   // a valid up intersect right of P.x
        }
        else
        if (E[i] crosses downward ala Rule  #2) {
            if (P is  strictly right of E[i])   // Rule #4
                 --wn;   // a valid down intersect right of P.x
        }
    }
    return wn;    // =0 <=> P is outside the polygon

}

분명이, 이 winding number 알고리즘은 crossing number 알고리즘과 같은 효율을 가진다. 따라서, 보통 이쪽이 더 정확하므로, 임의의 폴리곤에 대해 점이 내부에 있는지 판별할때는, the winding number 알고리즘이 우선 고려되야 한다.

게다가 wn 알고리즘의 효율성은 교차 비교 검증을 재배열함으로써 더 개선될 수 있다. 이는 아래에 주어진 wn_PnPoly() 의 상세한 구현부에 나타나있다. 해당 코드에서, 완전이 P 위에 있는 혹은 완전이 P 아래에 있는 모든 경계선들은 단지 두번의 (2) 불일치 검증을 하고 바로 제외된다. 하지만, 현재 cn알고리즘의 일반적인 구현 ([Franklin, 2000], [ Haines, 1994], [O’Rourke, 1998]) 은 제외될 각각의 경계선들에 대해 최소한 세번은 (3) 불일치 검증을 사용한다. 실제 현장에서 사용될땐, 거대한 폴리곤에서 대부분의 경계선들은 제외될것이기에, 비교 연산의 수행횟수를 33% (혹은 더 많이) 줄일 수 있게 된다. 엄청나게 큰 (1,000,000 의 경계선을 가진) 임의의 (경계선의 길이가 경계선의 지름의 1/10인) 폴리곤과 (해당 폴리곤의 영역 내부에 있는) 1000개의 테스트용 무작위 점들을 이용한 런타임 테스트에서, 우리는 결론적으로 20%의 효율 상승을 측정했다.

향상

소프트웨어 개발자들이 반드시 알아야할, 폴리곤 내부의 점에 대한 알고리즘[Haines, 1994]을 향상시킬 수 있는 몇가지 방법이 있다. 우리는 레이 교차 알고리즘들과 관련된 부분에 대해 말했었다. 하지만, 삼각형과 같은 작은 볼록 폴리곤들에 예외적인 경우들에 대해 더 나은 성능을 낼 수 있는 몇가지 다른 기술들이 있다. 이는 [Haines, 1994]에 논의 되있다.

윤곽 박스 혹은 윤곽 볼

모든 경계선들에 대해 레이 교차를 검사해보기 전에, 거대한 폴리곤에 대한 윤곽 박스나 윤곽 볼 내부에 P가 존재하는지 검사하는게 효율적이다. 만약 점이 윤곽 박스나 윤곽 볼 외부에 있다면, 이는 폴리곤 외부에 있다는 뜻과 같으며, 이후 다른 검증들이 필요 없다는 의미다. 하지만, 윤곽 박스(정점 x와  y좌표들의 최소 값과 최대 값)이나 윤곽 볼(중점과 최소 반지름들)에 대해 반드시 선행계산 해야하고, 이후 사용하기 위해 저장해두어야 한다.  일반적인 경우인, 몇개 보다 조금 많은 점에 대해 포함여부를 검사하는 경우들에선 해볼만한 가치가 있다. 외곽 컨테이너를 연산하는 방법에 대한 더 자세한 정보는 Algorithm 8 에서 볼 수 있다.

3D의 평면 상 폴리곤들

3D 어플리케이션에선, 서로 같은 평면안에 있는 폴리곤과 점을 가지고 검사해보고 싶을 수 있다. 예를 들어, 어떤 다면체의 면을 포함하는 평면과 교차한 레이의 교차점이 존재할때, 그것이 해당 다면체 면의 내부에 있는 검사하고 싶을 수 있다.  아니면 어떤점에서 내린 3D상 수직선의 밑면이 어떤 평면 폴리곤 내부에 있는지 알고 싶을 수 있다.

3D 포함여부는 해당 점과 폴리곤을 2D에 투영함으로서 쉽게 판단할 수 있다. 이를 위해서는 간단히 3D 좌표 구성원소 중 하나를 무시해버리고 남은 두 원소를 사용하면 된다. 무시할 좌표 원소를 최적으로 선택하기 위해서, 해당 평면의 법선 벡터를 계산한 다음, 좌표의 원소중 가장 절대값이 큰 두개를 남긴다 [Snyder & Barr, 1987]. 이로서 해당 폴리곤에 대한 투영 중 가장 넓이가 큰 투영을 얻을 수 있고, 좀더 여유로운 연산을 할 수 있다.

볼록 폴리곤 혹은 모노톤 폴리곤

폴리곤이 볼록일때, 많은 연산들의 속도가 높아질 수 있다. 예를 들어, 볼록하지 않은 폴리곤은 O(n) 시간을 소요하는데 비해 O(log n) 시간 내에 외곽 박스를 계산할 수 있다 [O’Rourke, 1998] . 게다가, 점의 포함여부도 O(n) 시간 내에 검사할 수 있다. 일반적으로 아래의 알고리즘들은 볼록 폴리곤이나 모노톤 폴리곤들에 적용될 수 있다.

 

볼록 혹은 y축-모노톤 폴리곤들은 두 부분의 폴리라인으로 나눌 수 있다. 하나는 y값이 증가하는 방향의 경계선들과, 다른 하나는 감소하는 방향의 경계선들. y값이 가장 큰 정점과 y값이 가장 작은 정점을 기준으로 분리한다. 이 두 정점은 폴리곤 외곽 박스의 최상단과 최하단에 해당한다는 것과, 만약 둘다 점 P의 y좌표에 대해 모두 아래거나 모두 위인 경우,  검사할 점은 폴리곤 바깥에 있다는 것에 주의해라. 아니면, 이 두 폴리라인은 x 방향으로 평행한 레이와 각자 한번씩 교차하고, 교차가능한 각각의 경계선들은, 각각의 폴리라인의 정점들에 대해 바이너리 탐색을 해서 알아낼수 있다. 이는 볼록 폴리곤과 모노톤 폴리곤에 대한 포함여부 검사에서, 실제로 O(log n) (사전 처리와 런타임에서) 알고리즘을 도출해냈다. 예를 들어, 아래의 다이어그램에서, 각각의 폴리라인에 대해 필요한 정점에 대한 바이너리 탐색은 단 3회 였다. (A1,A2,A3는 상승; 그리고 B1,B2,B3는 하강):

게다가 이 방법은 임의의 방향에 대해 모노톤인 폴리곤에 대해서도 쓸 수 있다. 모노톤 기준 방향(the direction of monotonicity)에 수직으로 P에서 출발한 레이를 사용해서, 알고리즘을 쉽게 바꾸어 적용할 수 있다. 레이에서 어떤 쪽이 정점이 있는 곳인지 판단하기 위해 조금더 연산이 필요하지만, 충분이 거대한 폴리곤에 대해, 오버헤드없이 O(log n) 성능을 내준다.

구현

이 부분에는 폴리곤 내부의 점을 판별하는데에 대한 the winding number 알고리즘을 “C++” 로 구현하였다. 2D 에 대한 경우만 다루었고, 점과 폴리곤에 대해 최대한 간단한 구조로 다루었기때문에, 당신이 어플리케이션과는 구조가 다를 수 있다.

// Copyright 2000 softSurfer, 2012 Dan Sunday
// This code may be freely used and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.
 

// 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)

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


// wn_PnPoly(): winding 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:  wn = the winding number (=0 only when P is outside)
int
wn_PnPoly( Point P, Point* V, int n )
{
    int    wn = 0;    // the  winding 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) {          // start y <= P.y
            if (V[i+1].y  > P.y)      // an upward crossing
                 if (isLeft( V[i], V[i+1], P) > 0)  // P left of  edge
                     ++wn;            // have  a valid up intersect
        }
        else {                        // start y > P.y (no test needed)
            if (V[i+1].y  <= P.y)     // a downward crossing
                 if (isLeft( V[i], V[i+1], P) < 0)  // P right of  edge
                     --wn;            // have  a valid down intersect
        }
    }
    return wn;
}
//===================================================================

 

레퍼런스

James Foley, Andries van Dam, Steven Feiner &  John Hughes, “Filled Primitives” in Computer Graphics (3rd Edition) (2013)

Wm. Randolph Franklin, “PNPOLY  – Point Inclusion in Polygon Test” Web Page (2000)

Eric Haines, “Point in Polygon Strategies” in Graphics Gems IV (1994)

Tomas Moller & Eric Haines, “Ray/Polygon Intersection” in Real-Time Rendering (3rd Edition) (2008)

Joseph O’Rourke, “Point in  Polygon” in Computational Geometry in C (2nd Edition) (1998)

John M. Snyder & Alan H. Barr, “Ray Tracing Complex  Models Containing Surface Tessellations”, Computer Graphics 21(4), 119-126 (1987)  [also in the Proceedings of SIGGRAPH 1987]

 

I_Jemin에 의해 한국어로 번역되었으며, 오직 학문적 목적임을 밝힘. I_Jemin은 원문서에 대한 어떠한 권리도 가지고 있지 않다.

Translated for Korean by I_Jemin. Translation is done by only academic purpose. I_Jemin does not have any kind of rights to original document.