Counter ClockWise (CCW)

CCW

“Counter ClockWise”의 약자로, “평면에 놓인 3개의 점에 대한 방향관계를 구하는 방법” 중 하나이다. CCW는 ‘반시계 방향’이라는 뜻을 가지고 있는데, 알고리즘의 반환값이 “점들의 관계가 반시계 방향이어야 양수를 반환”하기 때문이라고 생각한다.

시나리오 예시

큰 시나리오는 존재하지 않다. 다만 아래 case에 대해서 점을 명명할 것이다.

구현 방법

벡터의 외적을 이용하는 방법

CCW 알고리즘은 ‘벡터의 외적’이라는 개념을 사용한다. 우리는 위의 case에 대해, 각 점이 어떠한 방향 관계인지를 알고 싶다. 평면상에 점이 3개 존재한다면, 방향관계가 가능한 경우는 총 3가지로 요약할 수 있다.

• 점들의 방향관계가 시계방향인 경우 ( $A$ -> $C$ -> $B$ ) : 반환값 음수

  

• 점들의 방향관계가 반시계방향인 경우 ( $A$ -> $B$ -> $C$ ) : 반환값 양수

  

• 점들의 방향관계가 일직선인 경우 ( $A$ -> $B$ -> $C$ ) : 반환값 $0$

  • 두 선이 평행한 경우도 해당

  

각 경우에 따라 계산되는 CCW 함수의 값이 다르다. 자세한 반환값은 위의 case를 참고하자.

계산하는 식은 $A(x1, y1)$, $B(x2, y2)$, $C(x3, y3)$라고 할 때, $ABC$의 방향관계는 아래 식으로 계산할 수 있다.

\[\text{ccw}(A, B, C) = x1y2 + x2y3 + x3y1 - (x2y1 + x3y2 + x1y3)\]

이 값이 양수면 반시계방향, 음수면 시계방향, $0$이면 평행하다고 이해할 수 있다.

알고리즘 활용 방안

기하 알고리즘의 기본이 될 만한 알고리즘으로, 많은 기하 문제에서 사용될 수 있다고 한다.

• 선분 교차 문제에서 많이 쓰인다. 선분 교차 1이 선분 교차의 기본형 문제라고 볼 수 있다

• 다각형의 넓이를 구할 때에도 쓰인다. 다각형은 여러 삼각형으로 쪼갤 수 있고, 삼각형의 신발끈 공식이 정확히 CCW 알고리즘 반환값의 절반이다. 다각형의 면적 문제에서 이 점을 이용해 문제를 해결할 수 있다