반시계 판별

반시계 판별(counter-clockwise test)은 2차원 평면에서 세 점 A, B, C가 주어졌을 때, 이 점들이 만드는 꺾임 방향이 반시계 방향인지를 수학적으로 판단하는 연산이다. 좌회전 판정이라고도 불리며, 계산기하학에서 가장 핵심적인 기초 도구 중 하나이다. 볼록 껍질 (알고리즘), 선분 교차 판정, 다각형 내부 판정 등 다양한 기하 알고리즘에서 사용된다.

개념

점 A(x₁, y₁), B(x₂, y₂), C(x₃, y₃)가 주어졌을 때, 이 세 점을 순서대로 연결한 삼각형이 반시계 방향으로 꺾이는지, 시계 방향인지, 혹은 일직선 위에 놓여 있는지를 판별한다.

다양한 이름

• 반시계 판별 (counter-clockwise test)
• 좌회전 판정 (left-turn test)
• 방향성 판별 (orientation test)
• ccw 알고리즘 (ccw: counter-clockwise)
• 삼점 방향성 테스트 (orientation of three points)

이들은 모두 같은 수학적/기하학적 문제를 가리키며, 사용하는 문맥이나 언어에 따라 명칭만 다르다.

수식

세 점 A, B, C에 대해 다음 값을 계산한다:

ccw(A, B, C) = (x₂ - x₁)(y₃ - y₁) - (y₂ - y₁)(x₃ - x₁)

또는 벡터 외적을 통한 표현:

• AB = (x₂ - x₁, y₂ - y₁)
• AC = (x₃ - x₁, y₃ - y₁)
• AB × AC = (x₂ - x₁)(y₃ - y₁) - (y₂ - y₁)(x₃ - x₁)

판별 기준

• ccw(A, B, C) > 0 → 반시계 방향 (좌회전)
• ccw(A, B, C) < 0 → 시계 방향 (우회전)
• ccw(A, B, C) = 0 → 일직선

그래픽적 의미

• 점 A에서 B로 진행한 뒤, 점 C로 꺾이는 방향을 판단
• 반시계 방향이면 '왼쪽으로 도는 느낌', 시계 방향이면 '오른쪽으로 도는 느낌'

파이썬 예시

def ccw(a, b, c):
    x1, y1 = a
    x2, y2 = b
    x3, y3 = c
    return (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1)

활용

• 그레이엄 스캔: 볼록 껍질 생성 시 스택의 방향 판단
• Jarvis March: 외접 점을 반시계 방향으로 선택
• 선분 교차 판정: 두 선분의 교차 여부를 ccw로 판별
• 다각형 내부 판별: 점이 다각형 내부에 있는지 확인

같이 보기

• 좌회전 판정
• 볼록 껍질 (알고리즘)
• 그레이엄 스캔
• 선분 교차 판정
• 계산기하학
• 외적

참고 문헌

• Cormen, T. H. et al. (2009). Introduction to Algorithms. MIT Press
• Computational Geometry: Algorithms and Applications by de Berg et al.
• https://cp-algorithms.com/geometry/oriented-triangle-area.html