CCW (Counter Clock Wise)

세 점의 방향성을 판단하는 기하학적 문제

반시계 방향 시계 방향 일직선

 

CCW 값에 의해 세 점이 어느 방향으로 향하는지 알 수 있다.

 

공식은 아래와 같다.

CCW(A, B, C) = (B.x - A.x) × (C.y - A.y) - (B.y - A.y) × (C.x - A.x)

결과 값에 따라 양수: 반시계방향, 음수: 시계 방향, 0: 일직선을 나타낸다.

 

CCW가 어떻게 도출되는지 알아보자.

좌표 원점

좌측 그림과 같은 좌표를 가진 세 점이 있을 때, A를 원점으로 C와 B의 벡터를 구하면 오른쪽 그림과 같이 된다.

 

공식은 아래와 같다.

A' = (0, 0) ← A에서 A를 뺀 것
B' = (bx - ax, by - ay) ← B에서 A를 뺀 것 (6, 2) 이라고 가정
C' = (cx - ax, cy - ay) ← C에서 A를 뺀 것 (7, 3) 라고 가정

 

그럼 두 벡터간의 회전 방향을 알아보자.

 

2D에서 외적 공식:
벡터 u = (ux, uy)
벡터 v = (vx, vy)
u × v = ux × vy - uy × vx

2차원 벡터의 외적 공식을 통해 방향을 구할 수 있다.

B`(6, 2)와 C`(7, 3)의 방향을 구해보자.

6 * 3 - 2 * 7 = 4로 양수인 것을 알 수 있다.

 

반시계 방향으로 향함

 

실제 그림에서 확인한 결과도 B -> C 를 향하는 방향은 반시계방향이다.

원점 이동부터 2차원 외적 공식을 모두 적용한게 CCW 이다.

 

우리는 앞으로 CCW를 활용해 문제를 해결 할 수 있다.

가장 대표적으로 BOJ의 선분 교차 1 문제를 해결해보자. (다음 포스트에서)