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

볼록 껍질이란?

 

점들의 집합이 있을 때 그 집합에서 임의의 두 점을 이은 선분이 항상 집합에 포함되면 볼록 집합이라 부른다.

 

출처:https://en.wikipedia.org/wiki/Convex_set

 

왼쪽을 볼록 집합(convex set)이라고 하고 오른쪽을 비볼록집합(non convex set)이라고 한다.

 

 

 

 

 

 

출처:https://en.wikipedia.org/wiki/Convex_hull

 

이러한 볼록집합중에 주어진 모든 점을 포함하는 최소의  볼록집합을 볼록 껍질(convex hull)이라고 한다.  

점들을 고무줄로 팽팽하게 감싸게 되는 모양과 같다.

 

 

 

주어진 점들 중에서 볼록 껍질의 경계선에 포함된 점을 구하게 되면 볼록 껍질의 정확한 형태와 구조를 알 수 있다.

이러한 점들을 구하는 알고리즘에는 대표적으로 그레이엄 스캔(Graham Scan), 모노톤 체인(Andrew's Monotone Chain) 알고리즘이 있다.

 

 

 

그레이엄 스캔(Graham Scan) 알고리즘

 

그레이엄 스캔 알고리즘은 벡터의 외적을 통한 CCW 판별을 사용해서 구현 할수 있다.

 

두 선분의 교차 판정(2), CW/CCW, python

두 선분의 교차 판정(2), CW/CCW, python

 

 

 

 

\(\vec{AB}\times\vec{AC}>0\)이면 점 A, B, C가 반시계방향(CCW)

\(\vec{AB}\times\vec{AC}<0\)이면 점 A,B,C가 시계방향(CW)

\(\vec{AB}\times\vec{AC}=0\)이면 점 A, B, C가한 직선 위에 놓이게 된다.

 

 

 

 

 

그레이엄 스캔은 다음과 같이 진행된다.

 

1. y값이 가장 작은 점에서부터 시작한다. y값이 가장 작은 점이 여러 개라면, x값이 가장 작은 점을 선택한다.

2. 시작점을 제외한 나머지 점들을 {시작점과의 각도}가 작은 순으로 정렬한다. 각도가 같다면 시작점과의 거리가 짧은 순으로 정렬한다.

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

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

5. 모든 점들을 순회하고 나면 스택에 남은 점들은 볼록 껍질의 경계선(꼭짓점)의 점들이 된다.

 

 

 

 

 

 

 

 

 

다음과 같은 점들의 볼록 껍질을 구하는 과정이다.

 

 

 

 

 

 

시작점 선택

먼저 y축이 가장 작은 점(p0)을 시작점으로 선택한다.

 

 

 

 

 

 

 

 

 

시작점을 제외한 나머지 점들을 정렬하기

 

시작점을 제외한 점들을 정렬을 해야 한다.

p0과의 각도를 기준으로 오름차순으로 정렬한다. 만약 각도가 같다면 점사이의 거리가 짧은 것이 앞에 오게 정렬하면 된다. 

 

 

 

여기서 각도는 \(\theta=\arctan(\frac{y2-y1}{x2-x1})\) 로 구할 수 있다.

 

 

 

 

 

 

 

 

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

 

정렬이 완료되었다면, 정렬된 점들을 순회하며 스택의 상위 2개의 점과 현재 선택된 점의 외적을 구해야 한다.

 

 

스택에서 상위 2개를 확인해야 하므로 스택의 길이가 2보다 작다면 스택에 넣어준다. 

 

 

 

 

 

 

스택의 상위 2개와 현재 노드의 외적을 통해 CCW인지 체크한다.

외적이 음수이므로 CCW이고, 스택에 넣어준다.

 

 

 

 

 

 

 

 

스택에서 상위 2개의 점과 3번점은 CW이다. 따라서 스택에서 1개를 꺼낸다.

다시 스택 상위 2개와 3번점의 외적을 구한다. CCW이므로 스택에 넣어준다.

 

 

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

5번 점도 CCW이므로 넣어준다.

 

 

 

 

 

 

 

 

 

4,5,6은 CW이므로 스택에서 하나를 꺼내준다.

3,4,6은 CCW이므로 스택에 넣어준다.

 

 

 

 

 

 

이렇게 모든 점을 순회하게 되면 스택에 남는 점은 [시작점, 1, 3, 4, 6] 이 된다.

 

 

 

 

 

 

 

이 점들이 볼록 껍질의 꼭짓점이 된다.

 

 

 

 

python 구현

 

points.sort(key=lambda p:(p[1],p[0]))
# 시작점 선택
p0 = points[0]

# 시작점을 제외한 점들을 각도가 작은 순, 거리가 짧은순으로 정렬
points = points[1:]
points.sort(key=lambda p:(math.atan2(p[1]-p0[1],p[0]-p0[0]), (p0[0]-p[0])**2+(p0[1]-p[1])**2))

 

먼저 y값이 가장 작은 점을 시작점으로 선택한다.

시작점을 제외한 점들을 각도 순으로 정렬한다.

atan2 함수를 써서 arctan로 각도를 구할 수 있다.

 

 

# 외적을 통해 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

stack = [p0]
for p in points:
	# 스택에서 상위 2개의 점과 현재 점이 CW라면 스택에서 꺼낸다 
    while len(stack)>=2 and ccw(stack[-2],stack[-1],p) <= 0:
        stack.pop()
    stack.append(p)

 

스택에서 상위 2개의 점과 현재점이 CW라면 스택에서 꺼내고, CCW가 되면 스택에 넣어준다.

최종적으로 stack에 담긴 점들이 볼록 껍질의 꼭짓점이 된다.