CCW(Counter-clockwise) 알고리즘
CCW 평면에서 세 점의 방향 관계를 구하는 알고리즘이다.
세 점 A, B, C가 순서대로 반시계 방향이면 양수, 직선 방향이면 0, 시계 방향이면 음수를 반환하게 된다.
CCW의 원리: 벡터의 외적
위의 표에서 반시계 방향인 경우를 벡터로 표시해보았다. 두 벡터를 외적하여 생긴 벡터의 크기는 아래와 같다.
$$ | \vec{AB} \times \vec{AC} | = |\vec{AB}||\vec{AC}|sin\theta $$
위 식에서 $|\vec{AB}|$와 $|\vec{AC}|$는 양수이므로, $sin\theta$에 따라 값이 결정된다.
즉, 외적한 벡터의 크기는 $\theta$가 0° 초과 180° 미만인 경우 양수, 180° 초과 360° 미만인 경우 음수가 된다. (180°, 360°인 경우 0이다.)
또한 $\theta$는 앞의 벡터($\vec{AB}$)로 부터 반시계 방향으로 회전하며 뒤의 벡터($\vec{AC}$)까지의 각도를 나타내기 때문에, 반시계 방향인 경우가 양수, 시계 방향인 경우가 음수가 된다.
즉, $| \vec{AB} \times \vec{AC} |$값의 부호를 알면 두 벡터간 위치 관계(세 점의 방향 관계)를 알아낼 수 있다는 것이다.
외적 계산하기
이제 $| \vec{AB} \times \vec{AC} |$의 값을 계산해보자.
점 A, B, C의 좌표를 각각 $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$이라 두면
$\vec{AB} = (x_2-x_1, y_2-y_1)$, $\vec{AC} = (x_3-x_1, y_3-y_1)$이다.
한편, 3차원 벡터의 외적은 아래와 같은 식으로 나타낼 수 있다.
$$
\vec{a} \times \vec{b} =
\begin{vmatrix}
i & j & k \\
a_1 & a_2 & a_3 \\
b_1 & b_2 & b_3
\end{vmatrix} =
\begin{vmatrix}
a_2 & a_3 \\
b_2 & b_3
\end{vmatrix}i -
\begin{vmatrix}
a_1 & a_3 \\
b_1 & b_3
\end{vmatrix}j +
\begin{vmatrix}
a_1 & a_2 \\
b_1 & b_2
\end{vmatrix}k\\=
(a_2b_3 - a_3b_2, a_3b_1 - a_1b_3, a_1b_2 - a_2b_1)
$$
이제 이 식에 좌표들을 대입해보자.
$$ \vec{AB} \times \vec{AC} = (0, 0, (x_2-x_1)(y_3-y_1) - (y_2-y_1)(x_3-x_1)) $$
$$ | \vec{AB} \times \vec{AC} | = (x_2-x_1)(y_3-y_1) - (y_2-y_1)(x_3-x_1) $$
위 값이 바로 CCW 값이다.
구현해보기(코드)
def ccw(a, b, c) -> int:
value = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
return 1 if value > 0 else -1 if value < 0 else 0
세 점이 반시계 방향 관계이면 1, 시계 방향 관계이면 -1, 일직선 관계이면 0을 리턴하는 함수이다.
이 방법으로 백준 11758번을 해결할 수 있다.
선분 교차 판정
CCW를 활용하면 두 선분의 교차 여부를 쉽게 구할 수 있다.
두 선분이 교차하는 경우를 보자.
$\overline{AB}$를 기준으로, 점 $C$는 반시계 방향에, 점 $D$는 시계 방향에 있다.
$\overline{CD}$를 기준으로, 점 $A$는 반시계 방향에, 점 $B$는 시계 방향에 있다.
즉, $CCW(A, B, C) \times CCW(A, B, D) \leq 0$이면서 $CCW(C, D, A) \times CCW(C, D, B) \leq 0$이다.
예외: 일직선 상에 있을 때
위 식이 성립하지만 교차하지 않는 경우가 있는데, 바로 일직선 상에 있으면서 만나지 않는 경우이다.
따라서 $CCW(A, B, C) \times CCW(A, B, D) = CCW(C, D, A) \times CCW(C, D, B) = 0$인 경우, 두 선분이 만나는 지 따로 판별해줘야 한다.
구현해보기(코드)
ab, cd = ccw(a, b, c) * ccw(a, b, d), ccw(c, d, a) * ccw(c, d, b)
if ab == 0 and cd == 0:
a, b = min(a, b), max(a, b)
c, d = min(c, d), max(c, d)
print(1 if c <= b and a <= d else 0)
else:
print(1 if ab <= 0 and cd <= 0 else 0)
이 방법을 이용하여 백준 17387번을 풀 수 있다.
다각형의 넓이 구하기
CCW 값을 활용하여 서로 교차하는 변이 없는 단순 다각형의 넓이를 구할 수 있다.
앞에서 설명했듯이, CCW는 두 벡터를 외적해서 나온 벡터의 크기를 이용하며, 그 식은 아래와 같다.
$$ | \vec{a} \times \vec{b} | = |\vec{a}||\vec{b}|sin\theta $$
여기서 $|\vec{a}||\vec{b}|sin\theta$ 두 변의 길이가 각각 $|\vec{a}|$, $|\vec{b}|$인 평행사변형의 넓이와 같다.
그리고 이 값을 2로 나누면 아래와 같은 삼각형의 넓이가 된다.
이제 CCW의 값을 활용하여 삼각형의 넓이를 구하는 방법을 알았으니, 다각형을 여러 삼각형들로 쪼갠 후 넓이의 합을 구하면 다각형의 넓이를 구할 수 있다.
다각형의 꼭짓점들을 반시계방향 순서대로 각각 $p_0, p_1, \cdots, p_n$이라고 하자.
이제 삼각형의 넓이들을 구해보자. 계산의 편의성을 위해, 삼각형의 꼭짓점 중 하나는 무조건 (0, 0)으로 잡는다.
삼각형의 넓이는 각각 $\frac{1}{2}(\vec{p_0} \times \vec{p_1}), \frac{1}{2}(\vec{p_1} \times \vec{p_2}), \cdots, \frac{1}{2}(\vec{p_n} \times \vec{p_0})$이 되므로 구하고자 하는 넓이($S$)는 아래와 같다.
$$ S = \frac{1}{2}|(\vec{p_0} \times \vec{p_1} + \vec{p_1} \times \vec{p_2} + \cdots + \vec{p_n} \times \vec{p_0})| $$
각 점들의 좌표를 $(x_0, y_0), (x_1, y_1), \cdots, (x_n, y_n)$이라 두면 아래와 같은 식이 완성된다.
$$S = \frac{1}{2}|(x_0y_1 - x_1y_0 + x_1y_2 - x_2y_1 + \cdots + x_ny_0 - x_0y_n)|$$
식에서 덧셈과 뺄셈의 순서만 바꾸면 신발끈 공식이 완성된다.
오목 다각형에서도 성립할까?
다각형 중에도 위 그림처럼 내각이 180°가 넘는 꼭짓점을 가진 오목 다각형에서도 위 공식이 성립할까?
CCW를 설명하면서 말했듯이, 내각의 크기가 180°가 넘는 경우 외적한 결과값이 음수가 되어 해당 삼각형은 전체 넓이에서 빠지게 된다.
따라서 오목한 부분의 넓이가 정상적으로 빠지게 되어 식은 여전히 성립한다.
구현해보기(코드)
area = 0
for i in range(n):
j = (i + 1) % n
area += points[i][0] * points[j][1] - points[j][0] * points[i][1]
print(abs(area / 2.0))
n은 points 리스트의 크기이다.
이 방법을 이용하여 백준 2166번을 해결할 수 있다. (좌표가 다각형을 이루는 순서대로 주어진다고 조건이 있으므로, 위 방법을 그대로 적용하면 된다.)
