외적과 방향 판별: CCW의 모든 것

지난 글에서 점과 벡터, 그리고 내적을 다뤘습니다. 내적이 두 벡터의 “각도 부호”를 알려줬다면, 이번 글의 주인공인 외적(cross product)은 “회전 방향”을 알려줍니다. 선분 교차, 볼록 껍질, 다각형 넓이, 점의 내부 판정 — 계산기하의 거의 모든 알고리즘이 이 한 연산 위에 세워집니다. 외적 하나만 정확히 이해하면 나머지는 그 조합에 불과합니다.

2D 외적이란

3차원 외적은 두 벡터에 수직인 벡터를 만들지만, 2D에서는 그 결과 벡터의 z 성분 하나만 남습니다. 이 스칼라 값이 우리가 쓰는 2D 외적입니다.

u × v = u.x · v.y − u.y · v.x

두 벡터 u, v에 대해 이 값의 부호가 핵심 정보를 담습니다. 양수면 v가 u의 반시계 방향에, 음수면 시계 방향에, 0이면 일직선 위에 있습니다.

CCW: 세 점의 회전 방향

가장 많이 쓰는 형태는 세 점 A, B, C에 대한 방향 판별입니다. A→B→C로 따라갈 때 왼쪽으로 꺾이는지(반시계), 오른쪽으로 꺾이는지(시계), 똑바로 가는지를 묻습니다.

ccw(A, B, C) = (B − A) × (C − A)

부호의 의미는 다음과 같습니다.

• ccw > 0 → 반시계(CCW), C는 A→B의 왼쪽
• ccw < 0 → 시계(CW), C는 A→B의 오른쪽
• ccw = 0 → 세 점이 일직선

구현은 한 줄입니다.

def ccw(a, b, c):
    return (b[0] - a[0]) * (c[1] - a[1]) \
         - (b[1] - a[1]) * (c[0] - a[0])

# > 0 반시계 / < 0 시계 / = 0 일직선

내적이 cos을 부호로 읽었듯, 외적은 sin(회전 방향)을 부호로 읽습니다. 정수 좌표면 결과도 정수라 오차 없이 방향을 단정할 수 있다는 점이 결정적입니다. 부동소수점 각도 계산이 만드는 미세 오차에서 완전히 자유롭습니다.

외적의 크기 = 넓이

외적은 부호만 쓸모 있는 게 아닙니다. 절댓값은 두 벡터가 만드는 평행사변형의 넓이와 같습니다.

따라서 세 점이 이루는 삼각형의 넓이는 외적 절댓값의 절반입니다.

def triangle_area2(a, b, c):
    # 넓이의 2배 (정수 유지)
    return abs(ccw(a, b, c))

# 실제 넓이 = triangle_area2(...) / 2

여기서 외적은 사실상 2×2 행렬식(determinant)과 같습니다. 두 벡터를 열로 세운 행렬의 행렬식이 바로 외적이며, 이것이 넓이가 되는 것은 선형대수의 기본 사실입니다. 다음 글에서 다룰 다각형 넓이 공식(신발끈)도 이 외적의 합으로 유도됩니다.

응용 1: 점이 직선의 어느 쪽인가

직선을 두 점 A, B로 정의하면, 임의의 점 P가 어느 쪽에 있는지는 ccw(A, B, P)의 부호로 즉시 알 수 있습니다. 이는 볼록 다각형 내부 판정, 반평면 교집합 등에서 핵심입니다.

def side(a, b, p):
    s = ccw(a, b, p)
    if s > 0: return "left"
    if s < 0: return "right"
    return "on_line"

응용 2: 각도 기준 정렬

여러 점을 한 기준점에서 본 각도 순서로 정렬할 때, arctan2 같은 삼각함수 대신 외적을 비교 함수로 쓸 수 있습니다. 두 점 중 어느 쪽이 더 반시계인지는 외적 부호가 알려주기 때문입니다. 볼록 껍질의 그레이엄 스캔이 정확히 이 정렬을 사용합니다.

import functools

def polar_cmp(o):
    def cmp(p, q):
        c = ccw(o, p, q)
        if c != 0:
            return -1 if c > 0 else 1   # 반시계 우선
        # 같은 방향이면 가까운 점 우선
        dp = (p[0]-o[0])**2 + (p[1]-o[1])**2
        dq = (q[0]-o[0])**2 + (q[1]-o[1])**2
        return -1 if dp < dq else 1
    return functools.cmp_to_key(cmp)

정리: 외적이 답하는 질문들

외적 하나로 풀리는 질문을 모아보면 그 위력이 드러납니다.

질문	외적으로
왼쪽? 오른쪽? 일직선?	ccw(A,B,C) 부호
삼각형 넓이	|ccw| / 2
점이 선분의 어느 쪽	ccw(A,B,P) 부호
각도 순 정렬	ccw 를 비교자로
세 점 일직선 여부	ccw == 0

오버플로에만 주의하면 됩니다. 좌표 범위가 크면 외적은 좌표 제곱 규모까지 커지므로, 큰 정수형(파이썬은 자동, C++은 long long)을 써야 합니다.

다음 글에서는 이 외적을 본격적으로 활용하는 첫 알고리즘, 점들을 감싸는 가장 작은 볼록 다각형을 찾는 볼록 껍질(convex hull)을 다룹니다.

---

지난 글: 점과 벡터: 계산기하학의 출발점

다음 글: 볼록 껍질: 그레이엄 스캔과 모노톤 체인

읽어주셔서 감사합니다. 😊