CCW (Counter Clock Wise) + 선분 교차 판정

CCW 알고리즘은 두 선분이 어떤 방향을 이루고 있는지, 더 나아가 두 선분이 교차하는지 판단하는데 주로 쓰이는 알고리즘이다.

 

두 선분이 어느 방향으로 꺾여 있는지는 외적의 값을 통해 알아낼 수 있다.

외적의 값이 양수면 반시계 방향으로, 음수면 시계방향으로 꺾여 있다는 것을 의미하는데,

이는 오른손 법칙을 통해 쉽게 생각할 수 있다.

외적의 값이 양수라는 것은 엄지손가락이 위로 향했을 때에는나머지 네 손가락이 감기는 모습이 반시계 방향이고,

음수라는 것은 엄지손가락이 아래로 향했을 때에는 나머지 네 손가락이 시계방향으로 감기는 모습이다.

 

이를 통해 선분이 시계방향, 혹은 반시계 방향으로 꺾여있는지 알 수 있다.

간혹 외적 값이 0이 나올 수가 있는데,

이는 두 선분이 같은 평면상에 위치한다는 것이고, 그렇다면 당연히 회전이 없으므로 외적값은 0이 된다.

 

이 원리를 통해 선분이 교차했는지, 혹은 하지 않았는지 판단할 수 있다.

 

점 A B C D

 

이런 경우 벡터 AB와 벡터 AC를 외적, 벡터 AB와 벡터 AD를 외적하여 나온 결과 값을 곱해주었을 때

만약 값이 0보다 작다면 서로 교차하는 판정을, 아니라면 교차하지 않는다는 것을 알 수 있다.

값이 0보다 크다면 두 점 모두 기준 벡터의 한쪽 면에 위치한다는 소리이므로 교차하지 않는다는 것을 알 수 있다

 

허나, 이런 경우에도 반례가 존재한다

이런 경우, 벡터 AB와 벡터 AC를 외적한 값과 벡터 AB와 벡터 AD를 외적한 값의 곱은 음수가 나오지만, 서로 교차하지 않는다.

이런 경우가 존재하므로, AB와 AC, AB와 AD만 외적을 하는 것이 아닌 CD와 CA, CD와 CB도 계산해주어

두 값이 모두 0보다 작은지, 혹은 0보다 큰지 확인해주어야한다.

 

마지막으로 외적 값이 0이 나올 가능성이 있다.

즉, 모두 한 직선 위에 존재한다는 것인데,

이런 경우에는 여러가지 형태가 나올 가능성이 있다

 

일단 예시로 위의 그림을 보면

서로 교차할 수도 있고, 교차하지 않을 수도 있는데

이럴 때에는 단순히 각 선분의 끝과 끝이 서로에 포개어지는지만 확인해주면 된다.

 

무슨 소리냐면,

지금 A가 B보다 왼쪽에 위치(만약 B가 왼쪽이라면 둘이 스왑)하고, C가 D보다 왼쪽(만약 D가 왼쪽에 위치한다면 둘이 스왑)에 위치하므로 

 

A <= C <= B인지 확인하면 된다.