[알고리즘/파이썬] 볼록 껍질 Convex Hull 알아보기

 

 

https://www.acmicpc.net/problem/1708

1708번: 볼록 껍질

 

볼록 껍질 그 자체인 위의 문제를 보면서 볼록 껍질 알고리즘을 알아보자.

 

 

여러 점들이 좌표 상에 흩뿌려져 있을 때 그 점들을 모두 가두는 볼록 다각형을 만들어낼 수 있다.(선분 위의 점도 허용)

* 오목 다각형이라면 오목의 원인이 되는 점을 빼버리면 되기 때문에 항상 볼록 다각형을 만들어낼 수 있다

* 모든 점들이 일직선 상에 있거나 점이 2개인 경우처럼 예외인 경우는 있을 수 있음

 

 

 

1. 시작점 잡기

일단 출발점을 잡아야한다. y 좌표가 가장 점을 선택하고 여러 개인 경우 x좌표가 최대한 작은 점을 선택해야 한다.

 

2. 나머지 점들 정렬하기

이제 나머지 점들을 시계 반대 방향으로 정렬해야 한다. 정렬할 때 비교 조건을 다음과 같이 설정한다.

p1, p2 점을 비교한다고 했을 때, 시작점으로부터의 상대 벡터를 각각 구하고 CCW를 계산하여 어느 것이 더 

시계 반대 방향에 위치해 있는지 판정할 수 있다. 그래서 정렬이 완료되면 시계 반대 방향으로 순회가 가능해진다.

단, 이때 CCW=0인 경우는 p1, p2가 시작점으로부터 같은 직선 상에 위치한다는 의미인데 이때는 거리가 더 먼 점을 정렬 순서 상 더 뒤에 놓이게 한다. 

 

3. 점들 순회

이제 하나씩 순서에 따라 점들을 순회한다. 

아래 3번째 그림을 보자. 1,2를 이어서 직선을 그었을때 그 다음 점인 3이 그 직선에 대해 왼쪽에 놓아져있어야 한다.

그럼 그 직선이 나머지 점들을 포함할 수 있게 된다는 의미이므로 볼록껍질의 변이 된다.

4번째 그림을 보자. 2,3을 이어서 직선을 그었을 때 그 다음 점인 4가 그 직선에 대해 오른쪽에 놓여져있다. 이러면 해당 직선은 이 4번점을 포함할 수 없게되므로 볼록껍질의 변이 될 수 없다. 이때는 이 직선을 취소하고 2,4,을 이어서 계속 진행하면 된다. 이러한 취소는 한번에 여러번 일어날 수 있다.

(글의 설명이 다소 불친절하게 여겨질 수 있다. 지금 글 쓸 에너지가 거의 남아있지 않기 때문.. 하지만 다른 글들 같이 참고하면 수월하게 이해가 될 것이다.. ㅎㅎ)

 

from functools import cmp_to_key

def ccw(p, p1, p2):
    x1, y1 = [p1[0] - p[0], p1[1] - p[1]]
    x2, y2 = [p2[0] - p[0], p2[1] - p[1]]
    return x1*y2 - x2*y1

def compare_dist(p1, p2):
    d1 = p1[0]**2 + p1[1]**2
    d2 = p2[0]**2 + p2[1]**2
    return d1 > d2

# 파이썬 라이브러리 활용
# 리턴값이 음수면 p1, p2 순서가 그대로 유지
# 리턴값이 양수면 p2, p1 순서가 됨
def comp(p1, p2):
    direction = ccw([0, 0], p1, p2)
    if direction > 0: # 외적 결과가 양수라는 건 p2가 더 시계반대방향쪽에 있다는 뜻
        return -1
    if direction == 0:
        if compare_dist(p1, p2): # 더 먼 것은 p1이므로 p2보다 더 뒤에 놓는다.
            return 1
        else:
            return -1
    if direction < 0:
        return 1

n = int(input())
points = []
for _ in range(n):
    x, y = map(int, input().split())
    points.append([x, y])

# 시작점 찾기
points = sorted(points, key=lambda x: (x[1], x[0]))
start = points[0]

# 시작점에 대한 상대좌표를 구해 정렬
shifted_points = [[x-start[0], y-start[1]] for x, y in points[1:]]
sorted_shifted_points = sorted(shifted_points, key= cmp_to_key(comp))
points = [[x+start[0], y+start[1]] for x, y in sorted_shifted_points]

# 볼록 껍질의 정점을 담아둘 스택
# 스택에 2개의 점을 넣어준다.
stack = [start, points[0]]

# 외적 결과의 z좌표의 음양 부호를 통해 ccw 여부를 판단
# 0인 경우는 선분 위의 점이라는 뜻이므로 배제해주어야 함
for p in points[1:]:
    while len(stack) > 1 and ccw(stack[-2], stack[-1], p) <=0:
        stack.pop()
    stack.append(p)
print(len(stack))