볼록 껍질 (컨벡스 헐, Convex Hull) 알고리즘

정의

주어진 집합의 볼록 껍질은 해당 집합을 포함하는 가장 작은 볼록 다각형을 의미한다.

원리

볼록 껍질을 구하는 알고리즘은 여럿 있는데, 그 중 하나인 그레이엄 스캔(Graham Scan)을 소개한다.

CCW 알고리즘(https://monogatary.tistory.com/55)을 응용한 방식이며, $O(n\log{n})$ 의 시간 복잡도를 가진다.

• 주어진 좌표들을 정렬한 다음, 해당 배열을 순회한다.
• 스택을 생성하고, 배열을 순회하면서 배열 내의 좌표 c에 대하여 다음 과정을 반복한다.
  • 스택에 원소가 2개 이상 존재할 경우, 스택의 뒤에서 2번째 원소를 a, 마지막 원소를 b라 하자.
  • 좌표 a,b,c의 ccw가 양수거나, 스택의 원소가 2개 미만이 남을 때 까지 스택의 마지막 원소를 제거한다.
    • 만약 껍질의 꼭지점이 아닌 변 위에 위치한 좌표도 껍질에 추가하고 싶다면 ccw의 값이 0 이상으로 조건을 변경하면 된다.
  • 위 과정이 끝난 후, 좌표 c를 스택에 추가한다
• 위의 과정을 거치고 스택에 남아 있는 좌표들은 볼록 껍질의 절반이다. 나머지 절반은 배열을 반대 방향으로 정렬한 후 위의 과정을 반복하면 구할 수 있다.
• 두 껍질을 합친다. 경계에 있는 점들이 중복되므로 이를 처리해야 한다.

코드

def ccw(a,b,c): return ((b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0]))>0
def convex_hull(arr): # 볼록 껍질의 절반을 구하는 함수
    stack=[]
    for c in arr:
        while len(q)>1:
            a,b=stack[-2:]
            if ccw(a,b,c):break
            stack.pop()
        stack.append(c)
    return stack