[알고리즘] CCW (Counter Clock Wise)

CCW (Counter Clock Wise)

• 점 3개를 이었을 때의 방향을 알 수 있는 알고리즘
• 외적값을 통해 반시계, 평행, 시계를 판단한다.
• 외적값 < 0 : 시계 방향
• 외적값 == 0 : 평행
• 외적값 > 0 : 반시계 방향

외적값 구하기

$A(x1, y1), B(x2, y2), C(x3, y3)$
$→ (x1y2 + x2y3 + x3y1) - (x2y1 + x3y2 + x1y3)$
$→ (x2 - x1)(y3 - y1) - (x3 - x1)(y2 - y1)$

선분 교차 판정

$선분 1: A(x1, y1), B(x2, y2)$
$선분 2: C(x3, y3), D(x4, y4)$
$CCW(A, B, C) * CCW(A, B, D) <= 0$ & $CCW(C, D, A) * CCW(C, D, B) <= 0$

• 단, 둘 다 0일 경우(네 점이 한 선 상에 존재)
  $max(A, B) >= min(C, D)$ & $max(C, D) >= min(A, B)$ 를 만족해야한다.