[Algorithm] CCW알고리즘과 선분 교차 판정 알고리즘

CCW알고리즘이란?

    Counter Clock Wise의 약자로, 벡터의 외적을 이용하여 선분AB를 기준으로 점C가 시계반향에 있는지, 반시계반향에 있는지를 판단하는 알고리즘입니다. 

 

선분 교차 알고리즘이란?

    선분 교차 알고리즘은 CCW알고리즘을 이용해서 구할 수 있습니다. 선분AB와 선분CD가 주어질 때, 선분AB를 기준으로 점 C, D가 각각 시계, 반시계 반향에 있고, 선분CD를 기준으로 점 A, B가 각각 시계, 반시계 반향에 있을경우 두선분은 교차합니다. 각각의 선분이 반대 방향인지는 각각의 단위벡터의 z값을 곱했을 때 음수일 경우 다른 방향, 양수일 경우 같은 방향으로 판단합니다.