기하 - CCW, 선분 교차, 볼록 껍질

CCW(Counter Clockwise)란 세 점의 진행 방향이 시계 반대 방향인지, 시계 방향인지 판단할 수 있게 해 주는 알고리즘이다.

$CCW(A, B, C)$는 세 점을 입력으로 받아 직선 $AB$와 점 $C$의 위치 관계를 판단한다. $C$가 직선 $AB$에 비해 반시계 방향으로 진행한다면 양수를, 시계 방향으로 진행한다면 음수를, 직선 위에 있다면 0을 반환한다.

 

CCW 알고리즘은 벡터의 외적을 활용한다. 두 벡터 $\overrightarrow{AB}$와 $\overrightarrow{AC}$를 외적하면 그 부호는 오른손 법칙에 의해 결정되는 외적의 방향을 의미한다. $\overrightarrow{AB}$에 비해 $\overrightarrow{AC}$가 시계 반대 방향이라면 외적은 2차원 평면을 뚫고 나오는 방향이 되어 (+)가 되고, 시계 방향이라면 들어가는 방향이 되어 (-)가 된다. 원래 3차원 벡터에서 정의되는 외적은 2차원에서 사용할 때 $x_3 = y_3 = 0$으로 두어 $\textbf{x}\times\textbf{y}=(0,0,x_1y_2 - x_2y_1 )$으로 간단하게 표기할 수 있겠다.

 

ccw = lambda p1, p2, p3: (p2[0]-p1[0])*(p3[1]-p1[1])-(p2[1]-p1[1])*(p3[0]-p1[0])

 

 

이제 CCW를 응용한 두 알고리즘인 선분 교차 판정 알고리즘과 볼록 껍질 알고리즘에 대해 알아보자.

 

 

선분 교차 판정

두 선분 $AB$와 $CD$가 주어졌을 때, 두 선분이 교차하는지 판정하는 알고리즘이다. 끝점에서 만나는 것도 교차하는 것으로 본다. 대수적으로 접근할 수도 있겠지만, 소숫점 계산이 정밀하지 않으면 문제가 생길 수 있어 CCW를 이용한다.

 

핵심은 CCW를 총 4번 사용하는 것이다.

1. $CCW(A, B, C)$와 $CCW(A, B, D)$의 부호가 다른지 검사한다
2. $CCW(C, D, A)$와 $CCW(C, D, B)$의 부호가 다른지 검사한다.
3. 두 선분이 한 직선 위에 있을 때를 따로 처리한다.

1번을 통해, 직선 $AB$가 선분 $CD$를 관통하는지 확인할 수 있다. 다만 선분 $AB$의 바깥에서 $CD$가 관통되어 있는 경우도 있을 것이므로, 2번을 통해 반대의 입장에서 확인해 줌으로써 선분이 교차하는지 검사할 수 있다. 다만 두 선분이 하나의 직선 위에 있는 경우에는 CCW가 제대로 작동하지 않으므로 별도로 처리한다. 아래 코드를 보면 쉽게 이해할 수 있을 것이다.

def cross():
    r1 = ccw(A,B,C)*ccw(A,B,D)
    r2 = ccw(C,D,A)*ccw(C,D,B)
    if r1 > 0 or r2 > 0: return False
    if r1 == 0 and r2 == 0:
        left = max(min(A[0],B[0]),min(C[0],D[0]))
        right = min(max(A[0],B[0]),max(C[0],D[0]))
        down = max(min(A[1],B[1]),min(C[1],D[1]))
        up = min(max(A[1],B[1]),max(C[1],D[1]))
        return left<=right and down<=up
    return True

 

 

볼록 껍질(Convex Hull)

컨벡스 헐 알고리즘이라고도 불리는 볼록 껍질은 말 그대로 제시된 모든 점들을 포괄하는 볼록 다각형을 이루는 점들을 구하는 알고리즘이다.

 

출처: 백준

 

볼록 껍질을 구하는 방법으로 그레이엄 스캔(Graham Scan) 알고리즘이 있다. 다음과 같이 동작하여 $O(n\log n)$만에 볼록 껍질을 구한다(점들을 검사하는 것 자체는 $O(n)$만에 동작하나 정렬이 포함되어 있으므로).

 

1. 시작점(가장 아래의 점들 중 가장 왼쪽 점)에서부터 점들을 반시계방향으로 정렬한다.
2. 시작점을 포함해 2개의 점을 stack에 넣는다.
3. 현재 점 $p$에 대해 $CCW(stack[-2], stack[-1], p)$가 양수인지 검사한다. 아니라면 양수일 때까지 pop한다. p를 스택에 넣는다.
4. 모든 점에 대해 3을 반복한다.

볼록 껍질 자체가 CCW를 굉장히 직관적으로 잘 활용하는 알고리즘이므로 구체적인 설명은 생략한다. 다만 1번에서 어떻게 점들을 반시계방향으로 정렬하는지에 대한 의문이 있다. 가장 직관적인 방법은 시작점과의 기울기를 측정해서 기울기 오름차순으로 정렬하는 것이다. 다만 마찬가지로 소수점 정밀도에 대한 문제가 있으므로 이것도 CCW를 이용해서 해결할 수가 있다. 시작점 $s$에 대해 두 점 $A,B$을 비교하는 cmp함수를 만들어서 $CCW(s, A, B)$로 어느 점이 앞에 와야 하는지 검사하는 방식이다. 만약 s와의 기울기가 똑같다면(CCW=0), 유클리드 거리가 더 짧은 점을 앞에 오도록 만들면 되겠다.

ccw = lambda p1, p2, p3: (p2[0]-p1[0])*(p3[1]-p1[1])-(p2[1]-p1[1])*(p3[0]-p1[0])
dist = lambda p1, p2: (p2[0]-p1[0])**2+(p2[1]-p1[1])**2
def cmp(a, b):
    c = ccw(p[0], a, b)
    if c == 0:
        return (1,-1)[dist(p[0],a)<dist(p[0],b)]
    return (1,-1)[c>0]

from operator import itemgetter
from functools import cmp_to_key
p.sort(key=itemgetter(1,0))
p[1:] = sorted(p[1:], key=cmp_to_key(cmp))

hull = []
for point in p:
    while len(hull) >= 2 and ccw(hull[-2], hull[-1], point) <= 0:
        hull.pop()
    hull.append(point)
print(hull)

 

파이썬의 sort는 key를 기준으로 정렬하기 때문에, functools.cmp_to_key()를 활용한다.

 

 

좀 더 간단한 방식으로는, x좌표 기준으로 정렬해 두 개의 hull(upper hull, lower hull)을 구하는 방법이 있다. (http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain)

1. x좌표 기준으로 정렬한다.
2. 가장 왼쪽 점에서부터 시작해 lower hull을 구한다.
3. 정렬한 점들의 list를 뒤집어서, 가장 오른쪽 점에서부터 시작해 upper hull을 구한다.
4. 두 hull은 시작점과 끝점이 겹치므로 중복을 제거해 준다.

p.sort()
lower = []
for point in p:
    while len(lower) >= 2 and ccw(lower[-2], lower[-1], point) <= 0:
        lower.pop()
    lower.append(point)

upper = []
for point in reversed(p):
    while len(upper) >= 2 and ccw(upper[-2], upper[-1], point) <= 0:
        upper.pop()
    upper.append(point)

print(lower[:-1]+upper[:-1])