안녕하세요, 이번 글에서는 다각형(Polygon)으로 도형을 그리고 클릭 했을 때, 그 클릭한 곳이 다각형의 내부인지 외부인지 판별을 하는 알고리즘 입니다.
코드를 보기전에 우선 알고리즘 설명부터 하겠습니다.
아래와 같이 5각형을 기준으로 클릭을 한다고 봅시다.
다각형 내부 클릭
다각형 외부 클릭
사람은 “내부/외부에 클릭을 했다“라고 쉽게 생각합니다. 하지만 컴퓨터의 경우엔 어떻게 알 수 있을지 고민을 해봐야합니다.
Point in polygon
Point in Polygon은 2차원 좌표에서 특정 좌표가 다각형의 내부에 있는지 외부에 있는지 판별하는 알고리즘 입니다.
특정 좌표에서 왼쪽으로(혹은 오른쪽으로) 선을 쭉 그려봅니다.
이렇게 그린 선(빨간선)과 다각형의 닿는(cross) 갯수를 보면 내부는 홀수, 외부는 짝수가 되는 규칙이 있습니다.
이 방법은 어느 다각형을 보더라도 똑같이 적용 되죠
내부 클릭
위 알고리즘을 코드로 구현하면 아래와 같습니다.
BOOL PointInPolygon(CPoint point)
{
BOOL bPointInPolygon = FALSE;
int iCrosses = 0; // 교차 횟수
for( int i = 0; i < 5; i++ )
{
int j = ( i + 1 ) % 5;
//점(point)이 선분(m_apnt[i], m_apnt[j])의 y좌표 사이에 있음
if( ( m_apnt[i].y > point.y ) != ( m_apnt[j].y > point.y ) )
{
//atX는 점(point)을 지나는 수평선과 선분(m_apnt[i], m_apnt[j])의 교점
double atX = ( ( ( m_apnt[j].x - m_apnt[i].x )/( m_apnt[j].y - m_apnt[i].y ) )*( point.y - m_apnt[i].y ) )
+ m_apnt[i].x;
//atX가 오른쪽 반직선과의 교점이 맞으면 교점의 개수를 증가시킨다.
if( point.x < atX )
iCrosses++;
}
}
// 홀수면 내부, 짝수면 외부에 있음
if( 0 == ( iCrosses % 2 ) )
bPointInPolygon = FALSE;
else
bPointInPolygon = TRUE;
return bPointInPolygon;
}
위 알고리즘으로 다각형 클릭을 구현하면 아래와 같이 작동합니다.
