多角形の面積公式

AtCoderにて、有志の方によって提供されている競プロの典型問題41の解説[1]にて、式の理解に大分時間がかかってしまいました。勉強もかねて、せっかくなのでまとめます。

1. 目標の式
2. ベクトルの外積と三角形の面積
3. 多角形の三角形への分割
4. 式の変形
5. 式の意味

解説[1]の3ページ目に載っていた、以下の多角形の面積を求める式を理解することを目標とします。

$s=\frac{1}{2}\left|\mathrm{\sum }_{\mathrm{i}=1}^N\right(x_i\mathrm{ - }{x}_{i+1}\left)\right(y_i\mathrm{ + }{y}_{i+1}\left)\right|$

三角形の面積を求める方法として、ベクトルの外積を利用できます。
ベクトルの外積の定義は以下の2通り[2]があります。

1. 空間ベクトル $\overrightarrow{a}$ と $\overrightarrow{b}$ にたいして、長さが $\left|\overrightarrow{a}\right|\left|\overrightarrow{b}\right|\mathrm{sin\theta }$ で、 $\overrightarrow{a}$ と $\overrightarrow{b}$ に垂直なベクトル
2. 成分表示された2本の空間ベクトル $\overrightarrow{a}=\left(a_x\mathrm{ , }{a}_y\mathrm{ , }{a}_z\right)$ 、 $\overrightarrow{b}=\left(b_x\mathrm{ , }{b}_y\mathrm{ , }{b}_z\right)$ に対して、 $(a_y{b}_z-a_z{b}_y\mathrm{ , }{a}_z{b}_x-a_x{b}_z\mathrm{ , }{a}_x{b}_y-a_y{b}_x)$ という成分で表されるベクトル

ここで、 $\left|\overrightarrow{a}\right|\left|\overrightarrow{b}\right|\mathrm{sin\theta }$ は $\overrightarrow{a}$ と $\overrightarrow{b}$ がなす平行四辺形の面積と等しいです。
ただし、θによっては値が負になることがあることに注意が必要です。

平行四辺形の面積がでたら、これを半分にすれば三角形の面積になります。
また、 $\overrightarrow{a}$ と $\overrightarrow{b}$ がxy平面上にあるとしたら $a_z=b_z=0$ となるので、定義2の式から、 $\left(0\mathrm{ , }0\mathrm{ , }{a}_x{b}_y-a_y{b}_x\right)$ となります。これが平行四辺形の面積の大きさとなるので、三角形の面積は(正負はおいておいて)、$\frac{1}{2}(a_x{b}_y-a_y{b}_x)$になります。

図のように多角形は三角形に分割できます。

△OAB、△OBC、△OCD、△ODAの面積が出せれば、四角形の面積を出せます。図は四角形ですが、他の多角形でも同様に分割できます。
つまり、この多角形の面積は各三角形の面積の和である、

$s=\frac{1}{2}\left|\mathrm{\sum }_{\mathrm{i}=1}^N\right(x_i{y}_{\mathrm{i+1}}-y_i{x}_{\mathrm{i+1}}\left)\right|$

となります。
ただし、

です。

ここまでの話は、 こちらのサイト [3]で詳しく書いてあるので、合わせて参考にしてください。
原点を内部に含まない場合、各三角形の面積が正負でいい感じに打ち消しあうことに注意が必要です。

多角形の面積を求める式も導出できたので、これで終わり……、とはなりません。改めて解説の式と、導出した式を並べてみます。

1. $s=\frac{1}{2}\left|\mathrm{\sum }_{\mathrm{i}=1}^N\right(x_i-x_{i+1}\left)\right(y_i+y_{i+1}\left)\right|$
2. $s=\frac{1}{2}\left|\mathrm{\sum }_{\mathrm{i}=1}^N(x_i{y}_{i+1}-y_i{x}_{i+1})\right|$

よく見ると絶対値の中身が違います。ということで、式変形して一致することを確かめましょう。
それぞれの式でi = k-1、kの値をとりだし、 $x_k$ ・ $y_k$ について比較します。

• 1の式
$\left(x_{\mathrm{k-1}}-x_{\mathrm{k}}\right)\left(y_{\mathrm{k-1}}+y_k)+(x_k-x_{\mathrm{k+1}}\right)\left(y_k+y_{\mathrm{k+1}}\right)$
• $x_k$ の係数
$-\left(y_{\mathrm{k-1}}+y_k\right)+\left(y_k+y_{\mathrm{k+1}}\right)=-y_{\mathrm{k-1}}+y_{\mathrm{k+1}}$
• $y_k$ の係数
$\left(x_{\mathrm{k-1}}-x_{\mathrm{k}}\right)+\left(x_k-x_{\mathrm{k+1}}\right)=x_{\mathrm{k-1}}-x_{\mathrm{k+1}}$
• 2の式
$\left(x_{\mathrm{k-1}}{y}_k-y_{\mathrm{k-1}}{x}_k\right)+(x_k{y}_{\mathrm{k+1}}-y_k{x}_{\mathrm{k+1}})$
• $x_k$ の係数
$-y_{\mathrm{k-1}}+y_{\mathrm{k+1}}$
• $y_k$ の係数
$x_{\mathrm{k-1}}-x_{\mathrm{k+1}}$

係数が一致することを確認出来ました。

同値であることの確認はしましたが、直接何を表しているのかが結局わからずじまいです。
xの差とyの平均(最後に2で割ることから)を利用して何かしてるんですかね、一体どこの面積を持ってきているのか。

調べていたら、考察を見つけました(式変形についても書いてありました)[4]。
x軸と登場する2点からの垂線と2点を結んだ線分から作成される台形の面積らしいです。 三角形を使っているとばかり思っていましたが、これで納得です。
名前もついているらしく、倍横距法というらしいです[5]
積分から考えると、面積を求めるのに台形を使って考えるのは自然ですね。

以上、多角形の面積公式から解説の式を飲み込むところまで整理しました。式の違いは、三角形に分割するか、台形に分割するかという分割方法の違いから生まれてましたね。

今後の課題は、典型41関連として、ピックの定理の証明やfloorsumについて確認することです。
とまぁ、今後の課題も見つかったので、今回はここまで。 ではまた。