볼록껍질 (Convexhull) 구하기

계산기하 문제에서 CCW와 더불어 가장 많이 쓰이는 볼록껍질을 구하는 알고리즘을 소개한다.

볼록껍질(convexhull) 이란, 내각이 모두 180도 미만이면서 N개의 점들을 모두 포함하는 다각형을 의미한다.

N개의 점들이 주어졌을 때 우리는 O(n log n) 만에 볼록껍질을 구성하는 점들을 찾을 수 있다.

 

볼록껍질의 예

 

다른 블로그들에서 각도 순으로 정렬하여 찾는 Graham Scan 알고리즘을 소개하므로,

여기서는 원리는 비슷하지만 조금 다르게 구현하는 알고리즘을 소개한다.

 

우선 이 문제는 정렬이 매우 쉽다.

각도 기준이 아닌, 단순하게 x 좌표를 기준으로 오름차순으로 정렬하고 시작한다.

이제 우리는 CCW를 이용하여 오른쪽 점들만 계속해서 선택할 것이다. 아래 그림을 보자.

x 좌표 정렬 후 1번과 2번을 잇는다.

그러고 나서 봤더니 3번이 반직선 12 에 대해 오른쪽에 위치해 있다.

우리는 오른쪽 점들만 계속해서 선택할 것이므로 2번을 빼고 3번을 추가한다. 그럼 아래처럼 된다.

위처럼 2번이 빠지고 1번과 3번이 연결된다.

이제 그림에는 명시되어 있지 않지만 4번이 반직선 13 에 대해 왼쪽에 위치해 있다.

따라서 3번은 빠지지 않고 4번이 그대로 추가된다.

이제 보면, 5번은 반직선 34에 대해 오른쪽에 위치해 있다.

우리는 오른쪽 점들만 선택하기 때문에, 아까처럼 4번을 빼고, 5번을 추가한다.

여기서도 마찬가지다. 6번이 반직선 35에 대해 오른쪽에 위치해 있다.

따라서 5번을 빼고 6번을 추가한다.

이제 이를 나머지 7, 8, 9, 10 번 점들에서도 반복하면 아래처럼 아랫부분이 나온다.

더 이상 오른쪽에 점이 없으므로 여기서 탐색이 종료된다.

볼록껍질의 아래쪽 부분을 구한 것이다. 그렇다면, 위쪽 부분은 어떻게 구하면 될까?

 

방금 적용한 규칙을 반대로만 적용해주면 된다.

가장 최근에 추가된 두 점보다 현재 점이 왼쪽에 있으면 마지막 점을 빼고, 현재 점을 추가하면 된다.

이를 다시 1번과 2번을 이어주고 시작하면 아래 그림처럼 된다.

이로써 우리는 O(n log n) 만에 볼록껍질을 찾았다.

처음에 x 좌표를 기준으로 정렬할 때 O(n log n), 윗 부분 아랫 부분 각각 O(n) 이기 때문이다.

 

구현은 stack 을 쓰는 것처럼 구현하면 된다.

위쪽 두 개의 원소가 곧 최근 2개의 점들이기 때문에 CCW를 잘 적용해주면 될 것이다.

 

당연히 중복되는 2개의 점, 즉 1번과 10번은 빼주고 생각해야 한다.

1번과 10번은 윗부분 및 아랫부분에 둘 다 포함되기 때문이다.