[C++] 다각형 내부 판별 알고리즘(Point in polygon)
알고리즘

[C++] 다각형 내부 판별 알고리즘(Point in polygon)

알고리즘

안녕하세요, 이번 글에서는 다각형(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;
}

위 알고리즘으로 다각형 클릭을 구현하면 아래와 같이 작동합니다.

자세한 코드는 아래 파일을 참고해주세요

Draw code다운로드