중요한 공식이니 꼭 외우도록 한다!!
[참조 :http://bowbowbow.tistory.com/24]
static boolean isInside(int tx, int ty){ int crosses = 0; //점과 오른쪽 반직선과 다각형과의 교점 개수 int j; for (int i = 1; i < N+1; i++) { j = i%N + 1; // array에 1~N가지 존재 // tx, ty가 점 i,j 의 Y 좌료 사이에 있는 경우 if((Y[i]>ty) != (Y[j]>ty)) { // 둘다 크거나, 둘다 작으면 밖에 점 double atX = (X[j]-X[i])*(ty-Y[i])/(Y[j]-Y[i])+X[i]; //atX가 오른쪽 반직선과의 교점이 맞으면, 교점의 개수를 증가시킨다. if(tx < atX) crosses++; } }
return (crosses%2 > 0); } |
다각형의 내부 외부 판별이란?
그림1에는 다각형과 두개의 점(점 A, 점 B)가 있습니다. 이 그림에서 눈으로 딱 보고 점A 는 다각형 외부에 있고점B는 다각형 내부에 있다는 것을 쉽게 알 수 있습니다.
이렇게 다각형에 대해 주어진 점이 다각형 내부에 있는지 외부에 있는지 판별하는 것을 다각형의 내부 외부 판별이라고 합니다.
아이디어
다각형의 내부에 위치하는 점의 특징은 뭘까?
눈으로 보고 직관적으로 점이 다각형 내부에 있는지 판별하는 것은 아주 쉽습니다. 5살 어린이들한테 이 문제를 내도 다 맞출것이라 생각합니다.
그런데 컴퓨터가 특정 점이 다각형 내부에 있는지 판별하는건 쉬울까요? 우리가 느끼는 직관대로 “점이 선들에 둘러 싸여 있으면 다각형 내부에 있는거야!” 라고 외쳐도 컴퓨터는 알아듣지 못합니다. 컴퓨터가 이해할 수 있는 특징을 파악하고 이를 전달해야합니다.
그 특징은 점의 오른쪽으로 반 직선을 그었을 때 다각형과 만나는 점의 개수가 홀수 개이면 내부에 있는 점이라는 것 입니다. 그럼 짝수 개이면 외부에 있는 점이겠죠?
그림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처럼 꼭지점 p[9], p[0]을 연결하는 선분과 반직선과의 교차여부를 생각합시다. 점B는 선분 (p[9], p[0])의 y좌표 사이에 있지만 교점의 x좌표가 점B보다 작기 때문에 교차하지 않는다고 판단해야합니다.
세번째로 그림6처럼 꼭지점 p[3], p[4]을 연결하는 선분과 반직선과의 교차여부를 생각합시다. 점B는 선분 (p[3], p[4])의 y좌표 사이에 있지 않기 때문에 바로 교차하지 않는다고 판단합니다.