특정 점이 다각형 안에 포함되는지 알기

오늘 오후내내 생각하다가. 답답해서 올립니다.

특정 다각형 (오각형 ,육각형 … 그 사이의 특이한 형태까지)의 좌표값을 주고

시계 반대방향이나 시계 방향으로 회전하면서 값을 넣어주고

특정 위치의 x,y좌표값을 가지고 이 좌표값이 그 다각형에 포함유무를

체크 할려면 어떻게 해야할지..

많은 답글 부탁드립니다…

3각형, 4각형, 5각형 같은 볼록한 꼭지점만 있는 경우라면 반평면(half-space)계산으로 쉽게 계산할 수 있습니다. 한 변을 나타내는 직선의 방정식을 구해서 주어진 점이 어떤 방향에 있는지를 검사하고(직선이 평면을 2로 나누니까 한쪽에 있겠죠.) 모든 직선에 대해 내부 방향에 있다면(다각형 각 꼭지점의 순서가 시계방향인지 반시계방향인지에 달려 있겠죠.) 점은 안에 있는 것일겁니다.

하지만.. 오목한 꼭지점이 있는 경우(별 모양) 볼록한 꼭지점이 있는 다각형으로 나누어야 합니다. 그러면 위에 설명한 방법으로 계산이 가능합니다.

나누는 방법은 너무 기니 책을 참조하시길..

보통은 알고자 하는 점이 (4, 5)이고 다각형을 포함하는 영역이

(0, 0) ~ (20, 20)이라고 한다면 (4, 200)정도의 점을 하나 지정합니다.

그리고 나서 (4,5) ~ (4, 200)의 직선과 다각형을 구성하는 직선들과의

교차점의 갯수를 구합니다. 만약 홀수이면 (4,5)는 다각형의 내부이고

짝수이면 (4, 5)는 다각형의 외부에 있습니다.