[기하] 다각형의 내부 외부 판별

다각형의 내부 외부 판별이란?

그림1 에는 다각형과 두개의 점 A,B 가 있습니다. 이 그림에서 눈으로 확인했을 때 각 점이 다각형 내부에 있는지, 외부에 있는 지 판별하는 것은 쉽습니다.

이렇게 주어진 점이 다각형 내부에 있는 지 외부에 있는 지 판별하는 것을 다각형의 내부 외부 판별이라고 합니다.

아이디어

다각형의 내부에 위치하는 점의 특성

컴퓨터가 특정 점이 다각형 내부에 있는지 어떻게 판별할까요? 

오른쪽으로 반 직선을 그었을 때 다각형과 만나는 점의 개수가 홀수 개라면 내부에 있는 점입니다.

그림2를 보고 이 특징이 맞는지 확인해봅시다. 다각형 외부에 있는점  A는 다각형과의 교점 개수가 2개 즉 짝수개 입니다.

다각형 내부에 있는점 B는 오른쪽으로 그은 반직선과 다각형과의 교점 개수가 3개 즉 홀수 개 입니다. 

이 원칙은 눈으로 도저히 확인할 수 없을 만큼 복잡한 꼭지점이 백만 개 다각형에서도 내부 외부를 판별하는데 적용할 수 있는 강력한 규칙입니다.

구현

어떻게 반 직선과 다각형의 교점 개수를 구하지?

다각형의 내부 외부 판별 규칙은 간단하지만 반직선과 다각형의 교점의 개수를 구하는 것은 쉽지않아보입니다.

반직선과 다각형의 선분과의 교차점을 구한 후에 이 교차점이 선분 위에 있는지 조사하는 방법을 사용해야 할까요?

다행히 반직선은 x축에 항상 평행한 수평선이기 떄문에 비교적 간단하게 다각형의 선분과의 교차점을 구할 수 있습니다.

다각형의 모든 선분들에 대해 반직선과 교점이 존재하는지를 검사합니다. 

반직선과 선분 사이에 교점이 존재하기 위한 조건은 2가지 입니다.

- 점  B 의 y좌표가 두 선분 꼭지점의 y좌표 사이에 있다.

- 점  B를 지나는 수평선과 선분 사이의 교점의 x좌표가 점B의 x좌표보다 크다.

조건1을 만족하는 점B를 지나는 수평 직선과 선분 사이에 반드시 교점이 존재한다.

이 때 오른쪽 반직선과의 교점만 세야하므로 조건2를 추가로 만족해야 반직선과 선분 사이의 교점 존재여부를 올바르게 판별할 수 있습니다.

이제 그림 3과 같은 다각형이 주어졌을 때 점 B의 반직선과 다각형의 교점의 개수를 찾는 과정을 진행해봅시다.

다각형의 10개의 꼭지점은 p[0], p[1] ... p[9] 으로 주어졌습니다.

먼저 그림4처럼 꼭지점 p[0], p[1]을 연결하는 선분과 반직선과의 교차여부를 생각합시다.

 점 B는 선분 (p[0],p[1] ) 의 y좌표 사이에 있고 교점의 x좌표가 점 B보다 크기 떄문에 교차한다고 판단할 수 있습니다.

그림 5와같은 경우에는 조건2를 만족하지 않기 때문에, 교차하지 않는다고 판단해야합니다.

그림 6처럼 꼭지점 p[3],[4] 를 연결하는 선분과의 교차여부를 생각해봅시다. 

선분 (p[3],p[4])의 y좌표 사이에 있지 않기 때문에 교차하지 않는다고 판단합니다.

소스코드

/* 점을 구조체로 정의 함 */
strcut vector2{
int x, y;
}
/* STL vector를 이용해서 다각형 자료형을 정의 함 */
typedef vector<vector2> polygon;
 

이제 점 B가 다각형 p 내부에 있는지를 반환하는 함수 isinside 를 정의합니다.

bool isInside(vector2 B, const polygon& p){
//crosses는 점q와 오른쪽 반직선과 다각형과의 교점의 개수
int crosses = 0;
for(int i = 0 ; i < p.size() ; i++){
int j = (i+1)%p.size();
//점 B가 선분 (p[i], p[j])의 y좌표 사이에 있음
if((p[i].y > B.y) != (p[j].y > B.y) ){
//atX는 점 B를 지나는 수평선과 선분 (p[i], p[j])의 교점
double atX = (p[j].x- p[i].x)*(B.y-p[i].y)/(p[j].y-p[i].y)+p[i].x;
//atX가 오른쪽 반직선과의 교점이 맞으면 교점의 개수를 증가시킨다.
if(B.x < atX)
crosses++;
}
}
return crosses % 2 > 0;
}