다각형의 점이 순서대로 주어질 때, 다각형의 넓이를 구하는 문제입니다. n각형은 삼각형 n-2개로 나타낼 수 있다는 것을 생각해보면 쉽게 풀 수 있습니다. 그리고 삼각형의 두 벡터가 주어지면($(X_1,Y_1),(X_2,Y_2)$) 그 넓이는 $\frac{1}{2}(X_1 Y_2-X_2 Y_1)$으로 구할 수 있습니다. 이제 주어진 다각형에 대해 첫 번째 점 $P_0$는 계속 저장해두고, 삼각형 $P_0 P_k P_{k+1}$의 넓이를 위의 식을 사용해서 계속 구하면 됩니다. 그런데 오목한 다각형에 대해서는 어떻게 하냐고요? 위의 식을 사용하면 더해야 하는 넓이의 부호와 빼야 하는 넓이의 부호가 반대로 나옵니다. 그 이유는 위의 넓이 공식은 정확히는 외적이기 때문입니다. 그러면 오목한 다각형이라도 자동으로 알맞은 넓이가 나옵니다.
이 문제를 푸는 간단한 공식으로 신발끈 공식이 있다고 합니다. 삼각형에 대해 넓이를 구하는 공식은 위의 식을 참고해보면 아래와 같이 쓸 수 있습니다.
\[S=\frac{1}{2}(X_1 Y_2-X_2 Y_1)\\
=\frac{1}{2}((x_1-x_0)(y_2-y_0) - (x_2-x_0)(y_1-y_0))\\
=\frac{1}{2}(x_1y_2-x_0y_2-x_1y_0-x_2y_1+x_0y_1+x_2y_0)\\
=\frac{1}{2}(x_0y_1+x_1y_2+x_2y_0-x_1y_0-x_2y_1-x_0y_2)\]
이제 귀납법을 사용하여 n각형에 대해 식이 아래와 같음을 보일 수 있습니다.
\[S=\frac{1}{2}(x_0y_1+x_1y_2+x_2y_3+...+x_{n-1}y_0\\-x_1y_0-x_2y_1-x_3y_2-...-x_0y_{n-1})\]
증명은 생략합니다.뭐요? 이를 사용하면 더욱 쉽게 다각형의 넓이를 구할 수 있습니다.
PS알못 OrbitHv의 PS