볼록 껍질 (Convex Hull)

볼록 껍질 (Convex Hull)

 

 

볼록 껍질이란?

 

"2차원 평면 상에서 주어진 점들을 모두 포함하는 가장 작은 다각형"

(이 때, 다각형의 각 변들은 주어진 점을 양 끝점으로 갖는다)

 

기하 알고리즘에서 볼록 껍질이 자주 응용되기 때문에 중요한 알고리즘이다.

 

볼록 껍질을 구하는 데에는 '그라함 스캔 알고리즘(Graham's Scan Algorithm)'이 이용된다.

 

볼록 껍질 (Convex Hull) 구하는 과정은 다음과 같다.

 

 

< 볼록 껍질 (Convex Hull) 구하는 알고리즘 >

 

1. 주어진 점들 중 y좌표가 가장 작거나 혹은 y좌표가 가장 작은 점이 둘 이상이라면 x좌표가 가장 작은 점을 선택

2. 선택한 점을 기준으로 나머지 점들을 반시계 방향으로 정렬 (각을 이용)

3. 그라함 스캔 알고리즘 (Graham's Scan Algorighm) 적용 

 

 

 

< 그라함 스캔 알고리즘 (Graham's Scan Algorithm) 동작 원리 >

 

우선, 그라함 스캔 알고리즘 (Graham's Scan Algorithm)은 스택(Stack) 구조를 이용한다.

제일 처음 선택한 점을 스택에 먼저 넣고, 정렬된 점들을 차례대로 스택에 넣는다.

새로운 점을 스택에 push할 때 만약 스택에 두개 이상의 점이 있다면,

가장 최근에 push된 두 점을 이은 직선을 기준으로 새로운 점이 왼쪽에 있다면 push를 하고,

오른쪽에 있다면 스택의 가장 위의 점을 pop하고 새로운 점을 push한다. (CCW 이용)

아래의 그림 예시를 통해서 살펴보자.

 

                              

 

처음에 선택한 점을 스택에 push한다.

아직 스택에 점이 1개이므로 그 다음 점도 조건을 고려하지 않고 push한다.

그 다음 점을 스택에 push하기 전에 이전의 두 점을 연결한 직선보다 왼쪽에 있는지 파악한다.

위의 예시에서는 왼쪽에 있기 때문에 그대로 push한다.

 

 

위와 마찬가지로 왼쪽에 있으므로 push한다.

 

 

그 다음 점은 이전의 두 점을 연결한 직선보다 오른쪽에 있는 경우이다.

따라서 스택의 제일 위에 위치한 점을 pop하고 새로운 점을 push한다.

(선으로 연결된 점들이 현재 스택에 저장된 점)

 

이 과정들을 반복하면 아래와 같이 나오게 된다.

                         

 

 

 

                           

 

 

 

                            

 

실제로 그라함 스캔 알고리즘(Graham's Scan Algorithm)의 시간복잡도는 O(n)이므로,

볼록 껍질 (Convex Hull)을 구하는데 걸리는 시간복잡도는

점들을 반시계방향으로 정렬하는데 걸리는 O(nlogn)이다.

 

 

 

 

 

 

PC로 보시는 것을 권장합니다.

피드백은 항상 환영입니다.