삼각형의 유향 넓이¶
세 점 $p_1$, $p_2$, $p_3$이 주어질 때, 이 점들이 이루는 삼각형의 유향(부호 있는) 넓이를 계산하십시오. 넓이의 부호는 다음과 같이 정해집니다. 평면 위의 점 $p_1$에 서서 $p_2$를 바라보고 있다고 상상해 보십시오. $p_2$로 이동했을 때 $p_3$이 오른쪽에 있으면(이때 세 벡터가 "시계 방향"으로 회전한다고 합니다) 넓이의 부호는 음수이고, 그렇지 않으면 양수입니다. 세 점이 한 직선 위에 있으면 넓이는 0입니다.
이 부호 있는 넓이를 사용하면 일반적인 부호 없는 넓이(부호 있는 넓이의 절댓값)를 구할 수 있을 뿐만 아니라, 주어진 순서대로 놓인 점들이 시계 방향인지 반시계 방향인지도 판별할 수 있습니다(이는 예를 들어 볼록 껍질 알고리즘에서 유용합니다).
계산¶
$2\times 2$ 행렬의 행렬식이 그 행렬의 열(또는 행) 벡터들이 만드는 평행사변형의 부호 있는 넓이와 같다는 사실을 이용할 수 있습니다. 이는 2차원에서의 외적의 정의와 유사합니다(기초 기하학을 참고하십시오). 이 넓이를 2로 나누면 우리가 구하려는 삼각형의 넓이를 얻습니다. $\vec{p_1p_2}$와 $\vec{p_2p_3}$을 열 벡터로 사용하여 $2\times 2$ 행렬식을 계산하겠습니다:
$$2S=\left|\begin{matrix}x_2-x_1 & x_3-x_2\\y_2-y_1 & y_3-y_2\end{matrix}\right|=(x_2-x_1)(y_3-y_2)-(x_3-x_2)(y_2-y_1)$$
구현¶
int signed_area_parallelogram(point2d p1, point2d p2, point2d p3) {
return cross(p2 - p1, p3 - p2);
}
double triangle_area(point2d p1, point2d p2, point2d p3) {
return abs(signed_area_parallelogram(p1, p2, p3)) / 2.0;
}
bool clockwise(point2d p1, point2d p2, point2d p3) {
return signed_area_parallelogram(p1, p2, p3) < 0;
}
bool counter_clockwise(point2d p1, point2d p2, point2d p3) {
return signed_area_parallelogram(p1, p2, p3) > 0;
}