CCW

기하 알고리즘의 가장 기초가 되는 알고리즘이다.

가르쳐주신 분 말씀으로는 "대부분의 기하 문제는 CCW로 풀이가 가능하다." 라고 하실 정도니 꼭 알아두자.

CCW는 벡터의 외적을 이용하여 평면상에 세 점이 있을 때 점들의 위치관계를 판단할수 있는 알고리즘이며, 회전방향이 반시계인 경우 양의 값, 시계인 경우 음의 값, 일직선 상에 있는 경우 0의 값을 가지게 된다.

점이 3개인 경우, [ A(x1,y1), B(x2,y2), C(x3,y3) ] 일 때,

CCW(A,B,C) = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3)