2차원에서 방향 판단하기 (CCW)

알고리즘/일반

2차원에서 방향 판단하기 (CCW)

tsyang 2021. 9. 12. 23:50

문제

위와 같이 2차원 평면에 벡터 $\vec{A B}$ 가 있다. 점 C는 왼쪽방향 혹은 반시계방향(CCW)이고 점 D는 오른쪽방향 혹은 시계방향(CW)라고 할 수 있다.

이때 점C와 점D가 CW인지 CCW인지를 어떻게 판별할 수 있을까?

벡터의 외적으로 알아내기

두 3차원 벡터 $\vec{a}$ 와 $\vec{b}$ 가 있다. 이때 두 벡터의 외적은 다음과 같이 정의할 수 있다.

$\vec{a} \times \vec{b} = \hat{n} | \vec{a} | | \vec{b} | \sin θ$

$θ$ 는 두 벡터의 각도이며 $\hat{n}$ 은 두 벡터에 공통으로 수직인 단위 벡터이다. 이때 수직방향은 두 개가 있는데 오른손 법칙을 따르는 방향으로 한다.

출처 : https://en.wikipedia.org/wiki/Right-hand_rule

성분으로 표현하기

$\vec{a} = (a_{x}, a_{y}, a_{z}), \vec{b} = (b_{x}, b_{y}, b_{z})$ 일 때 두 벡터의 외적은 다음과 같다.

$\vec{a} \times \vec{b} = (a_{y} b_{z} - a_{z} b_{y}, a_{x} b_{z} - b_{x} a_{z}, a_{x} b_{y} - b_{x} a_{y})$

만약 벡터 $\vec{a}, \vec{b}$ 가 2차원 평면위에 있다면, $a_{z} = b_{z} = 0$ 일 것이다.

그러므로 $\vec{a} \times \vec{b} = (0, 0, a_{x} b_{y} - b_{x} a_{y})$ 이 된다.

이제 $a_{x} b_{y} - b_{x} a_{y}$ 의 부호로 두 벡터가 시계방향인지 반시계방향인지를 알 수 있는데, 위의 오른손 법칙의 그림을 보면 $\vec{a} \times \vec{b}$ 의 z성분이 양수일 때 $\vec{b}$ 가 $\vec{a}$ 의 반시계 방향에 있음을 알 수 있다.

따라서

두 이차원 벡터 $\vec{a} = (a_{x}, a_{y}), \vec{b} = (b_{x}, b_{y})$ 가 있을 때, $\vec{b}$ 는 $(a_{x} b_{y} - a_{y} b_{x})$ 가 0보다 크면 $\vec{a}$ 의 반시계 방향에, 0보다 작으면 $\vec{a}$ 의 시계 방향에, 0이면 $\vec{a}$ 와 같은 선상에 위치함을 알 수 있다.

선분 교차 판별

위 방법으로 두 선분이 교차하는지를 판단할 수 있다.

선분 AB에 대해서 점 D와 C가 각각 다른 방향에 있고, 선분 CD에 대해서 점 A와 B가 각각 다른 방향에 있다면 두 선분은 교차한다.

단, 만약 두 선분이 같은 선상에 존재한다면(즉, 외적의 값이 0이라면) 따로 겹치는지 여부를 구해줘야 한다.