신발끈 공식에 관한 고찰 - 1. 증명

고등학교 수학의 최종병기라고 하면 몇가지가 떠오릅니다. 로피탈 정리, 여러가지 근사... 그리고 신발끈 공식.

이들은 모두 고등학교에서 정식적으로 배우지는 않지만, 신기하게도 많은 학생들이 알고있는 테크닉입니다. 특히 신발끈 공식은 다양한 방법으로 응용되어 사용될 수 있으므로, 그것에 관해 약간의 고찰을 해보는 시간을 갖겠습니다. 

 

신발끈 공식이란?

그림 1: 일반적인 삼각형

위와 같은 삼각형이 주어졌을때, 이 삼각형의 넓이는 어떻게 구할까요? 밑변과 높이의 길이를 하나하나 구하기에는 너무나 힘들어 보입니다. 이 때 쓸 수 있는 공식이 바로 신발끈 공식 (Shoelace Formula) 입니다.

 

반시계 방향으로 점 $\mathrm{P}_1$, $\mathrm{P}_2$, $\mathrm{P}_3$가 주어졌을 때, 삼각형의 넓이 $A$는 다음과 같습니다.

$$A = \frac{1}{2} \begin{vmatrix} x_1 & x_2 & x_3 & x_1 \\ y_1 & y_2 & y_3 & y_1 \end{vmatrix}$$

 

여기서 $| \cdots |$ 부분은 이렇게 계산합니다.

붉은 화살표로 이어진 것끼리 곱한 뒤 모두 더하고, 푸른 화살표로 이어진 것끼리 곱한 뒤 빼면 됩니다. 즉, 삼각형의 넓이는 다시 이렇게 쓸 수 있겠습니다.

$$A = \frac{1}{2} | (x_1 y_2 + x_2 y_3 + x_3 y_1) - (x_2 y_1 + x_3 y_2 + x_1 y_3)|$$

 

우리의 목적은 넓이를 구하는 것이므로, 절댓값을 취해서 양수로 만들어 줘야겠죠. 

그럼, 이것을 간단히 증명해보겠습니다.

 

삼각형 신발끈 공식의 증명

신발끈 공식은 벡터의 외적으로 증명할 수 있습니다.

 

외적으로 증명하기 위해서, 위에 있는 삼각형(그림 1)이 $z = 0$평면 위에 있다고 가정해도 일반성을 잃지 않습니다. 벡터 $\mathbf{v}_1 = \overrightarrow{\mathrm{P}_1 \mathrm{P}_2}$, $\mathbf{v}_2 = \overrightarrow{\mathrm{P}_1 \mathrm{P}_3}$ 라고 정의합니다.

 

벡터의 외적의 크기는, 두 벡터가 만드는 평행사변형의 넓이와 같으므로, 삼각형의 넓이는 그것의 절반임을 알 수 있습니다.

즉, 삼각형의 넓이는 다음과 같습니다.

$$A = \frac{1}{2} \| \mathbf{v}_1 \times \mathbf{v}_2 \|$$

여기서 $\mathbf{v}_1 = (x_2 - x_1, y_2 - y_1 , 0)$, $\mathbf{v}_2 = (x_3 - x_1, y_3 - y_1, 0)$ 이므로 외적의 크기를 계산하면 다음이 나옵니다.

$$A = \frac{1}{2} | (x_1 y_2 + x_2 y_3 + x_3 y_1) - (x_2 y_1 + x_3 y_2 + x_1 y_3)|$$

■

---

위 증명에서 삼각형의 넓이를 구하기 위해, 외적의 크기($>0$)를 구했지만, 실제로 외적의 $z$방향($\mathbf{e}_3$) 값은 부호가 있습니다. 우리는 오른손 좌표계를 쓰므로, 양수 값을 얻기 위해서는 반시계 방향으로 외적을 계산하고, 그렇기 때문에 신발끈 공식을 사용하기 위해 삼각형의 점을 설정할 때 반시계 방향으로 점을 설정하게 되죠.

 

다른 표현

신발끈 공식은 생긴것이 마치 행렬식 같습니다. 신기하게도 행렬식으로도 표현할 수 있고, 그것이 훨씬 깔끔합니다.

공식을 유심히 보면 다음과 같다는 것을 알 수 있을 것입니다.

$$A = \frac{1}{2} \left | \sum_{i = 1} ^ 3 (x_{i+1} + x_i) (y_{i+1} - y_i) \right |$$

여기서 약간의 대수적인 계산을 하면 다음을 얻을 수 있죠.

$$A = \frac{1}{2} \left | \sum_{i = 1} ^ 3 \det \begin{pmatrix}x_i & x_{i+1} \\ y_i & y_{i+1} \end{pmatrix} \right |$$

더 깔끔하지 않나요? 단, 여기서 $x_4 = x_1$,  $y_4 = y_1$ 입니다.

 

이렇게 썼을 때 좋은 점은, 확장이 편하다는 것입니다. 지면도 낭비하지 않고, 시그마 위의 첨자만 바꿔주면 되니까요.

그럼 확장을 해봅시다.

 

신발끈 공식의 확장

그림 2: 단순 다각형

위와 같은 단순 n각형이 있습니다. (단순 다각형은, 쉽게 말해 모든 변이 꼭짓점에서만 만나는(self-intersect 하지 않는) 다각형을 말합니다) 이 다각형의 넓이는 어떻게 구할 수 있을까요? 바로, 여러개의 삼각형으로 분할하면 됩니다. 삼각형의 넓이를 구하는 법은 이미 알기 때문이죠.

 

$\mathrm{P}_1$을 기준으로 각 점을 잇는 유향선분(벡터)을 $\mathbf{v}_i = \overrightarrow{\mathrm{P}_1 \mathrm{P}_{i+1}}$로 정의하면,(단, $i = 1,\cdots, n-1$) 그림 2에서도 볼 수 있듯이 다음의 삼각형 $T_i$ 을 생각할 수 있습니다.

$$T_i = \{ m \mathbf{v}_i + n \mathbf{v}_{i+1} : m+n \le 1, m \ge 0, n \ge 0 \}$$

이러한 $T_i$는 사실상 다각형의 분할입니다. 다만, 그림 2와 같이 다각형과 겹치는 부분도 있고, 그렇지 않은 부분도 있기에 다각형의 넓이를 구할 때, 단순히 삼각형의 넓이의 합이 아닌, 부호가 포함된 넓이의 합으로 구해야 합니다. (자연적인 소거를 위해서)

따라서, 부호가 포함된 $T_i$의 넓이 $A_i$는 다음과 같습니다.

$$A_i = \frac{1}{2} (\mathbf{v}_i \times \mathbf{v}_{i+1}) \cdot \mathbf{e} _3$$

 

이로써 다각형의 넓이를 구할 준비를 모두 마쳤습니다. 그럼, 남은건 계산뿐입니다.

 

계산...

다각형의 넓이 $A$는 다음과 같습니다.

$$A = \sum_{i = 1} ^{n-2} A_i = \frac{1}{2} \sum_{i = 1} ^{n-2} (\mathbf{v}_i \times \mathbf{v}_{i+1}) \cdot \mathbf{e} _3$$

왜 $i$가 $n-2$까지 인가 하면, $n$각형은 총 $n-2$개의 삼각형으로 분할되기 때문이죠. 

 

여기서 $\mathbf{v}_i = (x_{i+1} - x_1 , y_{i+1} - y_1, 0)$, $\mathbf{v}_{i+1} = (x_{i+2} - x_1 , y_{i+2} - y_1, 0)$ 이므로, 이 둘을 외적하면,

$$\begin{array}{rcl} \mathbf{v}_i \times \mathbf{v}_{i+1} & = & \{ (x_{i+1} - x_1)(y_{i+2} - y_1) - (x_{i+2} - x_1)(y_{i+1}-y_1) \} \mathbf{e}_3 \\ & = & \{ (x_{i+1} y_{i+2} - x_{i+2} y_{i+1}) + x_1 (y_{i+1} - y_{i+2}) + y_1 (x_{i+2} - x_{i+1}) \} \mathbf{e}_3 \end{array}$$

계속 계산을 해주면,

$$\begin{array}{rcl} A & = & \dfrac{1}{2} \sum\limits_{i = 1} ^{n-2} (\mathbf{v}_i \times \mathbf{v}_{i+1}) \cdot \mathbf{e} _3 \\ &=& \dfrac{1}{2} \left \{ \sum\limits_{i = 1} ^{n-2} (x_{i+1} y_{i+2} - x_{i+2} y_{i+1} ) + \sum\limits_{i = 1} ^{n-2} x_1 (y_{i+1} - y_{i+2}) + \sum\limits_{i = 1} ^{n-2} y_1 (x_{i+2} - x_{i+1}) \right \} \\ &=& \dfrac{1}{2} \left \{ \sum\limits_{i = 1} ^{n-2} (x_{i+1} y_{i+2} - x_{i+2} y_{i+1} ) + x_1 y_2 - x_2 y_1 + x_n y_1 - x_1 y_n \right \} \\ &=& \dfrac{1}{2} \left \{ \sum\limits_{i = 1} ^{n-1} (x_{i} y_{i+1} - x_{i+1} y_{i} ) + x_n y_1 - x_1 y_n \right \} \end{array}$$

여기서 $x_1 = x_{n+1}$, $y_1 = y_{n+1}$이라 하면,

$$A = \frac{1}{2} \sum_{i = 1} ^ {n} (x_i y_{i+1} - x_{i+1} y_i) = \frac{1}{2} \sum_{i = 1} ^ {n} \det \begin{pmatrix}x_i & x_{i+1} \\ y_i & y_{i+1} \end{pmatrix}$$

이 됩니다. 넓이를 얻고 싶으면 절댓값을 취해주면 되겠네요. (어차피 반시계 방향으로 점을 설정하면 자연스럽게 양수의 답이 나옵니다)

■

 

---

이렇게 신발끈 공식은 삼각형 뿐만 아니라, 단순 다각형의 넓이를 구하는 데 용이하게 쓸 수 있습니다. 이렇게요.

n각형에서의 신발끈 공식

그럼 신발끈 공식은 오직 넓이 구할 때만 사용될까요? 우린 신발끈 공식에서 넓이($>0$)에만 치중한 나머지, 하나 놓치고 지나간 것이 있습니다. 바로, 부호죠.

외적으로부터의 증명에서도 알 수 있듯이, 오른손 좌표계 (반시계 방향)으로 계산하면 양수가 나오고, 시계방향으로 계산하면 음수가 나옴을 알 수 있습니다. 두 벡터가 평행하면 0이 나온다는 사실도 알 수 있겠죠. 

 

그럼, 반대로, 세 점이 순서대로 주어졌을 때, 그 점들이 시계 방향으로 정렬되어 있는지, 반시계 방향으로 정렬되어 있는지, 아니면 평행한지 알 수 있지 않을까요?

 

 

언젠가 이어서...!

 

References

https://artofproblemsolving.com/wiki/index.php/Shoelace_Theorem

Antti Laaksonen, Competitive Programmer’s Handbook