Convex Hull

평면 위에 점들의 집합이 주어졌을 때, Convex Hull 알고리즘은 이 모든 점을 포함하는 도형(점들로 이루어진)을 계산한다. 이 알고리즘은 다양한 차원의 점 집합에도 적용할 수 있지만, 여기서는 평면 위의 점들에 대해 다룬다. 기본적으로 이 알고리즘은 모든 점을 포함하는 선들을 계산한다. 이 문제에 대한 다양한 해결책을 비교할 때, 각 알고리즘의 시간 복잡도를 Big-O 표기법으로 설명할 수 있다.

Convex Hull 알고리즘은 여러 종류가 있지만, 여기서 소개할 해결책은 Quickhull이라는 알고리즘이다. 이 알고리즘은 W. Eddy(1977년)와 A. Bykat(1978년)의 연구에서 각각 독립적으로 개발되었다. Quickhull의 기대 시간 복잡도는 O(n log n)이지만, 최악의 경우 시간 복잡도는 O(n^2)이 될 수 있다. 평균적인 조건에서는 알고리즘이 꽤 효율적이지만, 높은 대칭성을 가진 경우나 원의 둘레에 점들이 위치한 경우에는 시간 복잡도가 기하급수적으로 증가할 수 있다.

Quickhull 알고리즘

Quickhull 알고리즘은 다음과 같이 동작한다:

• 알고리즘은 점들의 집합을 입력으로 받는다. 이 점들은 x 좌표 값에 따라 정렬되어 있어야 한다.
• 먼저 x 좌표가 최소인 점 A와 최대인 점 B를 찾는다. 이 두 점은 당연히 볼록 껍질의 일부가 된다.
• 이 두 점을 연결한 직선을 기준으로 점들의 집합을 두 개의 부분 집합으로 나눈다. 이 부분 집합들은 재귀적으로 처리된다.
• 직선의 한쪽에 있는 점들 중에서 직선과의 거리가 최대인 점을 찾는다. 이전에 찾은 두 점과 이 점은 삼각형을 형성한다.
• 이 삼각형 내부에 있는 점들은 볼록 껍질의 일부가 될 수 없으므로 이후 단계에서 무시한다.
• 삼각형을 이루는 두 선분(초기 직선이 아닌)에 대해 앞의 두 단계를 반복한다.
• 더 이상 남은 점이 없을 때까지 이 과정을 반복한다. 재귀가 종료되면 선택된 점들이 볼록 껍질을 구성한다.

우리의 함수는 다음과 같이 정의된다:

findHull(points: [CGPoint], p1: CGPoint, p2: CGPoint)

findHull(S1, A, B)
findHull(S2, B, A)

이 함수는 다음과 같은 작업을 수행한다:

1. points가 비어 있으면, 직선의 오른쪽에 추가할 점이 없으므로 반환한다.
2. p1에서 p2로 직선을 그린다.
3. points에서 이 직선과의 거리가 가장 먼 점을 찾는다. (maxPoint)
4. maxPoint를 p1 바로 뒤에 볼록 껍질에 추가한다.
5. p1에서 maxPoint로 직선을 그린다. (line1)
6. maxPoint에서 p2로 직선을 그린다. (line2) (이제 이 선들은 삼각형을 형성한다)
7. 이 삼각형 내부에 있는 모든 점들은 당연히 볼록 껍질의 일부가 아니므로 무시할 수 있다. points에서 line1의 오른쪽에 있는 점들을 배열 s1로 그룹화한다.
8. line2의 오른쪽에 있는 모든 점들은 배열 s2로 그룹화한다. line1과 line2의 오른쪽에 동시에 있는 점은 없다. 그렇지 않으면 maxPoint가 p1과 p2 사이의 초기 직선과의 거리가 가장 먼 점이 될 수 없다.
9. 새로운 점 그룹에 대해 findHull(_, _, _)를 다시 호출하여 더 많은 볼록 껍질 점을 찾는다.

findHull(s1, p1, maxPoint)
findHull(s2, maxPoint, p2)

이 과정을 반복하면 결국 볼록 껍질을 구성하는 점들의 배열이 남게 된다.

함께 보기

위키백과의 컨벡스 헐 알고리즘

Swift Algorithm Club을 위해 Jaap Wijnen이 작성함.