Point in a Polygon - 다각형 내부점 판단

문제마다 다각형 내부점이 되는 기준이 다 다르다

지금 정리하는 기준은 다각형의 선분위에 있는 점 또한 내부점으로 판단한다고 가정한다

 

주어진 점이 다각형의 내부점이 되는지 안되는지 파악하기 전에 

이 다각형을 시계방향이든 반시계방향이든 정렬해서 선분으로 사용할 수 있도록 만들어 놓아야 한다

좌표정렬 : https://junho0956.tistory.com/285?category=879042

 

좌표를 정렬했으니 내부점 판단에 대한 정리 ㄱㄱ

 

베이스는 다음과 같다

임의의 점을 기준으로 반직선을 그었을 떄 다각형의 선분과 교차하는 지점이 발생하게 되는데 이 지점을 횟수 저장하자

모든 다각형의 선분에 대한 탐색이 끝났을 때 교차횟수가 홀수이면 내부점, 짝수이면 외부점으로 판단할 수 있다

 

근데 단순히 저 방식대로만 하면 반례가 많이 생긴다

 

그래서 좀더 정확하게 해결하는 방법을 풀이해보자

 

기준점 => (px,py)

 

첫번째 방법 => ccw를 이용한 내부점 판단

i번째 점과 (i+1)%N점을 기준으로 반직선이 교차하는지 확인

 

다음과 같은 코드로 교차횟수를 증가할지 말지 판단할 수 있다

P[i].y < py && P[(i + 1) % N].y >= py && ccw(P[i], P[(i+1)%N], 기준점) > 0 
P[(i + 1) % N].y < py && P[i].y >= py && ccw(P[(i+1)%N], P[i], 기준점) > 0

 

ccw를 하기전 코드는 단순히 교차를 하는지만 판단하는 부분이고,

ccw의 의미는 선분을 기준으로 기준점이 어디에 있는지 판단하는 부분이 된다

ccw값이 >0 이 되는 즉 기준점이 왼쪽일때 교차횟수를 증가시켜준다

 

두번째 방법

 

ccw를 사용하지 않고 단순히 직선의방정식 y = (y2-y1)/(x2-x1)*(x-x1)+y1 으로도 해결할 수 있다

// 선분이 반직선과 겹치는 경우
if ((y1 < py && py <= y2) || (y2 < py && py <= y1)) {
    double xx = px;
    double check = (py - y1) * (x2 - x1) / (y2 - y1) + x1;
    if (xx <= check) ans++;
}