<자료구조 알고리즘> CCW 알고리즘

 

CCW(Counter Clock Wise) 알고리즘이란?

시계 반대 방향이라는 뜻으로 세 점이 있을 때 이들의 위치 관계를 파악하는 알고리즘이다. 

기하 알고리즘에서 덧셈처럼 아주 기본적인 알고리즘이며 선분 교차 convex hull 찾기 알고리즘 등 대부분의 기하 알고리즘에서 사용한다. 

결과가 음수라면 시계 방향, 0이라면 일직선, 양수라면 시계 반대 방향이라는 뜻이다.

 

일직선인 경우

 

 

시계 반대 방향

시계 방향

 

CCW 알고리즘은 벡터의 외적이 두 벡터의 상대적인 방향에 따라 결과 벡터의 방향이 바뀐다는 것을 이용한다. 그럼 벡터의 외적을 먼저 알아보자. 

벡터의 외적

$\overrightarrow{v} = \begin{bmatrix} v_1& v_2 & v_3 \\ \end{bmatrix}$   $\overrightarrow{w} = \begin{bmatrix} w_1& w_2 & w_3 \\ \end{bmatrix}$의 두 벡터가 있다고 할 때 이 두 벡터의 외적은 아래와 같다.

$$\overrightarrow{v}\times \overrightarrow{w} = \begin{vmatrix}
\widehat{i} & \widehat{j} & \widehat{k}  \\
 v_1& v_2 & v_3 \\
w_1 & w_2 & w_3 \\
\end{vmatrix} = \widehat{i}\begin{vmatrix}
v_2 & v_3 \\
w_2 & w_3 \\
\end{vmatrix} - \widehat{j}\begin{vmatrix}
v_1 & v_3 \\
w_1 & w_3 \\
\end{vmatrix} + \widehat{k}\begin{vmatrix}
v_1 & v_2 \\
w_1 & w_2 \\
\end{vmatrix} = \begin{bmatrix}
v_2w_3 - v_3 w_2 & v_1w_3 - v_3w_1 & v_1w_2 - v_2w_1 \\
\end{bmatrix}$$

여기는 수학 블로그가 아니므로 벡터의 외적을 잘 모른다면 개념만 찾아보고 오면 된다.

우리는 2차원 평면 상의 점들만 이용할 것이므로 $v_3$와 $w_3$는 0이 될 것이다. 이를 대입해서 다시 공식을 적어보면

$$\overrightarrow{v}\times \overrightarrow{w} = \begin{bmatrix}
0 & 0 & v_1w_2 - v_2w_1 \\
\end{bmatrix}$$

위와 같이 결과가 나오게 된다.  이제 본격적으로 ccw 알고리즘에 대해 알아보도록 하자.

 

CCW 알고리즘

2차원 평면 위에 $A(a_x,a_y)$  $B(b_x,b_y)$  $C(c_x,c_y)$ 세 점이 있다고 하자.  이 세점을 이용하여 $\overrightarrow{AB} = \begin{bmatrix}
b_x - a_x &b_y - a_y \\
\end{bmatrix}$,  $\overrightarrow{AC} = \begin{bmatrix} c_x - a_x& c_y - a_y \\ \end{bmatrix}$두 벡터를 구한다.

이제 이 두 벡터의 외적을 구해 보자

$$\overrightarrow{AB}\times \overrightarrow{AC} = \begin{bmatrix}
0 & 0 & (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x)\\
\end{bmatrix}$$

이 때 $ (b_x - a_x)(c_y - a_y) - (b_y - a_y)(c_x - a_x)$의 값이 시계방향이라면 음수 일직선 이라면 0 시계반대 방향이라면 양수가 되게 된다. 왜 이렇게 되는지는 오른손 법칙을 이용해서 방향을 알아보면 알 수 있을 것이다. 이렇게 평면상의 세 점의 관계를 알아내는 알고리즘에 대해 알아보았다.

 

구현

직접 구현할 때는 위의 결과를 전개한 식으로 많이 사용한다.  또한 오버플로가 잘 일어남으로 범위를 잘 확인하여 적절한 자료형을 선택해야 한다. 아래 문제는 ccw만 이용하여 풀 수 있으므로 직접 구현하여 풀어보길 바란다. (답안 코드는 아래에)

https://www.acmicpc.net/problem/11758

11758번: CCW

 

코드는 아래 더보기를 클릭하면 볼 수 있다.

#include<iostream>

using namespace std;
int ccw(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
    double result = (a.first * b.second) + (b.first * c.second) + (c.first * a.second);
    result -= (a.first * c.second) + (b.first * a.second) + (c.first * b.second);
    return result > 0 ? 1 : (result == 0) ? 0 : -1;
}

int main(){
    pair<double, double> a, b, c;
    cin >> a.first >> a.second >> b.first >> b.second >> c.first >> c.second;
    cout << ccw(a,b,c);
}