コンテンツにスキップ

多角形のモーメントとは何か

shogo-library の多角形のライブラリには、PolygonMoment という型と polygon_edge_moment という関数があります。どちらも「面積と一次モーメント」を扱うものですが、モーメントという言葉はなじみが薄いと思います。この記事では、モーメントとは何か、なぜ重心を求めるのに便利なのか、ライブラリでは何ができるのかを説明します。

数直線上に、重さ m1,m2,…,mnm_1, m_2, \dots, m_n のおもりが位置 x1,x2,…,xnx_1, x_2, \dots, x_n に置かれているとします。このとき

  • 零次モーメント:M0=∑imiM_0 = \sum_i m_i(重さの合計)
  • 一次モーメント:M1=∑imixiM_1 = \sum_i m_i x_i(重さ × 位置の合計)
  • 二次モーメント:M2=∑imixi2M_2 = \sum_i m_i x_i^2(重さ × 位置の 2 乗の合計)

をモーメントと呼びます。kk 次モーメントは「重さ × 位置の kk 乗」の合計です。

重心(重さの平均位置)は g=M1/M0g = M_1 / M_0 です。一次モーメントを零次モーメントで割ると重心になる、というのがこの記事でいちばん大事な式です。

名前の由来はてこです。位置 cc を支点にすると、おもり ii が回そうとする強さ(力のモーメント)は mi(xi−c)m_i (x_i - c) で、合計は M1−cM0M_1 - c M_0 です。これが 00 になる、つまり釣り合う支点が c=M1/M0c = M_1 / M_0、すなわち重心です。

平面の図形 DD では、おもりの代わりに面積を重さと考え、和を積分に置き換えます。

S=∬D1 dA,Mx=∬Dx dA,My=∬Dy dAS = \iint_D 1 \, dA, \qquad M_x = \iint_D x \, dA, \qquad M_y = \iint_D y \, dA

SS は面積(零次モーメント)、(Mx,My)(M_x, M_y) は一次モーメントです。図形の重心は

(gx,gy)=(MxS,MyS)(g_x, g_y) = \left( \frac{M_x}{S}, \frac{M_y}{S} \right)

です。言いかえると、一次モーメントは「面積 × 重心」です:(Mx,My)=S⋅(gx,gy)(M_x, M_y) = S \cdot (g_x, g_y)。

モーメントは足せる、重心は足せない

Section titled “モーメントは足せる、重心は足せない”

モーメントが便利なのは、図形を分割したとき、各部分のモーメントを足すと全体のモーメントになることです。積分の範囲を分けているだけなので当然です。面積が足せるのと同じ理由で、一次モーメントも足せます。

一方、重心はそのままでは足せません。図形 AA と BB をくっつけた図形の重心は、AA の重心と BB の重心の平均ではなく、面積で重みを付けた平均

g=SAgA+SBgBSA+SBg = \frac{S_A g_A + S_B g_B}{S_A + S_B}

です。分子は一次モーメントの和、分母は面積の和なので、これは「モーメントを足してから割る」と言っているだけです。

例として、L 字形の図形 (0,0),(2,0),(2,1),(1,1),(1,2),(0,2)(0,0), (2,0), (2,1), (1,1), (1,2), (0,2) の重心を求めます。

  • 下の長方形 [0,2]×[0,1][0,2] \times [0,1]:S=2S = 2、重心 (1,0.5)(1, 0.5)、一次モーメント (2,1)(2, 1)
  • 左上の長方形 [0,1]×[1,2][0,1] \times [1,2]:S=1S = 1、重心 (0.5,1.5)(0.5, 1.5)、一次モーメント (0.5,1.5)(0.5, 1.5)

足すと S=3S = 3、一次モーメント (2.5,2.5)(2.5, 2.5) なので、重心は (2.5/3,2.5/3)=(5/6,5/6)(2.5/3, 2.5/3) = (5/6, 5/6) です。

引き算もできます。穴の開いた図形のモーメントは「外側のモーメント − 穴のモーメント」です。このように足し算と引き算ができることが、あとで累積和に載せるときに効いてきます。

多角形のモーメントを辺ごとに分解する

Section titled “多角形のモーメントを辺ごとに分解する”

三角形 a,b,ca, b, c の面積は外積で S=12(b−a)×(c−a)S = \frac{1}{2} (b - a) \times (c - a)、重心は 3 頂点の平均 a+b+c3\frac{a + b + c}{3} です。したがって一次モーメントは

S⋅a+b+c3S \cdot \frac{a + b + c}{3}

です。

原点を頂点にした三角形に分ける

Section titled “原点を頂点にした三角形に分ける”

反時計回りの多角形 p0,p1,…,pn−1p_0, p_1, \dots, p_{n-1} を、辺 pi→pi+1p_i \to p_{i+1} ごとに原点 OO と結んだ三角形 O,pi,pi+1O, p_i, p_{i+1} に分けます(pn=p0p_n = p_0)。この三角形の符号付き面積は 12 pi×pi+1\frac{1}{2} \, p_i \times p_{i+1} で、OO から見て反時計回りなら正、時計回りなら負です。

O p₀ p₁ p₂ p₃
青は正(反時計回り)の三角形、赤は負(時計回り)の三角形。太線が多角形。

図では Op0p1O p_0 p_1, Op1p2O p_1 p_2, Op2p3O p_2 p_3 の 3 つが正で、これらを合わせると多角形よりはみ出します。はみ出した部分はちょうど負の三角形 Op3p0O p_3 p_0 と重なり、打ち消されます。凹多角形でも、原点が多角形の外にあっても同じことが起き、各点は「多角形の内部なら合計 1 回、外部なら合計 0 回」数えられます(正確には、その点のまわりを多角形が何周するか、つまり回転数の回数だけ数えられます)。

面積だけでなく一次モーメントも積分なので、同じように符号付きで足せば打ち消し合いが起きます。三角形 O,pi,pi+1O, p_i, p_{i+1} の重心は pi+pi+13\frac{p_i + p_{i+1}}{3} なので、多角形全体は

S=12∑ipi×pi+1,(Mx,My)=16∑i(pi×pi+1)(pi+pi+1)S = \frac{1}{2} \sum_i p_i \times p_{i+1}, \qquad (M_x, M_y) = \frac{1}{6} \sum_i (p_i \times p_{i+1}) (p_i + p_{i+1})

となります。面積の式は、よく知られた外積で多角形の面積を求める式(靴ひも公式)そのものです。一次モーメントの式はそれを一歩進めたものです。

polygon_edge_moment(p, q) は、辺 p→qp \to q の寄与(三角形 O,p,qO, p, q の符号付き面積と一次モーメント)を返します。分母の 2 と 6 を払った値を持っているので、整数座標なら誤差なく計算できます。

メンバ中身式
area2面積の 2 倍p×qp \times q
mxxx の一次モーメントの 6 倍(p×q)(px+qx)(p \times q)(p_x + q_x)
myyy の一次モーメントの 6 倍(p×q)(py+qy)(p \times q)(p_y + q_y)

全辺の寄与を足すと、多角形全体の PolygonMoment になります。area() は area2 / 2、centroid() は

gx=MxS=mx/6area2/2=mx3⋅area2g_x = \frac{M_x}{S} = \frac{\texttt{mx} / 6}{\texttt{area2} / 2} = \frac{\texttt{mx}}{3 \cdot \texttt{area2}}

を計算しています(gyg_y も同様)。polygon_centroid は、これを全辺について足して重心を返すだけの関数です。

さきほどの L 字形で確かめると、辺ごとの (area2, mx, my) は

辺area2mxmy
(0,0)→(2,0)(0,0) \to (2,0)000
(2,0)→(2,1)(2,0) \to (2,1)282
(2,1)→(1,1)(2,1) \to (1,1)132
(1,1)→(1,2)(1,1) \to (1,2)123
(1,2)→(0,2)(1,2) \to (0,2)228
(0,2)→(0,0)(0,2) \to (0,0)000
合計61515

で、面積 6/2=36/2 = 3、重心 15/(3⋅6)=5/615 / (3 \cdot 6) = 5/6 と、長方形に分けて求めた結果と一致します。

座標が 10910^9 程度だと mx は 102710^{27} 程度になるので、整数座標のときは __int128_t で値を持ちます。

部分多角形の面積と重心を O(1)O(1) で求める

Section titled “部分多角形の面積と重心を O(1)O(1)O(1) で求める”

いちばんの使いみちです。多角形の頂点 u,u+1,…,vu, u+1, \dots, v を順に結んで閉じた部分多角形の面積や重心を、たくさん求めたいとします。

部分多角形の辺は、元の多角形の辺 u→u+1,…,v−1→vu \to u+1, \dots, v-1 \to v と、閉じる辺 v→uv \to u です。モーメントは辺ごとの寄与の和なので、前者は寄与の累積和で 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 つに切ったときの面積の差を最小化する、といった問題では、切り方ごとに両側の面積が O(1)O(1) で求まるので、尺取り法や二分探索と組み合わせられます。重心が要る問題でも同じように扱えます。

頂点 pip_i を動かすと、寄与が変わるのは辺 pi−1→pip_{i-1} \to p_i と pi→pi+1p_i \to p_{i+1} の 2 つだけです。PolygonMoment の和は結合的なので、セグメント木に載せれば、頂点の更新と部分多角形のモーメントの取得がそれぞれ O(log⁡n)O(\log n) でできます。

離れた複数の多角形をまとめた図形の重心は、それぞれの PolygonMoment を足してから centroid() を呼べば求まります。穴の開いた図形は、外側から穴を引きます。時計回りの多角形の寄与は符号が反転するので、穴を時計回りで与えれば、外側と穴の寄与をすべて足すだけでも同じ結果になります。

整数座標なら area2, mx, my はすべて整数で、重心は gx=mx/(3⋅area2)g_x = \texttt{mx} / (3 \cdot \texttt{area2}) という分数です。2 つの図形の重心の xx 座標の大小や、重心がある点と一致するかどうかは、分母を払って整数のまま比べられます(分母の符号に注意してください)。centroid() は double を返すので、厳密な判定が必要なときはメンバを直接使います。

ライブラリにはありませんが、同じ考え方で二次モーメントも辺ごとに分解できます。

Ixx=∬Dx2 dA=112∑i(pi×pi+1)(xi2+xixi+1+xi+12)I_{xx} = \iint_D x^2 \, dA = \frac{1}{12} \sum_i (p_i \times p_{i+1}) (x_i^2 + x_i x_{i+1} + x_{i+1}^2)

(xix_i は pip_i の xx 座標。IyyI_{yy} も同様)。L 字形で計算すると Ixx=3I_{xx} = 3 になり、長方形ごとに積分した 83+13\frac{8}{3} + \frac{1}{3} と一致します。

二次モーメントがあると、たとえば図形内の一様ランダムな点と点 cc の距離の 2 乗の期待値が

Ixx+IyyS−2 c⋅g+∣c∣2\frac{I_{xx} + I_{yy}}{S} - 2 \, c \cdot g + |c|^2

で求まります。物理でいう慣性モーメント(回転させにくさ)も、この Ixx+IyyI_{xx} + I_{yy} です。

  • kk 次モーメントは「重さ × 位置の kk 乗」の合計で、図形なら積分。零次は面積、一次は「面積 × 重心」
  • モーメントは図形を分割すると足し算・引き算できるが、重心はそのままでは足せない。だからモーメントで持って、最後に割る
  • 多角形は原点と各辺の三角形に符号付きで分けられるので、モーメントは辺ごとの寄与の和になる
  • 寄与の累積和を取れば、部分多角形の面積と重心が O(1)O(1) で求まる。PolygonMoment はそのための型