CCW(Counter-Clockwise) Algorithm

Counter Clockwise 알고리즘

• CCW 알고리즘은 3개의 점에 대한 방향성에 대한 정보를 알아보는 알고리즘이다.
• 즉, 두 벡터의 방향 관계성을 보기 위한 알고리즘으로 3가지 종류가 있다.

두 백터, v1=(x1,y1,z1) 와 v2=(x2,y2,z2) 가 존재한다고 가정하였을 때, 이 두 백터의 외적(Cross Product)을 통하여 두 백터 에 대한 방향성 정보를 알 수 있다. 외적은 다음과 같이 계산 할 수 있다.

 

S=(x1y2+x2y3+x3y1)−(x2y1+x3y2+x1y3)

 

• S < 0 : Clockwise
• S > 0 : Counter Clockwise
• S = 0: Straight

그렇다면 방향성으로 무엇을 할 수 있을까?

우리는 이 방향성을 이용해서 두 선분이 교차하는지 판단할 수 있다. 

위의 두 선분은 교차하고 있다. 그렇다면 CCW 알고리즘을 어떻게 사용할까?

l1을 기준으로 CCW 알고리즘을 수행해 보면 알 수 있다.

 

CCW(p1,p2,p3) x CCW(p1,p2,p4) < 0

 

하지만 이는 절반만 맞은 풀이이다. 

다음 상황에서는 교차하지 않지만 위와 같이 수행했을 경우 교차판정이 나오게 된다.

즉, l1 뿐이 아닌 l2에 대해서도 CCW 알고리즘을 수행해 주면 된다. 

 

CCW(p1,p2,p3) x CCW(p1,p2,p4) < 0 && CCW(p3,p4,p1) x CCW(p3,p4,p2) < 0

 

마지막으로 CCW의 값이 0인경우를 살펴보자.

이러한 형태의 두 선분이 교차하는 경우는 포개져 있는 경우밖에 없으므로 이 또한 예외처리를 해 주어야 한다.