TIL: ピックの定理とShoelace formulaすごいぞ！

今年もAdvent of Codeにぼちぼちと参加しています。その中で、ピックの定理とShoelace formulaを知ったので簡単にまとめておきます！

Advent of Codeについてはこちらも↓

ピックの定理とは

すべての頂点が二次元格子点上に存在する多角形の面積を求める公式です。

$\displaystyle A=i+\frac{1}{2}b-1$

ここでAは多角形の面積、iは多角形の内側の格子点数、bは多角形の辺上の格子点数です。

詳細はこちら。証明は別として非常にわかりやすい公式であり、中学生で習う人もいるようですね。

頂点座標列から多角形の面積を求める公式です。こちらは台形の面積を考えれば証明も容易と思います。詳細はこちら。

$\displaystyle A=\frac{1}{2}\sum^n_{i=1}(y_i+y_{i+1})(x_i-x_{i+1})$

ここで $P_i=(x_i, y_i)$ は多角形の i 番目の頂点です。( $1 \le i \le n$ 。また、ループする $P_{n+1}=P_1$ )。頂点を巡る順番によっては面積が負の数になるため、実用上は最後に絶対値をとってしまうのが楽です。

日本だと座標法とか、そのまま靴紐の公式とか、ガウスの面積公式などと呼ばれるようです。ま　た　ガウス　か！

この2つを組み合わせると、多角形内の格子点数を簡単に求めることができます！

今、多角形の頂点座標の配列は得られているとします。

まずは面積Aを Shoelace formula で求めましょう。これは全頂点座標をループすれば容易に得られます。

次に辺上の格子点数bを数えましょう。これは辺が軸に平行であれば、隣り合う頂点の座標を引き算するだけで求められます。

これらの値A, bを使えば、ピックの定理で多角形内の格子点数iが求まります。

$\displaystyle i = A - \frac{1}{2}b + 1$

簡単ながら強力。すごい！！

こんな多角形でも簡単です。これで動物たちの巣の面積が求まりました！

こんなのでも、変わらず適用できます。これでエルフが溶岩を何リットル保持できるかわかりました！

計算量が頂点数に比例するのも良い点です！どんなに大きな図形でも頂点が少なければ素早く答えが得られます。やった！

これらはSimple polygonでしか使うことができません。つまり、辺が交差する多角形や、穴の空いた多角形では単純に適用できないと思われます。今のところAoCではそうした条件が出題されてないため、その場合の対応方法は調べきれていません。
軸に平行でない辺がある場合は、辺上の格子点数は一筋縄では求められないはずです。しかしこの場合もまだ出題されてないので (以下略
頂点が格子点でない場合の一般的な問題は、Point in polygonと呼ばれます。Rayを飛ばして辺と交差する回数を数えるのが基本ですが、計算量は数える点の個数に比例します。このため、今年のDay18 part2のように大きな多角形の場合は、特にピックの定理が活きます。
初めてはてなでTex記法を使いましたが、絶妙にダサくて残念です！

抱卵も終わり、また元気に飛び回っています。