반시계 판별 편집하기

반시계 판별(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에 대해 다음 값을 계산한다:<pre>
ccw(A, B, C) = (x₂ - x₁)(y₃ - y₁) - (y₂ - y₁)(x₃ - x₁)
</pre>또는 벡터 외적을 통한 표현:
*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로 꺾이는 방향을 판단
*반시계 방향이면 '왼쪽으로 도는 느낌', 시계 방향이면 '오른쪽으로 도는 느낌'
==파이썬 예시==
<pre>
def ccw(a, b, c):
    x1, y1 = a
    x2, y2 = b
    x3, y3 = c
    return (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1)
</pre>
==활용==
*[[그레이엄 스캔]]: 볼록 껍질 생성 시 스택의 방향 판단
*[[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
[[분류:기하학]]
[[분류:알고리즘]]
[[분류:수학]]