Counter ClockWise (CCW)

CCW 알고리즘

LCS란?

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

---

알고리즘 해법

이 단계에서는 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 (백준 17386) 문제를 참고하자. 풀이는 이 글을 참고하자.