직장인의 개발 일기

컨벡스 헐 알고리즘(Convex Hull Algorithm)을 이용해서 다음 문제를 풀 수 있습니다.

https://rudalsd.tistory.com/67

1. 컨벡스 헐 알고리즘(Convex Hull Algorithm)이란?

컨벡스 헐 알고리즘은 2차원 평면에 여러 개의 점이 있을 때 그 점들 중 일부를 사용하여 볼록 다각형을 만들고 그 안에 나머지 모든 점을 포함시키는 것을 의미합니다.

위의 그림을 컨벡스 헐 알고리즘을 통해 선을 그으면 다음과 같이 표시할 수 있습니다.

위를 볼록 껍질이라고 하고, 점 5개로 이루어져있습니다.

이를 알고리즘을 통해 구현할텐데 그 중에서도 O(NlogN)에 구현할 수 있는 그라함 스캔(Graham's Scan) 알고리즘을 알아보도록 하겠습니다.

2. 컨벡스 헐 알고리즘(Convex Hull Algorithm) 동작 원리?

그라함 스캔(Graham's Scan)을 사용하기 전에 두가지 전처리가 필요합니다.

1. 우선 가장 아래에 있는 점들 중 가장 왼쪽에 있는 점을 기준점으로 잡습니다.

2. 이 기준점을 바탕으로 모든 점에 대해 반시계방향에 있는 순서대로 정렬을 합니다.

이 과정을 마친 후 다음과 같이 진행하면 됩니다.

먼저 스택에 1번과 2번 점을 넣습니다.

스택에서 2번 점과 1번 점을 뽑아낸 후 next 점과 ccw를 하여 반시계방향에 있는지(ccw > 0)체크한 후 반시계방향에 있다면 볼록껍질이 될 수 있다는 뜻이고, 뽑아낸 2번 점을 다시 넣고 next를 넣어줍니다.

같은 방법을 통해 next를 또 스택에 넣습니다.

이번에는 first - second 직선보다 first - next 직선이 오른쪽에 있으므로 ccw 값은 0보다 작게 나옵니다. 그렇다면 second 점은 볼록 껍질의 점이 될 수 없으므로 second는 다시 스택에 넣지 않고 위 과정을 반복합니다.

ccw값이 0보다 크므로 next를 stack에 넣어줍니다.

이러한 과정들을 모두 거치면 다음과 같은 결과를 얻을 수 있습니다.