[알고리즘] CCW로 세 점의 방향성 판별하기

0. 들어가기 전에

첫 알고리즘 포스트입니다. 이번에 쓸 내용은 CCW입니다.

원래는 기하 알고리즘들을 전반적으로 다루려고 했는데 생각보다 글이 길어져서 CCW만 쓰게 되었습니다.

 

본 글의 내용은 고등학교 과정(2007 개정 교육과정 기준)인 '기하와 벡터' 수준의 지식만 있으면 얼추 알아들을 수 있지만, 혹시 그렇지 않다면 설명을 봐도 이해가 안가실 수 있습니다.

급하게 CCW를 사용해야 한다면 바로 아래의 한 줄 요약과 본문 하단의 코드(여기)만 보고 쓰시면 됩니다.

 

1. CCW

기하 알고리즘을 공부하기 전에 필수로 알아야 할 것이 있는데, 그게 바로 CCW입니다. 거의 사칙연산처럼 쓰게 될 거에요.

 

CCW는 Counter Clockwise의 약자로써, 평면 위에 놓여진 세 점의 방향관계를 구할 수 있는 알고리즘입니다.

먼저 한 줄로 요약하자면, CCW는 점 $A, B, C$를 순서대로 봤을때 반시계방향으로 놓여 있으면 양수를, 시계방향이면 음수를, 평행하게 놓여있으면 0을 반환하게 됩니다. 

 

그럼 세 점의 방향관계를 어떻게 판별할까요?

우선 우리는 세 점으로부터 벡터 $\vec{a}=\vec{AB},\ \ \vec{b}=\vec{AC}$를 놓을 수 있습니다.

 

 

 

이때 $\vec{a}$와 $\vec{b}$의 외적의 방향으로 점 $A, B, C$의 방향을 판단 할 수 있습니다.

 

2. 외적 - 기초 지식

들어가기에 앞서 잠깐 설명할 것이 있습니다.

 

1) 외적은 기호 $\times$ 를 사용하여 표기합니다.

외적의 결과로 외적에 쓰인 두 벡터와 동시에 수직인 벡터를 구할 수 있습니다. 이때 이 수직벡터의 방향으로 세 점의 방향 관계를 판단할 수 있습니다.

 

2) 외적은 교환법칙이 성립하지 않습니다. 따라서 $\vec{a}\times\vec{b}$와 $\vec{b}\times\vec{a}$는 다릅니다. (사실 크기는 같습니다.)

 

3) 모든 성분이 0인 벡터를 0 벡터라 하며, $\vec{0}$ 으로 표기합니다.

또한 스칼라 $0$과 임의의 벡터 $\vec{v}$ 에 대해, $0\cdot\vec{v}$ = $\vec{0}$ 입니다.

 

4) 길이가 1인 벡터를 단위벡터(unit vector)라 합니다.

또한 각각 x축, y축, z축의 양의 방향으로 향하는 단위벡터를 특별히 $\hat{i},\ \hat{j},\ \hat{k}$ 로 표기하겠습니다.

 

3. 외적

$\vec{n}$을 $\vec{a}, \vec{b}$에 수직인 단위벡터라 하고, $\theta$ 를 $\vec{a}, \vec{b}$가 이루는 각도라 하면 다음과 같습니다.

$$\vec{a}\times\vec{b} = (|\vec{a}||\vec{b}|\sin\theta)\vec{n},\ (0\leq\theta\leq\pi)$$

 

우선 $\theta = 0$ 혹은 $\theta = \pi$이면 $|\vec{a}||\vec{b}|\sin\theta = 0$이므로, 외적의 결과는 $0\cdot\vec{n} = \vec{0}$임을 알 수 있습니다.

여기서 $\theta = 0\text{ or }\theta = \pi$는 두 벡터가 평행한 경우, 즉, 세 점이 일직선 상에 있는 경우를 의미합니다.

 

그 외의 경우를 생각해보죠.

$A, B, C$가 2차원 평면에 놓여있기 때문에 $\vec{n} = \hat{k}$ 또는 $\vec{n} = -\hat{k}$ 입니다.

왜인지 이해가 안가셔도 괜찮습니다. 밑에서 명확하게 알 수 있습니다.

 

이 방향은 어떻게 정해지느냐, 공대의 만능 법칙인 오른손 법칙을 따릅니다.

 

(그림출처 http://furthermathematicst.blogspot.com/2011/07/121-3d-vectors.html)

 

정말 명확하긴 한데... 이건 그림만 보고 판단할 때 가능한 방법입니다.

컴퓨터는 오른손이 없으니 일단 외적을 직교좌표계로 나타내봅니다.

 

어떤 두 벡터 $\vec{u} = (m_1,\ m_2,\ m_3)$, $\vec{v} = (n_1,\ n_2,\ n_3)$가 있다고 합시다. $\vec{u}\times\vec{v}$의 결과는 다음과 같습니다. 중간 행렬식은 생략하고 마지막 결과만 보셔도 됩니다.

$$\vec{u}\times\vec{v} = \begin{vmatrix}\hat{i}&\hat{j}&\hat{k}\\m_1&m_2&m_3\\n_1&n_2&n_3\end{vmatrix} = \begin{vmatrix}m_2&m_3\\n_2&n_3\end{vmatrix}\hat{i} - \begin{vmatrix}m_1&m_3\\n_1&n_3\end{vmatrix}\hat{j} + \begin{vmatrix}m_1&m_2\\n_1&n_2\end{vmatrix}\hat{k}$$

$$= (m_2n_3-m_3n_2,\ m_3n_1-m_1n_3,\ m_1n_2-m_2n_1)$$

 

이렇게 임의의 두 벡터의 외적을 구했습니다.

우리가 고려하는 벡터는 2차원 평면위에 놓인 벡터입니다. 그러므로 z축 성분인 $m_3$과 $n_3$이 0이어야 합니다.

이를 고려하여 다음과 같은 결과를 얻을 수 있습니다.

$$\vec{u}\times\vec{v} = (0,\ 0,\ m_1n_2-m_2n_1)$$

 

어떤가요? 이제 외적의 결과가 xy평면에 수직이라는 것이 명확해지지 않았나요?

거기다 $m_1n_2-m_2n_1$의 부호에 따라서 점 $A,\ B,\ C$의 방향을 구별할 수 있습니다.

오른손 법칙을 생각하시면 됩니다!

 

값에 따른 방향성은 다음과 같습니다.

$D = m_1n_2-m_2n_1$라 합시다.

$D > 0$이면 반시계방향입니다.

$D = 0$인 경우는 처음에 다뤘습니다. 이때는 평행합니다.

$D < 0$이면 시계방향입니다.

 

4. 평면위의 세 점의 방향성 판별하기

이제 방금 예시로 들었던 벡터 $\vec{u},\ \vec{v}$가 아닌, 아까 우리가 세 점으로부터 정의한 평면 위의 벡터 $\vec{a},\ \vec{b}$에 대해서 생각해봅시다.

우선 점 $A,\ B,\ C$의 좌표를 정의합니다.

$A = (x_1,\ y_1,\ 0), B = (x_2,\ y_2,\ 0), C = (x_3,\ y_3,\ 0)$ 라고 하겠습니다.

$\vec{a} = \vec{AB} = (x_2-x_1,\ y_2-y_1,\ 0)$, $\vec{b} = \vec{AC} = (x_3 - x_1,\ y_3 - y_1,\ 0)$ 입니다.

 

아까 $\vec{u}\times\vec{v} = (0,\ 0,\ m_1n_2-m_2n_1)$라고 했습니다.

따라서 $\vec{a}\times\vec{b}$의 결과는 다음과 같습니다.

$$\vec{a}\times\vec{b} = (0,\ 0,\ (x_2 - x_1)(y_3 - y_1) - (x_3 - x_1)(y_2 - y_1)$$

 

이 결과를 바탕으로 우리는 세 점의 좌표만 가지고도 방향성을 구할 수 있게 되었습니다.

 

5. 코드 구현

다음은 이를 코드로 구현한 것입니다.

 

	struct Point {
	int x = 0, y = 0;
	};
	int ccw(Point A, Point B, Point C) {
	return (B.x - A.x)*(C.y - A.y) - (C.x - A.x)*(B.y - A.y);
	}

view raw ccw.cpp hosted with ❤ by GitHub

 

또한 struct를 쓰지 않고도 사용할 수 있습니다.

 

위 식을 전개해봅시다.

$(x_2 - x_1)(y_3 - y_1) - (x_3 - x_1)(y_2 - y_1)$

$= x_1y_2 + x_2y_3 + x_3y_1 - (y_1x_2 + y_2x_3 + y_3x_1)$

바로 이 식입니다.

 

복잡해보이지만 의외로 외우기 쉽습니다.

사선공식, 혹은 신발끈 공식이라고 불리는데, 세 점의 좌표가 주어질 때 삼각형의 넓이를 쉽게 구할 수 있는 공식입니다.

 

우선 다음과 같이 좌표들을 배치합니다.

$$\begin{vmatrix}x_1&x_2&x_3&x_1\\y_1&y_2&y_3&y_1\end{vmatrix}$$

 

빨간색 빗금을 각각 곱한 뒤 모두 더해주면 됩니다.

$x_1y_2 + x_2y_3 + x_3y_1$ 입니다.

 

파란색 빗금은 각각 곱한 뒤 모두 빼주면 됩니다.

$-(y_1x_2 + y_2x_3 + y_3x_1)$ 입니다.

 

 

이를 코드로 구현하면 다음과 같습니다.

	int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
	int a = x1 * y2 + x2 * y3 + x3 * y1;
	int b = y1 * x2 + y2 * x3 + y3 * x1;
	return a - b;
	}

view raw ccw.cpp hosted with ❤ by GitHub

 

번외) 세 점의 좌표로 삼각형의 넓이 구하기

방금 사선공식이 삼각형의 넓이를 구할때 쓰인다고 했는데요, 이에 대해 알아봅시다.

아까전에(여기) 외적의 값이 다음과 같다고 했습니다.

$$\vec{a}\times\vec{b} = (|\vec{a}||\vec{b}|\sin\theta)\vec{n},\ (0\leq\theta\leq\pi)$$

그렇다면 외적의 크기 $|\vec{a}\times\vec{b}|$는 다음과 같습니다.

$$|\vec{a}\times\vec{b}| = |\vec{a}||\vec{b}|\sin\theta,\ (0\leq\theta\leq\pi)$$

 

네, 삼각형 면적을 구하는 공식 중에 이런 공식이 있었습니다.

$$\triangle = \dfrac{1}{2}ab\sin\theta$$

위의 삼각형에서 $a,\ b$를 벡터로 본다면, 그 외적의 크기는 $a$와 $b$를 변으로 하는 평행사변형의 넓이입니다. 

따라서 CCW함수에서 반환하는 값에 절댓값을 씌우고, 2로 나눠준다면 세 점이 이루는 삼각형의 넓이를 구할 수 있게 됩니다. 넓이에 관한 이 성질은 나중에 다각형의 면적을 구할 때도 이용하게 됩니다.

 

 

---

 

 

질문 및 피드백은 항상 환영합니다.