CCW(Counter-Clockwise) 알고리즘

정의

Counter-Clockwise 알고리즘은, 벡터의 외적을 통해서 한 정점을 기준으로 나머지 2개의 정점의 위치 관계를 파악하는 알고리즘이다.

 

벡터의 외적?

${\vec{a}}$ x ${\vec{b}}$ 는 다음과 같이 정의된다. 

( ${\mid{\vec{a}} \mid}$ ${\mid{\vec{b}} \mid}$ ${\sin\theta}$) $\vec{v}$, [v는 a,b의 법선벡터,  $\theta$는 a벡터에서 b벡터까지 반시계 방향으로 잰 각의 크기]

 

각의 크기 $\theta$는 180도인 $\pi$ 이하의 각도. (약 더 큰 각도라면 각의 변환을 통해서 ${0 \leq \theta \leq \pi}$ 내로 변환을 해주어야한다.) 

참고: sin함수의 그래프

 

또한 벡터의 평행이동을 활용하면 세 점의 좌표를 통해서 바로 외적이 가능하다. 기준점을 O(x1,y1)로 잡고 A(x2,y2) B(x3,y3) 로 잡았을 때, ${\vec{OA}}$ x ${\vec{OC}}$ = ( 0, 0,  x1y2 + x2y3 + x3y1 - y1y2 - y2x3 - y3x1 ) 이 된다.

[외적의 방향 : 두 벡터와 수직인 방향, 외적의 크기 : 두 벡터가 이루는 평행사변형의 넓이]

이 공식은 행렬로 표현했을 때 외적의 결과는 행렬식의 결과와 같으며, 2차원 벡터들의 외적은 항상 3차원 벡터가 나온다는 것을 명심하자.(엄밀하게, 외적은 3차원 상에서 정의된다. -> 2차원 좌표로 주어질 경우, 별 다른 언급이 없다면 z좌표를 단위벡터로 주어서 연산)

 

 

CCW알고리즘 소스코드

long long CCW(pair<long long,long long> a, pair<long long,long long> b, pair<long long,long long> c){
    // 벡터의 외적 활용, 곧 CCW가 외적한 결과 (-)값도 될 수 있음.
    return (long long)(a.first*b.second)+(b.first*c.second)+(a.second*c.first) -
            (b.first*a.second)-(c.first*b.second)-(a.first*c.second);
}

 

 

자, 이제 벡터의 외적을 통해 무엇을 알 수 있을까?

 

먼저, 두 정점 사이의 위치관계를 알 수 있다.

다음과 같은 벡터가 있다고 가정해보자.

A라는 점을 기준으로 B와 C의 위치 관계(시계방향/반시계방향/일직선)를 알고 싶다.

이때 우리가 유의해야할 것은 외적의 결과에 대한 부호이다.

 

$\vec{AB}$ 와 $\vec{AC}$를 각각 $\vec{b}$ 와 $\vec{c}$ 로 부르겠다.

외적의 결과에 대한 부호에 영향을 주는 것은 법선 벡터의 방향이다.

 

B가 C보다 어느 위치에 있는 지 확인하기 위해 $\vec{b}$ x $\vec{c}$를 해보자.

$\theta$는 $\vec{b}$와 $\vec{c}$가 이루는 각을 반시계방향으로 잰 것인데. 이것이 180도($\pi$)초과 360도($2\pi$) 미만 일 경우 ${\sin(\theta)}$는 음수의 부호를 가지게 된다. 즉 이 경우는 B에서 C까지 반시계방향으로 각도를 재었을 때 180도가 초과하므로 음수값을 가지게 된다.

이때 B는 C보다 반시계 방향에 있다고 표현한다.

 

C가 B보다 어느 위치에 있는 지 확인하기 위해 $\vec{c}$ x $\vec{b}$를 해보자.

이 경우는 $\theta$가 90도 미만의 특정 값이다. 외적의 결과는 +부호를 갖게 되며 이 경우에는 C가 B보다 시계 방향에 있다고 표현한다.

 

 

마지막 예시를 살펴보자.

 

이 경우 $\theta$가 180도($\pi$)가 되게 되고 이 경우 외적의 결과는 0이 된다.

 

 

요약하자면, CCW의 결과 R에 대해 

R<0 이면 첫번째 벡터가 가리키는 정점이 나머지 정점의 반시계방향에 있는 것이고

R>0 이면 첫번째 벡터가 가리키는 정점이 나머지 정점의 시계방향에 있는 것이고 

R=0 이면 첫번째 벡터가 가리키는 정점이 나머지 정점과 동일선상에 위치하고 있는 것이다.

 

 

이 알고리즘은 정점간의 위치관계를 따지는 것 외에도, 다각형의 넓이를 구하는 것과 Convex hull을 구하는데에도 활용되는

가장 기초적인 기하 알고리즘이다.