세 점의 방향성에 대해 알려주는 알고리즘이다.
세점의 방향성은 3가지로 나뉠 수 있다.
여기서 외적을 통해 세 점의 관계가 저 3개 중 어떤 것인지 판별한다.
세 점의 좌표를 다음과 같이 둬 보자.
$$ (x_1, y_1), (x_2, y_2), (x_3, y_3) $$
점1에서 점2로 가는 벡터$\vec a$ 와, 점2에서 점3으로 가는 벡터$\vec b$ 를 다음과 같이 정의할 수 있다.
$$ \vec a = (x_2-x_1, y_2-y_1)\\ \vec b = (x_3-x_2, y_3-y_2) $$
이를 외적한다.
$$ \vec a \times \vec b = (x_2-x_1)(y_3-y_2) - (y_2-y_1)(x_3-x_2) $$
외적의 결과가 양수라면 반시계, 0이라면 직선, 음수라면 시계방향이다.
외적으로 위와 같이 다각형의 면적을 구하는 문제도 해결할 수 있다.
CCW를 통해 선분 교차 판정을 할 수 있다.
아래 3가지 케이스를 고려하여 최종적인 Line Intersection방법을 알아보자.