볼록 껍질(convex hull) 구하는 graham scan 알고리즘 배우기

1. 볼록 껍질(convex hull)

 

주어진 모든 점을 포함하는 최소 크기의 볼록 집합

 

여기서 볼록 집합(convex)이라는 것은 집합 내에 임의의 두 점을 잡아 선분을 그릴때, 해당 선분이 집합 내에 포함되는 집합이다.

 

아래 그림에서 왼쪽은 볼록 집합이지만 오른쪽은 볼록 집합이 아니다.

 

 

 

직관적으로는 무한한 크기의 고무줄(검은색)을 주어진 모든 점을 둘러싸도록 크게 당긴 다음,

 

손을 놓았을때 점에 탁 걸리면서 만들어지는 도형(파란색)

 

 

 

2. 그라함 스캔(graham scan)

 

볼록 껍질을 구하는 대표적인 알고리즘 중 하나

 

1) 주어진 점을 각도 순으로 정렬

 

점을 각도 순으로 정렬한다는 말은...

 

기준점을 잡고 기준점과 점들을 연결한 선분과 x축의 양의 방향이 이루는 각도가 작은 것에서 큰 순으로 번호를 부여하라는 말

 

 

 

그러면 각도순 정렬은 어떻게 할 수 있을까?

 

반시계방향 보니까 CCW를 이용할 수 있을 것 같다

 

기준점 O를 기준으로 A,B를 각도순 정렬하고자 한다면, OA와 OB에 대한 CCW를 구해서, 

 

CCW가 음수여서 시계방향이면 다음 그림과 같이 A가 B보다 큰 것이고, 양수여서 반시계방향이면 B가 A보다 큰 것이다.

 

 

 

그런데 일직선이면 조금 까다롭다. 

 

이거는 문제에서 어떻게 정의하느냐에 따라 다른데, 선분 위의 점을 빼야할 수도 있고 넣어야할 수도 있다.

 

보통은 기준점 O와 가까운 A점이 먼저 나온다고 생각하여 A가 B보다 작다고 정렬하는게 보통이라는데

 

아무튼..

 

 

2) 순서대로 점을 보면서 스택에 차례대로 집어 넣는다.

 

3) 스택의 마지막 두 점과 새로 추가되는 점이 CCW가 아니라면, CCW가 될때까지 스택에서 pop

 

4) 마지막에 스택에 남아있는 점들이 볼록 껍질을 구성하는 점들

 

 

점들이 정렬되어 있다면, 정렬된 점들을 순서대로 순회하여 스택에 집어넣는다.

 

먼저 스택에는 최소한 2개의 점은 들어가 있어야한다.

 

그래서 스택이 길이가 1 이하이면 일단 점을 집어 넣는다.

 

그리고 길이가 2 이상부터 새로운 점을 넣을려고 할때는... 다음 그림을 보자.

 

 

 

스택에 2개 이상의 원소가 있을때는, (-2번 원소, -1번 원소, 들어올려는 원소)순으로 CCW를 계산한다.

 

만약 반시계방향을 이루면 새로운 점을 집어 넣고 다음으로 넘어간다.

 

이렇게 점들을 집어 넣다가.. 다음 그림을 보면.. 5번을 집어넣을려고 하는데..

 

 

 

(3,4,5) 점이 CW로 시계방향을 이룬다. 그러면 다음과 같이 볼록 집합의 정의를 벗어나는게 그림으로도 보인다.

 

 

이러면 이제 5번을 넣지 말고, 스택의 마지막 원소인 4번을 pop하고, 다시 (2,3,5)순으로 CCW를 체크

 

여전히 시계방향을 이루기 때문에, 3번도 빼주고 (1,2,5) 순으로 CCW를 체크하게 된다.

 

 

그러면 (1,2,5)는 반시계 방향을 이루기 때문에 이제는 5를 스택에 집어넣을 수 있다.

 

 

 

 

이를 계속 반복하면 다음과 같이 되는데.. (6,7,8)에서 시계방향이므로 7을 빼고 (5,6,8)이 반시계 방향이므로 

 

이제는 8을 넣어주면 스택에 남아있는 0,1,2,5,6,8이 볼록 껍질을 이루는 점들이 된다.

 

 

 

3. 연습문제

 

1708번: 볼록 껍질 (acmicpc.net)

1708번: 볼록 껍질

 

4. 풀이

 

위 알고리즘을 구현하면 되는데 문제는 볼록 껍질의 선분 위에 점이 여러개 있는 경우 양 끝점만 포함하라고 한다

 

먼저 기준점을 잡고 각도순 정렬을 해야하는데, 기준점을 어떻게 잡으라는지 설명을 안해줘서

 

기준점 아무거나 잡아도 되겠지 했는데... 그러면 틀리더라고

 

알고보니 기준점을 잡을때는 y좌표가 작고 y좌표가 같다면 x좌표가 작은 순으로 정렬한 다음에 가장 작은 점을 잡아야하더라

 

생각해보면 당연한 얘기인듯..?

 

아무튼 가장 좌측 하단의 점을 기준점으로 잡으라는 얘기임

 

n = int(stdin.readline())

points = []

for _ in range(n):
    
    x,y = map(int,stdin.readline().split())

    points.append((x,y))

points.sort(key = lambda item: [item[1],item[0]])

p = points[0]

 

다음으로 기준점을 기준으로 CCW를 이용해 정렬을 해야하는데.. 이걸 어떻게 해야할까? 찾아보니

 

sort()함수에 key로 넣을때 파이썬에서는 cmp_to_key라는 함수를 지원하더라고..

 

정렬하기 전에 기준으로 잡은 p를 기준으로 벡터를 만들어 주고.. 정렬

 

from functools import cmp_to_key

for i in range(n):
    
    points[i] = (points[i][0]-p[0],points[i][1]-p[1])

points.sort(key = cmp_to_key(ccw))

 

참고로 cmp_to_key()에 들어가는 정렬함수는 2개의 인자를 가지고 있어야한다.

 

인자가 1개만 있으면 다음과 같이 2개를 넣고 있는데 1개만 받는 함수라며 에러난다

 

 

 

이제 점을 각도 정렬 했으면, 순서대로 순회해서 스택에 넣을건데 스택의 길이가 1 이하이면 일단 스택에 넣는다

 

scan = [0]

for i in range(1,n):

    if len(scan) <= 1:

        scan.append(i)

 

 

길이가 2 이상일때 스택에 넣을려고 한다면... (-2번, -1번, 새로 넣을려는 점)으로 CCW를 체크해야한다.

 

scan = [0]

for i in range(1,n):

    if len(scan) <= 1:

        scan.append(i)

    else:

        while len(scan) >= 2:

            p = points[scan[-2]]

            x = [points[scan[-1]][0] - p[0], points[scan[-1]][1] - p[1]]
            y = [points[i][0] - p[0], points[i][1] - p[1]]

            v = ccw(x,y)

 

여기서 선분 위의 여러 점이 있다면... 양 끝점만 포함하라고 했는데.. 이걸 어떻게 처리할 수 있을까?

 

이 경우는 (-2번, -1번, 넣을려고 하는 점)이 일직선을 이루는 경우이다.

 

다음 그림을 보면 양 끝점만 포함하라고 했으니

 

가운데에 있는 -1번 점은 빼버리고 새로 들어오는 점을 스택에 넣어주면 될 것이라는 것을 파악할 수 있다.

 

 

 

여기서 각도순 정렬되어 있으니, 거리 계산할 필요는 없이 -1번 점을 빼버리고 새로 들어오는 점을 append하면 된다

 

그리고 append하면 break하면 된다.

 

scan = [0]

for i in range(1,n):

    if len(scan) <= 1:

        scan.append(i)

    else:

        while len(scan) >= 2:

            p = points[scan[-2]]

            x = [points[scan[-1]][0] - p[0], points[scan[-1]][1] - p[1]]
            y = [points[i][0] - p[0], points[i][1] - p[1]]

            v = ccw(x,y)

            if v < 0:

                scan.append(i)
                break

            elif v == 0:

                scan.pop()
                scan.append(i)
                break

            else:

                scan.pop()

 

 

근데 이제 pop을 하다보면.. 우연히 스택의 모든 점들과 CCW를 계속 이루지 못할수도 있잖아?

 

그래도 계속 pop을 해야할까?

 

최소 길이가 2 이상을 유지해야하므로, 길이가 1 이하이면 반복문을 멈춰준다.

 

반복문을 탈출했는데 길이가 1 이하라면, CCW를 체크하면서 새로 넣을려는 i번 점을 넣지 못했다는 뜻이므로...

 

i번 점을 append해준다

 

scan = [0]

for i in range(1,n):

    if len(scan) <= 1:

        scan.append(i)

    else:

        while len(scan) >= 2:

            p = points[scan[-2]]

            x = [points[scan[-1]][0] - p[0], points[scan[-1]][1] - p[1]]
            y = [points[i][0] - p[0], points[i][1] - p[1]]

            v = ccw(x,y)

            if v < 0:

                scan.append(i)
                break

            elif v == 0:

                scan.pop()
                scan.append(i)
                break

            else:

                scan.pop()

        if len(scan) <= 1:

            scan.append(i)

 

 

근데.. 그렇게 생각했는데 이게 문제가 모든 점이 일직선 위에 있는 경우는 없고, 현재 점이 각도순 정렬 되어 있기 때문에

 

스택의 모든 점이 pop될리는 없거든?

 

모든 점이 pop될려면 결국 새로운 점들이 모두 시계방향이어야하지만, 반시계방향으로 각도순 정렬되어 있기 때문에, 

 

점들이 A선 아래쪽에는 없으니까... 이게 보니까 스택이 빌리는 없겠다..

 

 

 

 

그래서 최종적으로 다음과 같이 구현 가능하다.

 

from functools import cmp_to_key
from sys import stdin

def ccw(x,y):

    return - (x[0]*y[1]) + (x[1]*y[0])

def graham(points):
    
    scan = [0]

    for i in range(1,n):
        
        if len(scan) <= 1:
            
            scan.append(i)
        
        else:
            
            while scan:
                
                p = points[scan[-2]]

                x = [points[scan[-1]][0] - p[0], points[scan[-1]][1] - p[1]]
                y = [points[i][0] - p[0], points[i][1] - p[1]]

                v = ccw(x,y)

                if v < 0:
                
                    scan.append(i)
                    break
            
                elif v == 0:
                        
                    scan.pop()
                    scan.append(i)
                    break
                    
                else:
                    
                    scan.pop()
    
    return scan

n = int(stdin.readline())

points = []

for _ in range(n):
    
    x,y = map(int,stdin.readline().split())

    points.append((x,y))

points.sort(key = lambda item: [item[1],item[0]])

p = points[0]

for i in range(n):
    
    points[i] = (points[i][0]-p[0],points[i][1]-p[1])

points.sort(key = cmp_to_key(ccw))

scan = graham(points)

print(len(scan))

 

 

5. 최적화된 풀이

 

각도순 정렬을 CCW로 했지만.. 사실 다른 방법이 있다.

 

각도순 정렬이라는게 기준점과 해당 점을 이은 선분이 X축 양의 방향과 이루는 각도가 큰 순으로 오름차순 정렬인데..

 

 

 

좌표가 있으면 math.atan2(y,x)로 각도를 구할 수 있다는 것을 배웠다!

 

https://deepdata.tistory.com/987

각도 구하는 math.atan, math.atan2 사용법 익히기

 

이를 이용해 정렬하면 2배는 빨라진다..

 

그리고 여기와서 생각해보니... 1번부터 순회할 필요 없고 일단 scan에 0,1번을 넣어두고 2번부터 순회하면 될듯?

 

그러면 for문 안에 if len(scan) <= 1:은 할 필요가 없음

 

위에서 생각해봤을때 각도순 정렬하는 순간 어차피 scan에는 최소 2개이상의 점이 들어가 있으니까

 

#convex hull - graham scan
import math
from sys import stdin

#CCW
def ccw(x,y):

    return - (x[0]*y[1]) + (x[1]*y[0])

#find convex hull using graham scan 
def graham(points):
    
    #기준점과 시작점을 볼록 껍질에 넣어주고.
    scan = [0,1]
    
    #정렬된 점을 2번부터 순회하여...
    for i in range(2,n):
        
        #(-2번,-1번,i번 점)의 CCW여부 체크
        while scan:
        
            p = points[scan[-2]]

            x = [points[scan[-1]][0] - p[0], points[scan[-1]][1] - p[1]]
            y = [points[i][0] - p[0], points[i][1] - p[1]]

            v = ccw(x,y)
            
            #CCW를 이루면 볼록껍질에 넣어주고 바로 반복문 탈출
            if v < 0:

                scan.append(i)
                break
            
            #일직선을 이루면.. 선분의 양 끝점만 가지고 가라 했으므로.. 중간의 점을 제거하고
            #i번 점을 넣어주고 반복문 탈출
            #정렬되어 있으니 -1번 점이 중간의 점이고 pop한 다음 바로 append(i)하면 된다.
            elif v == 0:

                scan.pop()
                scan.append(i)
                break
            
            #CW를 이루면 -1번 점을 pop하고 다시 위 과정을 반복
            else:

                scan.pop()
    
    #모든 점을 순회하고 스택에 남아 있는 점들이 볼록 껍질을 이룬다
    return scan

n = int(stdin.readline())

points = []

for _ in range(n):
    
    x,y = map(int,stdin.readline().split())

    points.append((x,y))

#점들을 y좌표가 작은 순, y좌표가 같으면 x좌표가 작은 순으로 오름차순 정렬
points.sort(key = lambda item: [item[1],item[0]])

#기준점은 y좌표가 가장 작고 x좌표가 가장 작은 좌표
p = points[0]

#각도순 정렬
#기준점을 중심으로 해당 점이 x축 양의 방향과 이루는 각도 크기로 오름차순 정렬
#math.atan2(y,x)로 각도 크기를 구한다.
points.sort(key = lambda item: math.atan2(item[1]-p[1],item[0]-p[0]))

scan = graham(points)

print(len(scan))

 

 

참고로 v = 0으로 일직선을 이루는 경우 -1번을 pop하고 i번을 append하고 break하지 않고 그냥 pop해도 되긴 하는데...

 

이 경우에는 스택의 길이가 1 이하가 될 수 있으므로 반복 조건을 설정해줘야한다

 

def graham(points):
    
    scan = [0,1]

    for i in range(2,n):
            
        while len(scan) >= 2:

            p = points[scan[-2]]

            x = [points[scan[-1]][0] - p[0], points[scan[-1]][1] - p[1]]
            y = [points[i][0] - p[0], points[i][1] - p[1]]

            v = ccw(x,y)

            if v < 0:

                scan.append(i)
                break

            else:

                scan.pop()
        
        if len(scan) <= 1:
            scan.append(i)
    
    return scan

 

 

 

 

 

https://www.youtube.com/watch?v=ZzQGZ97ax0k&t=743s