티스토리 뷰
[기하]외적을 이용한 두 벡터의 상대적인 방향 판별
두 벡터의 방향 판별이란?
위 그림의 두 벡터 
와 
에 대해 는 로 부터 반시계 방향으로 약 90도 방향에 있습니다.
위 그림의 두 벡터 와 에 대해 는 로 부터 시계방향으로으로 약 115도 방향에 있습니다.
이렇게 두 벡터에 대해 한 벡터가 다른 벡터로 부터 시계 방향 또는 반시계 방향으로 몇도에 있는지 파악하는 것을 두 벡터의 방향 판별이라고 합니다.
계산기하 알고리즘에서 이러한 두 벡터 사이의 상대적인 방향에 대한 정보를 필요로 하는 상황이 많습니다.
계산 기하 알고리즘이란 컴퓨터를 이용해서 점, 선, 면, 다각형 등 기하학적 도형을 다루는 알고리즘을 말합니다.
그럼 두 벡터가 주어졌을 때 어떻게 프로그래밍적으로 상대적인 방향을 판별할 수 있을까요?
벡터의 외적을 이용하면 됩니다. 그 전에 벡터의 외적이 무엇인지 알아봅시다.
벡터의 외적
정의
벡터의 외적이란 두개의 3차원 벡터에 대해 정의 되는 연산입니다.
두 벡터 , 의 외적은 다음과 같이 정의 됩니다.
는
과
가 이루는 각을 나타내며
은
는 와 에 공통으로 수직인 벡터입니다. 그러나 수직인 벡터는 두개인데 이 중 오른손 법칙에 따라 위 그림에서 엄지 방향에 있는 벡터를 
로 하기로 정의되었습니다.
오른손 법칙을 따라 방향을 따져보면
임을 알 수 있습니다. (벡터의 외적에서 왼쪽 항이 위 그림에서 검지에 해당하기 때문입니다.) 따라서 벡터의 외적에서는 내적과 달리
교환법칙이 성립하지 않습니다.
외적의 성분 표현
, 
와 같이 벡터를 성분으로 표현할 때 두 벡터의 외적 는 
으로 나타낼 수 있습니다.
증명
,
일 때
와
로 나타낼 수 있습니다.
벡터의 외적 연산은 분배법칙이 성립하기 때문에 아래와 같은 전개를 할 수 있습니다.(
)
위 그림을 참고하면
이고
이므로
로 나타낼 수 있고 이는
는 성분 표현으로
입니다.
이차원에서 벡터의 외적
벡터의 외적은 3차원 벡터에서 정의되는데 이차원 벡터에서도 외적으로 의미있는 것을 할 수 있을까요?
이차원 벡터는 z좌표가 0인 3차원 벡터로 생각할 수 있기 때문에 2차원 벡터에 대해서도 외적을 정의할 수 있습니다.
두 벡터 
에 대해 즉 
, 
으로 나타낼 수 있고
이 성립합니다.
즉 두 벡터 에 대해 
가 양수이면 오른손 법칙에 의해 는 로 부터 반시계 방향에 있고
가 음수이면 는 로 부터 시계 방향에 있는 것을 알 수 있습니다.
벡터의 방향성 판단 구현
벡터의 외적의 개념을 알았으니 이제 이차원 벡터에 대해 벡터의 상대적인 방향성을 판단하는 코드를 작성해봅시다.
다음과 같이 벡터의 구조체를 선언합니다. (c++11 문법으로 작성되었습니다.)
struct vector2{
double x, y;
//생성자
vector2(double _x, double _y){
x = _x, y = _y;
}
//외적
double cross(const vector2& other) const{
return x*other.y-y*other*x;
}
}
c++ STL에 동적 배열로 사용되는 vector가 이미 정의되어 있기 때문에 벡터 구조체를 vector2라고 이름지었습니다.
이제 두벡터의 방향성을 판단하는 함수ccw를 구현해봅시다.
ccw는 counterclockwise 반시계 방향이란 단어의 약자로 두 벡터의 상대적인 방향이 반시계 방향일 때 양수, 시계 방향이면 음수, 평행이면 0을 반환하는 함수입니다.
double ccw(vector2 a, vector2 b){
return a.cross(b);
}
어디에 활용되나?
벡터의 상대적인 관계에 대한 정보가 필요할 때 거의 항상 사용됩니다. 이 개념이 중요하게 사용되는 대표적인 사례로 두 선분의 교차 여부를 판별과 볼록 껍질 찾기(convex hull)를 들 수 있습니다.
References
이 글은 알고리즘 문제해결 전략 1권 Capter 15 계산기하를 참고해서 작성했습니다.
- Total
- Today
- Yesterday