2개의 기하 알고리즘 (CCW, 그라함 스캔)

CCW와 그라함 스캔 알고리즘은 Convex Hull을 구할때 사용된다.

Convex Hull은 점들이 주어졌을 때, 해당 점들을 모두 포함하는 볼록다각형을 의미한다.

이러한 Convex Hull을 구하기 위한 알고리즘은 다양하게 존재하고 본 글에서는 2가지에 대해서 다룰 것이다. 

 

Algorithm 1. 

첫번째 방법은 직선의 방정식을 이용하는 방법이다. 점들이 1000개 분포한다고 하였을 때, 특정 두 점을 잡고 이 두점이 이루는 선분이 Convex Hull의 한변이 된다면 이 두점을 잇는 직선과 다른 점들과의 관계는 직선보다 크거나 작은 것이 된다. 따라서 전체 점들의 조합, 즉 1000C2의 조합에서 해당 조건 모든 점들에 대하여 직선<0 or 직선>0을 만족하지 않으면 해당 경우는 Convex Hull의 변이 아니게 된다. O(n^3)의 시간복잡도를 가지기 때문에 최악의 경우에 시간이 오래 걸리지만 점들이 정렬되지 않은 상태로 랜덤하게 분포할 때, 오히려 break가 작용되어 시간이 짧아진다. 

 

 

Algorithm 2. 

두번째 알고리즘은 그라함 스캔이라는 Convex Hull을 구하는 대표적인 알고리즘을 이용하는 것이다. 해당 알고리즘을 위해서는 Stack 자료구조가 사용되는 것이 좋고 Python의 경우 append와 pop이 존재하는 List를 그대로 사용하였다. 해당 알고리즘을 적용하기 위해서는 정렬이 선행되어야 한다. 우선 y좌표가 최소인 순서대로, 그다음 x좌표가 최소인 순서대로 정렬을 한다. y좌표가 최소인 점으로 정렬을 하면 좋은점이 CCW를 이용하기 위하여 기준점에서 각도가 작은 순서대로 정렬할때, 내적을 통한 코사인 값을 이용하여 각도를 간접적으로 도출이 가능하다는 점이다. y좌표가 최소인 점이 기준점이라면 다른 모든 점들과 이은 벡터가 (1,0) 벡터와 이루는 각도가 0<= 각도 <=180을 만족하기 때문에 코사인 값과 각도의 일대일 매칭이 가능해진다. 또한 앞서 언급한 CCW의 경우 두 벡터가 이루는 방향을 알아내는 것인데 두 벡터의 외적값을 구하고 0보다 크다면 반시계 방향, 0보다 작다면 시계 방향이 된다. 상기의 과정들을 통해 그라함 스캔의 준비과정이 완료되었고 구체적인 그라함 스캔의 방법은 점들을 스택에 넣어주면서 pop한 기존 2개의 점과 함께 CCW를 하여 오목이 아닌 볼록을 이루는 경우에만 스택에 추가해준다. 만약 오목한 경우라면 스택에서 첫번째로 꺼낸 점을 제거하고 두번째로 꺼낸 점을 첫번째 선분으로 세번째로 꺼내점을 추가하여 위의 과정을 반복한다.