http://cookyworld.tistory.com/49
ClockWise(이하 CW)와 CounterClockWise(이하 CCW)알고리즘은 한 선과 한 점의 위치관계를 구할 때 쓰입니다.
응용하면 선과 선의 위치관계도 구할 수 있습니다.
예를 들어 보면,
<그림 1>
위와 같이 선분AB(보라색)가 있습니다. 연보라색은 선분AB의 연장선으로 이해를 돕기 위해 추가했습니다.
그리고 점i(빨강색), 점j(초록색), 점k(파랑색)가 있습니다.
CW, CCW알고리즘으로는 점 i, j, k가 선분AB의 시계방향에 있는지 반시계방향에 있는지 혹은 일직선(연장선)상에 있는지 구할 수 있습니다!
다음의 식을 통해서 각 위치관계를 알 수 있습니다.
점 K가 있다면 K의 x좌표는 K.x, K의 y좌표는 K.y입니다.
<그림 2>
res = (A.x * B.y + B.x * C.y + C.x * A.y) - (A.x * C.y + B.x * A.y + C.x * B.y)
- 식이 꽤나 복잡해 보이지만, 삽입된 그림을 통해 보면 간단해 보이기도 합니다.
선분의 각 끝 점을 각각 A와 B에 대입하고, 구하려고 하는 점을 C에 대입한 후 res값을 통해 위치관계를 알 수 있습니다.
res == 0 : 점 C는 선분 AB의 일직선상에 있습니다. (세 점 모두 일직선상에 있습니다.)
res > 0 : 점 C는 선분 AB의 반시계방향에 있습니다.
res < 0 : 점 C는 선분 AB의 시계방향에 있습니다.
<그림 1>의 경우 선분 AB와 점 i는 반시계방향, 선분 AB와 점 j는 시계방향, 선분 AB와 점 k는 일직선상에 있습니다.