<알고리즘에 대한 정보는 http://geomalgorithms.com/a03-_inclusion.html를 많이 참고하였다.>
점 P가 주어질 때 다각형 내부 또는 외부에 속해있는 지 판별하는 알고리즘이다.
1) Crossing number algorithm
2) Winding number algorithm
크게 위의 두 가지 알고리즘으로 구현할 수 있다.
<Crossing number algorithm>
Crossing number algorithm은 점 P에서 반직선을 그어 다각형의 변과 접하는 횟수를 계산해
짝수면 외부, 홀수면 내부로 판별하는 알고리즘이다.
다각형의 경계선(boundary)은 다각형을 내부에서 외부로 분리해주는 역할이기 때문에
이 알고리즘은 보다 직관적으로 이해할 수 있다.
홀짝만 판단하기 때문에 구현또한 쉬울것 같지만 여러 예외상황이 존재한다.
1) 점P의 반직선이 다각형의 한점에서 접점하는 경우
위의 경우가 이에 해당된다.
CN 알고리즘은 다각형의 경계선과의 접점횟수로 결과를 내기 때문에
위와같이 다각형의 한 점에서 접점하는 경우 판단하기 힘들다.
2) non-simple 다각형내에 점P가 존재하는 경우
이와 같은 경우도 엄밀히 말하면 점P는 다각형 내부에 포함되어 있지만 외부로 판단된다.
3) 점P의 반직선과 다각형의 경계선이 수평으로 접하는 경우
이와 같은 경우도 수평으로 접하는것을 한번의 횟수로 단정짓기 어렵다.
이러한 예외경우를 없애기 위해 Edge Crossing Rule이라는 규칙을 정의한다.
- upward edge 시작점은 포함, 끝점은 배제
- downward edge 시작점은 배제, 끝점은 포함
- 반직선과 수평선은 배제
- edge-ray 교차점은 점 P의 오른쪽에 위치한 점으로만 정의됨
위의 규칙에 따르면 simple polygon에 대해서는 point in polygon 문제를 해결할 수 있다.
[출처]
http://geomalgorithms.com/a03-_inclusion.html
