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

1. 모노톤 체인(monotone chain)

 

볼록 껍질(convex hull)을 구하는 두번째 알고리즘

 

graham scan과는 다르게 점을 정렬하는 방법이 다르고, 아래쪽 껍질과 위쪽 껍질을 구하여 둘을 합치는 방식으로 구한다

 

구체적으로는...

 

1) 주어진 점을 x좌표 순으로 오름차순 정렬하고 x좌표가 같으면 y좌표를 기준으로 오름차순 정렬

 

2) 첫번째 점과 두번째 점을 스택에 넣는다.

 

3) 이제 순서대로 세번째 점부터 순회하면서 조건에 맞으면 스택에 차례대로 집어 넣는다.

 

3-1) 스택의 -2번, -1번 점과 새로 추가하려는 점이 CW를 이루면 스택에 집어 넣는다.

 

3-2) CW를 이루지 않는다면 CW가 될 때까지 스택의 마지막 점을 pop한다

 

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

 

5) 2),3)을 처음부터 다시 하는데, CW대신 CCW로 바꾸어서 수행하면 마지막에 스택에 남아있는 점들이 아래 껍질이 된다.

 

6) 4),5)에서 얻은 껍질을 합치면 볼록 껍질이 된다.

 

 

2. 예시로 생각해보기

 

점을 X좌표가 작은 순으로 정렬하면 다음 그림과 같이 왼쪽부터 오른쪽으로 점들이 정렬된다.

 

 

 

 

다음에 스택에 점들을 집어 넣을건데 첫번째 두번째는 일단 넣고 세번째부터.. 들어가도 되는지 체크한다

 

만약 (-2번,-1번,새로 들어가려는 점)이 시계방향을 이루면 스택에 넣는다.

 

 

 

반시계방향을 이루므로 스택의 마지막 점 2번을 빼주고, 3번을 넣어준다.

 

이 때 최소 스택은 크기가 2 이상이 되도록 해줘야한다.

 

위와 같은 경우 2번을 빼면 더 이상 반시계,시계를 체크할 수 없으므로, 3번을 바로 넣어주고 4번 점으로 넘어간다.

 

graham scan은 반시계방향으로 정렬되어 있으므로 위와 같은 상황이 일어나지 않지만,

 

monotone chain은 x좌표 순으로 정렬되어 있으므로 위와 같이 스택이 길이가 1 이하가 되도록 pop될 수 있다

 

 

 

그런 다음, (1,3,4)를 확인했을 때 시계방향이므로 4번이 들어가다가 (3,4,5)를 확인했을때 반시계방향이므로 4번이 빠진다

 

그리고 (1,3,5)를 확인했을때 시계방향이므로 5번이 들어가게 된다.

 

이를 반복하면... 마지막에 남아 있는 점들이 볼록 껍질의 윗 껍질을 구성하게 된다.

 

 

 

 

 

다시 1번부터 시작해서 CW를 체크하는 대신 CCW로 바꾸어서 체크하면 아래 껍질을 얻게 된다

 

 

CW를 체크하면 시계방향으로 가장 먼 점들을 가지고 오니 윗 껍질을 찾게 되고 

 

CCW를 체크하면 반시계방향으로 가장 먼 점들을 가지고 오니 아래 껍질을 가지고 오게 된다.

 

또한 X좌표가 최소인 점과 최대인 점 1,9번 점들은 두 껍질에 모두 포함되어 있다.

 

 

3. 연습문제

 

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

1708번: 볼록 껍질

 

 

4. 풀이

 

monotone chain은 graham scan과는 다르게 주의할 것도 없이 그대로 구현하면 된다

 

또한 atan2로 정렬한 graham scan과 비슷한 속도를 보인다.

 

점을 x좌표,y좌표 기준으로 정렬하고..

 

upper, lower 각각에 0,1번 점을 넣은 다음 upper에 대해서는 새로 들어오려는 점과 CW를 체크하고

 

lower에 대해서는 새로 들어오려는 점과 CCW를 체크한다.

 

위에서 보인대로 graham scan과는 다르게 pop이 무한정 될 수 있으므로 스택의 길이가 최소 2 이상이 될때만 반복문을 수행

 

나왔을때 스택의 길이가 1 이하라면 계속 pop되다가 append가 되지 않은 상태이므로 현재 점 i를 append를 시켜준다.

 

반복문을 모두 수행하면 upper이 윗껍질 lower가 아래 껍질을 이룬다.

 

여기서 시작점과 끝점은 모두 upper, lower에 포함되므로 마지막에 2개를 빼줘야한다.

 

#convex hull - monotone chain
from sys import stdin

def ccw(x,y):
    
    return x[0]*y[1] - x[1]*y[0]

def monotone(points):
    
    #점을 x좌표 순으로, 같으면 y좌표 순으로 오름차순 정렬
    points.sort()

    n = len(points)
    
    #0번, 1번점을 윗껍질, 아래껍질에 넣고
    upper = [0,1]
    lower = [0,1]
    
    #2번점부터 차례대로 순회하여...
    for i in range(2,n):
        
        #윗 껍질을 구하는 과정
        #스택의 길이가 최소 2이상일때만 반복문 수행
        #(-2번,-1번,i번)점이 CW를 이루면 append하고 break
        #그 외에는 pop하고 반복
        while len(upper) >= 2:

            x = [points[upper[-1]][0] - points[upper[-2]][0], points[upper[-1]][1] - points[upper[-2]][1]]
            y = [points[i][0] - points[upper[-2]][0], points[i][1] - points[upper[-2]][1]]

            k = ccw(x,y)

            if k >= 0:

                upper.pop()

            else:

                upper.append(i)
                break

        if len(upper) <= 1:

            upper.append(i)
        
        #아래 껍질을 구하는 과정
        #스택의 길이가 최소 2이상일때만 반복문 수행
        #(-2번,-1번,i번)점이 CCW를 이루면 append하고 break
        #그 외에는 pop하고 반복
        while len(lower) >= 2:

            x = [points[lower[-1]][0] - points[lower[-2]][0], points[lower[-1]][1] - points[lower[-2]][1]]
            y = [points[i][0] - points[lower[-2]][0], points[i][1] - points[lower[-2]][1]]

            k = ccw(x,y)

            if k <= 0:

                lower.pop()

            else:

                lower.append(i)
                break

        if len(lower) <= 1:

            lower.append(i)
    
    #시작점, 끝점은 upper, lower에 동시에 포함되어 있으니 2개를 빼줘야함
    return len(upper)+len(lower)-2

n = int(stdin.readline())

points = []

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

print(monotone(points))

 

 

일직선을 이룰 때 신경써야하는거 아니냐? 할 수 있는데 k = 0으로 일직선이면 일단 pop시키도록 구현되어 있다

 

근데 graham scan처럼 가운데(스택의 끝 부분)를 pop하고 현재 점 i를 append한 다음 break해도 되긴 한다

 

그러면 이렇게 하면 upper, lower가 2 이상이 될때만 반복하는거 안해도 되는거 아니냐? 할 수 있지만

 

어쨌든 점 자체가 반시계, 시계방향 정렬이 아니니 무한정 pop될 수 있기 때문에.. 2이상을 유지시켜줘야 index error가 안난다

 

def monotone(points):

    points.sort()

    n = len(points)

    upper = [0,1]
    lower = [0,1]

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

            x = [points[upper[-1]][0] - points[upper[-2]][0], points[upper[-1]][1] - points[upper[-2]][1]]
            y = [points[i][0] - points[upper[-2]][0], points[i][1] - points[upper[-2]][1]]

            k = ccw(x,y)

            if k > 0:

                upper.pop()
            
            elif k == 0:
                
                upper.pop()
                upper.append(i)
                break

            else:

                upper.append(i)
                break
        
        if len(upper) <= 1:
            upper.append(i)
            
        while len(lower) >= 2:

            x = [points[lower[-1]][0] - points[lower[-2]][0], points[lower[-1]][1] - points[lower[-2]][1]]
            y = [points[i][0] - points[lower[-2]][0], points[i][1] - points[lower[-2]][1]]

            k = ccw(x,y)

            if k < 0:

                lower.pop()
            
            elif k == 0:
                lower.pop()
                lower.append(i)
                break

            else:

                lower.append(i)
                break
        
        if len(lower) <= 1:
            lower.append(i)

    return len(upper)+len(lower)-2

 

 

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