외적 (CCW 알고리즘)

외적

 

이 게시글에서는 '기하 알고리즘'에서 이용되는 벡터의 외적 개념에 대해서

간단하게 살펴볼 예정이다.

(기본적으로 벡터에 대한 개념이 숙지되어 있어야 이해하기가 쉬울 것 같다....)

 

외적은 두 벡터에 동시에 수직인 벡터 (이하 수직벡터)를 구하는 연산으로, 기호로는 를 이용한다.

 

이 때, 두 벡터가 평행하지 않은 경우, 수직벡터는 아래와 같이 두 경우로 나오게 된다.

이는 두 벡터를 연산하는 순서에 따라서 달라지게 되고, 수직벡터는

서로 반대의 방향으로 나타난다.

그러므로 연산 순서에 따라 외적값이 음수 또는 양수로 나타난다. (크기는 같다)

 

혹시 오른손법칙을 알고 있는 사람이라면, 수직벡터가 어떤 방향으로 나타나는지 쉽게 알 수 있을 것이다.

위의 그림은 a X b 를 구한 경우이다.

 

즉, a에서 b로 회전하는 방향인 경우에 수직벡터의 방향을 나타낸 것인데

위의 그림처럼 회전하는 방향대로 엄지를 제외한 손가락들을 접었을 때,

엄지손가락이 가리키는 방향이 수직벡터의 방향인 것이다.

 

만약 두 벡터가 평행한 경우에는 수직벡터는

두 벡터가 놓여있는 평면위에 동일하게 놓이게 된다.

 

주로 xy 평면상에서의 두 벡터를 가지고 외적을 이용하고,

실제로 "CCW 알고리즘"에서도 xy평면상에서 고려하기 때문에

두 벡터가 평행하지 않은 경우, 두 수직벡터는 z좌표의 부호가 반대로 나오게 된다.

(xy평면에 수직이고, 방향이 반대이므로 z좌표만 부호가 반대인 형태)

 

만약 두 벡터가 평행한 경우에는, 두 벡터가 놓여있는 평면(xy평면) 위에 놓이므로

수직벡터의 z좌표는 0으로 나오게 된다.

 

이와 같은 이유로, CCW 알고리즘에서는 수직벡터의 z좌표를 기준으로 삼는 것이다.

 

그렇다면, 이 z좌표를 어떻게 구하는지를 알아보자. 

 

두 벡터 와 이 있다고 하자.

 

이 두 벡터를 외적한  은 다음과 같다.

 

 

앞에서 언급했듯이 처음의 두 벡터를 xy평면상에서의 벡터라고 둔다면,

두 벡터의 z좌표는 0이므로 a3과 b3의 값은 0이 된다. 따라서 

 

으로 나오게 된다.

 

이제, 이 a1b2 - a2b1 의 값을 CCW 함수의 반환값으로 설정하면 된다.

 

만약 세 점 A(x1, y1) , B(x2, y2) , C(x3, y3) 이 주어진다면,

 으로 나오게 되고,

xy평면위의 두 벡터이므로 z좌표를 0으로 둔 후 위의 외적 과정을 이용하면

이므로 

이 z좌표의 부호를 따져서 CCW 알고리즘을 이용하게 되는 것이다! 

 

실제로 이 z좌표는 '사선공식' 이라고 불리는, 세 점이 주어졌을 때

삼각형의 넓이를 구하는 식과 동일하다.

그러므로 선언한 CCW 함수를 통해서 다각형의 넓이를 구하는데에 이용하기도 한다.

 

 

피드백은 언제나 감사합니다.