CCW (Counter-ClockWise) - (1)

CCW (Counter-ClockWise) - (1)

 

 

CCW 알고리즘은 수 계산에서의 사칙연산처럼, '기하 알고리즘'에서 가장 기본적인 알고리즘이다.

즉, 기하 알고리즘에서 매우 자주 이용된다는 뜻이다. 

우선 이 게시글에서는 CCW에 대한 소개를 하려고 한다.

 

CCW 알고리즘이란?

"평면에 놓여진 세 점의 방향관계를 구하는 알고리즘"

 

기본적으로 벡터의 외적 개념이 사용되지만 크게 어려운 내용은 아니다.

아래의 그림을 통해서 이해해보자.

 

 

 

  이렇게 세 점이 주어져 있는 경우에, 이 세 점이 시계방향인 관계인지,

  시계 반대 방향인지, 혹은 평행한 관계인지를 따지는 것이 목표이다.

  CCW 알고리즘은 시계반대방향일 때 양수, 시계방향일 때 음수,

  평행일 때 0을 반환한다.

 

 

 

 위의 그림과 같이 A,B,C 순서로 세 점의 방향관계를 따질 때에는

시계반대방향 관계에 있다고 한다.

위의 그림과 같이 A,C,B 순서로 세 점의 방향 관계를 따질 때에는

시계방향 관계에 있다고 한다.

이를 참고하여 벡터의 외적 개념이 어떻게 적용되는지 알아보자.

 

 

 

1. 세 점으로 두개의 벡터를 표현한다. 

 

만약 A,B,C 순서로 방향관계를 알고 싶다면 A , B를 연결한 AB벡터와

A , C를 연결한 AC벡터를 고려한다.

 

 

2. 두 벡터의 외적값을 따진다.

 

두 벡터의 외적값을 구하면 CCW 함수의 반환값이 된다.

이 때, 외적은 '교환법칙'이 성립하지 않는 것에 주의해야 한다.

즉, A,B,C 순서로 방향관계를 알고 싶다면 AB벡터 x AC벡터로 구해주어야 한다.

(AC벡터 X AB벡터로 구한다면 A,C,B 순서의 방향관계를 구하는 셈이다.)

(위의 그림은 AB벡터 x AC벡터를 구하는 것으로, A,B,C의 방향관계를 구하는 과정이다)

 

 

3. 외적을 통해 구한 법선벡터의 방향(부호)를 따져서 세 점의 방향관계를 구한다.

 

각각의 점을 A(x1, y1) , B(x2, y2), C(x3, y3) 이라고 좌표를 두고, A,B,C 순서로 방향관계를 구한다면,

CCW 함수의 return값은 x1y2 + x2y3 + x3y1 - (x2y1 + x3y2 + x1y3) 이 된다.

(자세한 과정은 <외적> https://wogud6792.tistory.com/11 에서 참고할 수 있다.

이해가 잘 되지 않으면 단순히 암기해도 상관없다.)

 

이 값이 양수이면 시계반대방향, 음수이면 시계방향, 0이면 평행인 것이다.

 

다음 게시글 (2) 에서는 CCW 알고리즘을 어떻게 이용하는지에 대해서 알아보자.

(다음 게시글 : https://wogud6792.tistory.com/12)