볼록 껍질(convex hull)(2), Monotone Chain 알고리즘, python

모노톤 체인(Andrew's Monotone Chain) 알고리즘

 

 

볼록 껍질(convex hull)(1), Graham Scan 알고리즘, python

볼록 껍질(convex hull)(1), Graham Scan 알고리즘, python

 

 

 

모노톤 체인 알고리즘도 스택을 사용해 점들을 순회하며 CCW를 판별하여 꼭짓점들을 추가해 나가는 방식이 그레이엄 스캔과 동일하다.

하지만 점을 정렬하는 방식과 볼록 껍질을 구성하게 되는 순서에서 차이점이 있다.

 

 

 

 

모노톤 체인에서는 점들을 x축 기준으로 정렬한다.

그리고 스택에 넣으면서 CCW체크를 하게되면 볼록 껍질의 위쪽 절반만 구할 수 있다.

따라서 점들의 정렬순서를 뒤집어서 아래쪽 절반도 구해줘야 한다. 

y축 기준으로 정렬하게 되면 오른쪽 볼록 껍질과 왼쪽 볼록 껍질을 구하게된다.

 

 

 

 

모노톤 체인 알고리즘은 다음과 같이 진행된다.

 

1. 모든 점들을 y값이 작은순으로 정렬한다. y값이 같다면 x값이 작은 순으로 정렬한다.

2. 정렬된 점의 첫번째 점을 시작점으로 선택한다.

3. 정렬한 점들을 스택에 넣는다.

4. 모든 점들을 순회하면서 스택의 상위 2개의 점과 현재 선택된 점의 외적을 구한다. CCW라면 스택에 넣어주고, CW라면 스택에서 1개를 제거한다. CCW가 나올때까지 이 단계를 반복한다.

5. 정렬한 점들의 순서를 뒤집어서 2~4 과정을 한번더 반복한다.

 

 

 

 

점 정렬후 시작점 선택

 

 

 

모든 점들을 y축 오름차순으로 정렬한 뒤, y값이 제일 작은 점을 시작점(p0)으로 선택한다.

 

 

 

 

 

 

 

정렬된 점들을 순회하며 조건 검사하기

 

 

 

처음 2점을 스택에 넣고 스택의 상위 2개와 2번점은 CW이므로 스택에서 하나를 꺼내준다.

스택에 길이가 2보다 작으므로 3번점을 스택에 넣어준다.

 

 

 

 

 

 

 

스택의 상위 2개와 4번점은 CCW이므로 스택에 넣어준다.

스택의 상위 2개와 5번점은 CW이므로 스택에서 하나를 꺼내준다.

 

 

 

 

 

 

 

스택의 상위 2개와 5번점은 CCW이므로 스택에 넣어준다.

스택의 상위 2개와 6번점은 CCW이므로 스택에 넣어준다.

 

 

 

 

 

 

위 과정을 마치게 되면 오른쪽 볼록 껍질을 구할 수 있다.

 

 

 

 

 

 

정렬 순서를 뒤집어서 한번 더 반복하기

 

이제 점의 정렬 순서를 뒤집어서 위 과정을 한번 더 해주게 되면 왼쪽 볼록 껍질을 구할 수 있다.

 

 

 

 

 

스택의 상위 2개와 2번점은 CW이므로 스택에서 하나를 꺼내준다.

스택에 길이가 2보다 작으므로 3번점을 스택에 넣어준다.

 

 

 

 

 

 

 

스택의 상위 2개와 4번점은 CW이므로 스택에서 하나를 꺼내준다.

스택에 길이가 2보다 작으므로 5번점을 스택에 넣어준다.

 

 

 

 

 

스택의 상위 2개와 6번점은 CCW이므로 스택에 넣어준다.

 

 

 

 

이렇게 하면 왼쪽 볼록 껍질을 구할 수 있다.

 

 

 

 

이제 오른쪽 볼록 껍질과 왼쪽 볼록 껍질을 합쳐주면 된다.

여기서 시작점과 끝점은 중복되므로 제거해주면된다.

 

 

python 구현

 

# 외적을 계산해 CCW를 체크
def ccw(p1,p2,p3):
    a,b = p2[0]-p1[0],p2[1]-p1[1]
    c,d = p3[0]-p1[0],p3[1]-p1[1]
    return a*d-b*c

 

graham scan과 동일한 방식으로 벡터의 외적을 통해 CCW를 체크한다.

 

 

# y값이 작은 순으로 정렬
points.sort(key=lambda x:(x[1],x[0]))

# 오른쪽 볼록 껍질
stack1 = []

for i in range(n):
    while len(stack1)>=2 and ccw(points[stack1[-2]],points[stack1[-1]],points[i]) <= 0:
        stack1.pop()
    stack1.append(i)

 

점을 y값 오름차순으로 하여 오른쪽 볼록 껍질을 구한다.

 

 

# y값이 큰 순으로 정렬
points.sort(key=lambda x:(-x[1],-x[0]))

# 왼쪽 볼록 껍질
stack2 = []

for i in range(n):
    while len(stack2)>=2 and ccw(points[stack2[-2]],points[stack2[-1]],points[i]) <= 0:
        stack2.pop()
    stack2.append(i)

 

정렬 순서를 뒤집어 왼쪽 볼록 껍질을 구한다.

 

 

convex_hull = stack1[1:] + stack2[1:]

 

중복되는 점을 제외하고 왼쪽 볼록 껍질과 오른쪽 볼록 껍질을 합쳐주면 된다.