多角形のモーメントとは何か
shogo-library の多角形のライブラリには、PolygonMoment という型と polygon_edge_moment という関数があります。どちらも「面積と一次モーメント」を扱うものですが、モーメントという言葉はなじみが薄いと思います。この記事では、モーメントとは何か、なぜ重心を求めるのに便利なのか、ライブラリでは何ができるのかを説明します。
モーメントとは
Section titled “モーメントとは”点の集まりの場合
Section titled “点の集まりの場合”数直線上に、重さ のおもりが位置 に置かれているとします。このとき
- 零次モーメント:(重さの合計)
- 一次モーメント:(重さ × 位置の合計)
- 二次モーメント:(重さ × 位置の 2 乗の合計)
をモーメントと呼びます。 次モーメントは「重さ × 位置の 乗」の合計です。
重心(重さの平均位置)は です。一次モーメントを零次モーメントで割ると重心になる、というのがこの記事でいちばん大事な式です。
名前の由来はてこです。位置 を支点にすると、おもり が回そうとする強さ(力のモーメント)は で、合計は です。これが になる、つまり釣り合う支点が 、すなわち重心です。
平面の図形 では、おもりの代わりに面積を重さと考え、和を積分に置き換えます。
は面積(零次モーメント)、 は一次モーメントです。図形の重心は
です。言いかえると、一次モーメントは「面積 × 重心」です:。
モーメントは足せる、重心は足せない
Section titled “モーメントは足せる、重心は足せない”モーメントが便利なのは、図形を分割したとき、各部分のモーメントを足すと全体のモーメントになることです。積分の範囲を分けているだけなので当然です。面積が足せるのと同じ理由で、一次モーメントも足せます。
一方、重心はそのままでは足せません。図形 と をくっつけた図形の重心は、 の重心と の重心の平均ではなく、面積で重みを付けた平均
です。分子は一次モーメントの和、分母は面積の和なので、これは「モーメントを足してから割る」と言っているだけです。
例として、L 字形の図形 の重心を求めます。
- 下の長方形 :、重心 、一次モーメント
- 左上の長方形 :、重心 、一次モーメント
足すと 、一次モーメント なので、重心は です。
引き算もできます。穴の開いた図形のモーメントは「外側のモーメント − 穴のモーメント」です。このように足し算と引き算ができることが、あとで累積和に載せるときに効いてきます。
多角形のモーメントを辺ごとに分解する
Section titled “多角形のモーメントを辺ごとに分解する”三角形 の面積は外積で 、重心は 3 頂点の平均 です。したがって一次モーメントは
です。
原点を頂点にした三角形に分ける
Section titled “原点を頂点にした三角形に分ける”反時計回りの多角形 を、辺 ごとに原点 と結んだ三角形 に分けます()。この三角形の符号付き面積は で、 から見て反時計回りなら正、時計回りなら負です。
図では , , の 3 つが正で、これらを合わせると多角形よりはみ出します。はみ出した部分はちょうど負の三角形 と重なり、打ち消されます。凹多角形でも、原点が多角形の外にあっても同じことが起き、各点は「多角形の内部なら合計 1 回、外部なら合計 0 回」数えられます(正確には、その点のまわりを多角形が何周するか、つまり回転数の回数だけ数えられます)。
面積だけでなく一次モーメントも積分なので、同じように符号付きで足せば打ち消し合いが起きます。三角形 の重心は なので、多角形全体は
となります。面積の式は、よく知られた外積で多角形の面積を求める式(靴ひも公式)そのものです。一次モーメントの式はそれを一歩進めたものです。
ライブラリの PolygonMoment
Section titled “ライブラリの PolygonMoment”polygon_edge_moment(p, q) は、辺 の寄与(三角形 の符号付き面積と一次モーメント)を返します。分母の 2 と 6 を払った値を持っているので、整数座標なら誤差なく計算できます。
| メンバ | 中身 | 式 |
|---|---|---|
area2 | 面積の 2 倍 | |
mx | の一次モーメントの 6 倍 | |
my | の一次モーメントの 6 倍 |
全辺の寄与を足すと、多角形全体の PolygonMoment になります。area() は area2 / 2、centroid() は
を計算しています( も同様)。polygon_centroid は、これを全辺について足して重心を返すだけの関数です。
さきほどの L 字形で確かめると、辺ごとの (area2, mx, my) は
| 辺 | area2 | mx | my |
|---|---|---|---|
| 0 | 0 | 0 | |
| 2 | 8 | 2 | |
| 1 | 3 | 2 | |
| 1 | 2 | 3 | |
| 2 | 2 | 8 | |
| 0 | 0 | 0 | |
| 合計 | 6 | 15 | 15 |
で、面積 、重心 と、長方形に分けて求めた結果と一致します。
座標が 程度だと mx は 程度になるので、整数座標のときは __int128_t で値を持ちます。
何ができるか
Section titled “何ができるか”部分多角形の面積と重心を で求める
Section titled “部分多角形の面積と重心を O(1)O(1)O(1) で求める”いちばんの使いみちです。多角形の頂点 を順に結んで閉じた部分多角形の面積や重心を、たくさん求めたいとします。
部分多角形の辺は、元の多角形の辺 と、閉じる辺 です。モーメントは辺ごとの寄与の和なので、前者は寄与の累積和で で求まり、そこに閉じる辺の寄与を 1 つ足せば完成です。PolygonMoment は + と - が使えるので、そのまま累積和に載せられます。頂点の番号が一周をまたぐ場合もあるので、円環上の区間和 CircularSum を使うと便利です。
using P = Vector<long long>;std::vector<PolygonMoment<long long>> e(n);for (int i = 0; i < n; i++) e[i] = polygon_edge_moment(ps[i], ps[(i + 1) % n]);CircularSum cs(e);// 頂点 u, u+1, ..., v を結んだ部分多角形auto m = cs.sum(u, v) + polygon_edge_moment(ps[v], ps[u]);m.area(); // 符号付き面積m.centroid(); // 重心辺の寄与は原点の位置によって変わりますが、閉じた多角形について足した合計は原点によりません(打ち消し合いの議論は原点の位置を問わないからです)。途中までの和だけでは意味のある値にならず、閉じる辺を足して初めて部分多角形の値になる、という点に注意してください。
凸多角形を対角線で 2 つに切ったときの面積の差を最小化する、といった問題では、切り方ごとに両側の面積が で求まるので、尺取り法や二分探索と組み合わせられます。重心が要る問題でも同じように扱えます。
頂点を動かしながら求める
Section titled “頂点を動かしながら求める”頂点 を動かすと、寄与が変わるのは辺 と の 2 つだけです。PolygonMoment の和は結合的なので、セグメント木に載せれば、頂点の更新と部分多角形のモーメントの取得がそれぞれ でできます。
図形を足したり引いたりする
Section titled “図形を足したり引いたりする”離れた複数の多角形をまとめた図形の重心は、それぞれの PolygonMoment を足してから centroid() を呼べば求まります。穴の開いた図形は、外側から穴を引きます。時計回りの多角形の寄与は符号が反転するので、穴を時計回りで与えれば、外側と穴の寄与をすべて足すだけでも同じ結果になります。
重心を誤差なく比較する
Section titled “重心を誤差なく比較する”整数座標なら area2, mx, my はすべて整数で、重心は という分数です。2 つの図形の重心の 座標の大小や、重心がある点と一致するかどうかは、分母を払って整数のまま比べられます(分母の符号に注意してください)。centroid() は double を返すので、厳密な判定が必要なときはメンバを直接使います。
二次モーメント
Section titled “二次モーメント”ライブラリにはありませんが、同じ考え方で二次モーメントも辺ごとに分解できます。
( は の 座標。 も同様)。L 字形で計算すると になり、長方形ごとに積分した と一致します。
二次モーメントがあると、たとえば図形内の一様ランダムな点と点 の距離の 2 乗の期待値が
で求まります。物理でいう慣性モーメント(回転させにくさ)も、この です。
- 次モーメントは「重さ × 位置の 乗」の合計で、図形なら積分。零次は面積、一次は「面積 × 重心」
- モーメントは図形を分割すると足し算・引き算できるが、重心はそのままでは足せない。だからモーメントで持って、最後に割る
- 多角形は原点と各辺の三角形に符号付きで分けられるので、モーメントは辺ごとの寄与の和になる
- 寄与の累積和を取れば、部分多角形の面積と重心が で求まる。
PolygonMomentはそのための型