CCW (Counter Clock Wise) 알고리즘

정의

CCW는 점 3개를 연결했을 때 직선의 방향을 파악할 수 있는 알고리즘이다.


구체적으로, 점 A, B, C가 있을 때, 세 점을 순서대로 이어서 나오는 선이 시계 방향을 그리는지, 반시계 방향을 그리는지, 혹은 일직선인지 알려준다.

왼쪽부터 순서대로 시계방향, 반시계방향, 일직선

원리

CCW는 벡터의 외적과 연관이 있다.


벡터 $u$,$v$의 외적 $u \times v$ 의 크기 $| u \times v |$ 는 $|u||v| \sin \theta$ 와 같은데, 여기서 $\theta$는 두 벡터 사이의 각도이다.


$\sin{\theta}$는 $180 ^\circ < \theta < 360 ^\circ $ 일 때 음수값을 가지므로, $| u \times v |$ 의 부호에 따라 두 벡터의 방향을 파악할 수 있다.

주의할 점

벡터의 외적은 교환법칙이 성립하지 않기 때문에 순서에 주의해야 한다.

코드

#입력값 a,b,c는 (x,y)의 형태를 가진다고 가정
def ccw(a,b,c):
    return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0])