shogo-library の多角形のライブラリ には、PolygonMoment という型と polygon_edge_moment という関数があります。どちらも「面積と一次モーメント」を扱うものですが、モーメントという言葉はなじみが薄いと思います。この記事では、モーメントとは何か、なぜ重心を求めるのに便利なのか、ライブラリでは何ができるのかを説明します。
数直線上に、重さ m 1 , m 2 , … , m n m_1, m_2, \dots, m_n m 1 , m 2 , … , m n のおもりが位置 x 1 , x 2 , … , x n x_1, x_2, \dots, x_n x 1 , x 2 , … , x n に置かれているとします。このとき
零次モーメント :M 0 = ∑ i m i M_0 = \sum_i m_i M 0 = ∑ i m i (重さの合計)
一次モーメント :M 1 = ∑ i m i x i M_1 = \sum_i m_i x_i M 1 = ∑ i m i x i (重さ × 位置の合計)
二次モーメント :M 2 = ∑ i m i x i 2 M_2 = \sum_i m_i x_i^2 M 2 = ∑ i m i x i 2 (重さ × 位置の 2 乗の合計)
をモーメントと呼びます。k k k 次モーメントは「重さ × 位置の k k k 乗」の合計です。
重心(重さの平均位置)は g = M 1 / M 0 g = M_1 / M_0 g = M 1 / M 0 です。一次モーメントを零次モーメントで割ると重心になる、というのがこの記事でいちばん大事な式です。
名前の由来はてこです。位置 c c c を支点にすると、おもり i i i が回そうとする強さ(力のモーメント)は m i ( x i − c ) m_i (x_i - c) m i ( x i − c ) で、合計は M 1 − c M 0 M_1 - c M_0 M 1 − c M 0 です。これが 0 0 0 になる、つまり釣り合う支点が c = M 1 / M 0 c = M_1 / M_0 c = M 1 / M 0 、すなわち重心です。
平面の図形 D D D では、おもりの代わりに面積を重さと考え、和を積分に置き換えます。
S = ∬ D 1 d A , M x = ∬ D x d A , M y = ∬ D y d A S = \iint_D 1 \, dA, \qquad M_x = \iint_D x \, dA, \qquad M_y = \iint_D y \, dA S = ∬ D 1 d A , M x = ∬ D x d A , M y = ∬ D y d A
S S S は面積(零次モーメント)、( M x , M y ) (M_x, M_y) ( M x , M y ) は一次モーメントです。図形の重心は
( g x , g y ) = ( M x S , M y S ) (g_x, g_y) = \left( \frac{M_x}{S}, \frac{M_y}{S} \right) ( g x , g y ) = ( S M x , S M y )
です。言いかえると、一次モーメントは「面積 × 重心」です:( M x , M y ) = S ⋅ ( g x , g y ) (M_x, M_y) = S \cdot (g_x, g_y) ( M x , M y ) = S ⋅ ( g x , g y ) 。
モーメントが便利なのは、図形を分割したとき、各部分のモーメントを足すと全体のモーメントになる ことです。積分の範囲を分けているだけなので当然です。面積が足せるのと同じ理由で、一次モーメントも足せます。
一方、重心はそのままでは足せません。図形 A A A と B B B をくっつけた図形の重心は、A A A の重心と B B B の重心の平均ではなく、面積で重みを付けた平均
g = S A g A + S B g B S A + S B g = \frac{S_A g_A + S_B g_B}{S_A + S_B} g = S A + S B S A g A + S B g 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 , 0 ) , ( 2 , 0 ) , ( 2 , 1 ) , ( 1 , 1 ) , ( 1 , 2 ) , ( 0 , 2 ) の重心を求めます。
下の長方形 [ 0 , 2 ] × [ 0 , 1 ] [0,2] \times [0,1] [ 0 , 2 ] × [ 0 , 1 ] :S = 2 S = 2 S = 2 、重心 ( 1 , 0.5 ) (1, 0.5) ( 1 , 0.5 ) 、一次モーメント ( 2 , 1 ) (2, 1) ( 2 , 1 )
左上の長方形 [ 0 , 1 ] × [ 1 , 2 ] [0,1] \times [1,2] [ 0 , 1 ] × [ 1 , 2 ] :S = 1 S = 1 S = 1 、重心 ( 0.5 , 1.5 ) (0.5, 1.5) ( 0.5 , 1.5 ) 、一次モーメント ( 0.5 , 1.5 ) (0.5, 1.5) ( 0.5 , 1.5 )
足すと S = 3 S = 3 S = 3 、一次モーメント ( 2.5 , 2.5 ) (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) ( 2.5/3 , 2.5/3 ) = ( 5/6 , 5/6 ) です。
引き算もできます。穴の開いた図形のモーメントは「外側のモーメント − 穴のモーメント」です。このように足し算と引き算ができる ことが、あとで累積和に載せるときに効いてきます。
三角形 a , b , c a, b, c a , b , c の面積は外積で S = 1 2 ( b − a ) × ( c − a ) S = \frac{1}{2} (b - a) \times (c - a) S = 2 1 ( b − a ) × ( c − a ) 、重心は 3 頂点の平均 a + b + c 3 \frac{a + b + c}{3} 3 a + b + c です。したがって一次モーメントは
S ⋅ a + b + c 3 S \cdot \frac{a + b + c}{3} S ⋅ 3 a + b + c
です。
反時計回りの多角形 p 0 , p 1 , … , p n − 1 p_0, p_1, \dots, p_{n-1} p 0 , p 1 , … , p n − 1 を、辺 p i → p i + 1 p_i \to p_{i+1} p i → p i + 1 ごとに原点 O O O と結んだ三角形 O , p i , p i + 1 O, p_i, p_{i+1} O , p i , p i + 1 に分けます(p n = p 0 p_n = p_0 p n = p 0 )。この三角形の符号付き 面積は 1 2 p i × p i + 1 \frac{1}{2} \, p_i \times p_{i+1} 2 1 p i × p i + 1 で、O O O から見て反時計回りなら正、時計回りなら負です。
O
p₀
p₁
p₂
p₃
青は正(反時計回り)の三角形、赤は負(時計回り)の三角形。太線が多角形。
図では O p 0 p 1 O p_0 p_1 O p 0 p 1 , O p 1 p 2 O p_1 p_2 O p 1 p 2 , O p 2 p 3 O p_2 p_3 O p 2 p 3 の 3 つが正で、これらを合わせると多角形よりはみ出します。はみ出した部分はちょうど負の三角形 O p 3 p 0 O p_3 p_0 O p 3 p 0 と重なり、打ち消されます。凹多角形でも、原点が多角形の外にあっても同じことが起き、各点は「多角形の内部なら合計 1 回、外部なら合計 0 回」数えられます(正確には、その点のまわりを多角形が何周するか、つまり回転数の回数だけ数えられます)。
面積だけでなく一次モーメントも積分なので、同じように符号付きで足せば打ち消し合いが起きます。三角形 O , p i , p i + 1 O, p_i, p_{i+1} O , p i , p i + 1 の重心は p i + p i + 1 3 \frac{p_i + p_{i+1}}{3} 3 p i + p i + 1 なので、多角形全体は
S = 1 2 ∑ i p i × p i + 1 , ( M x , M y ) = 1 6 ∑ i ( p i × p i + 1 ) ( p i + p i + 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}) S = 2 1 i ∑ p i × p i + 1 , ( M x , M y ) = 6 1 i ∑ ( p i × p i + 1 ) ( p i + p i + 1 )
となります。面積の式は、よく知られた外積で多角形の面積を求める式(靴ひも公式)そのものです。一次モーメントの式はそれを一歩進めたものです。
polygon_edge_moment(p, q) は、辺 p → q p \to q p → q の寄与(三角形 O , p , q O, p, q O , p , q の符号付き面積と一次モーメント)を返します。分母の 2 と 6 を払った値を持っているので、整数座標なら誤差なく計算できます。
メンバ 中身 式 area2面積の 2 倍 p × q p \times q p × q mxx x x の一次モーメントの 6 倍( p × q ) ( p x + q x ) (p \times q)(p_x + q_x) ( p × q ) ( p x + q x ) myy y y の一次モーメントの 6 倍( p × q ) ( p y + q y ) (p \times q)(p_y + q_y) ( p × q ) ( p y + q y )
全辺の寄与を足すと、多角形全体の PolygonMoment になります。area() は area2 / 2、centroid() は
g x = M x S = mx / 6 area2 / 2 = mx 3 ⋅ area2 g_x = \frac{M_x}{S} = \frac{\texttt{mx} / 6}{\texttt{area2} / 2} = \frac{\texttt{mx}}{3 \cdot \texttt{area2}} g x = S M x = area2 /2 mx /6 = 3 ⋅ area2 mx
を計算しています(g y g_y g y も同様)。polygon_centroid は、これを全辺について足して重心を返すだけの関数です。
さきほどの L 字形で確かめると、辺ごとの (area2, mx, my) は
辺 area2mxmy( 0 , 0 ) → ( 2 , 0 ) (0,0) \to (2,0) ( 0 , 0 ) → ( 2 , 0 ) 0 0 0 ( 2 , 0 ) → ( 2 , 1 ) (2,0) \to (2,1) ( 2 , 0 ) → ( 2 , 1 ) 2 8 2 ( 2 , 1 ) → ( 1 , 1 ) (2,1) \to (1,1) ( 2 , 1 ) → ( 1 , 1 ) 1 3 2 ( 1 , 1 ) → ( 1 , 2 ) (1,1) \to (1,2) ( 1 , 1 ) → ( 1 , 2 ) 1 2 3 ( 1 , 2 ) → ( 0 , 2 ) (1,2) \to (0,2) ( 1 , 2 ) → ( 0 , 2 ) 2 2 8 ( 0 , 2 ) → ( 0 , 0 ) (0,2) \to (0,0) ( 0 , 2 ) → ( 0 , 0 ) 0 0 0 合計 6 15 15
で、面積 6 / 2 = 3 6/2 = 3 6/2 = 3 、重心 15 / ( 3 ⋅ 6 ) = 5 / 6 15 / (3 \cdot 6) = 5/6 15/ ( 3 ⋅ 6 ) = 5/6 と、長方形に分けて求めた結果と一致します。
座標が 10 9 10^9 1 0 9 程度だと mx は 10 27 10^{27} 1 0 27 程度になるので、整数座標のときは __int128_t で値を持ちます。
いちばんの使いみちです。多角形の頂点 u , u + 1 , … , v u, u+1, \dots, v u , u + 1 , … , v を順に結んで閉じた部分多角形の面積や重心を、たくさん求めたいとします。
部分多角形の辺は、元の多角形の辺 u → u + 1 , … , v − 1 → v u \to u+1, \dots, v-1 \to v u → u + 1 , … , v − 1 → v と、閉じる辺 v → u v \to u v → u です。モーメントは辺ごとの寄与の和なので、前者は寄与の累積和で 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 ]);
// 頂点 u, u+1, ..., v を結んだ部分多角形
auto m = cs . sum ( u , v ) + polygon_edge_moment ( ps [ v ], ps [ u ]);
辺の寄与は原点の位置によって変わりますが、閉じた多角形について足した合計は原点によりません(打ち消し合いの議論は原点の位置を問わないからです)。途中までの和だけでは意味のある値にならず、閉じる辺を足して初めて部分多角形の値になる、という点に注意してください。
凸多角形を対角線で 2 つに切ったときの面積の差を最小化する、といった問題では、切り方ごとに両側の面積が O ( 1 ) O(1) O ( 1 ) で求まるので、尺取り法や二分探索と組み合わせられます。重心が要る問題でも同じように扱えます。
頂点 p i p_i p i を動かすと、寄与が変わるのは辺 p i − 1 → p i p_{i-1} \to p_i p i − 1 → p i と p i → p i + 1 p_i \to p_{i+1} p i → p i + 1 の 2 つだけです。PolygonMoment の和は結合的なので、セグメント木に載せれば、頂点の更新と部分多角形のモーメントの取得がそれぞれ O ( log n ) O(\log n) O ( log n ) でできます。
離れた複数の多角形をまとめた図形の重心は、それぞれの PolygonMoment を足してから centroid() を呼べば求まります。穴の開いた図形は、外側から穴を引きます。時計回りの多角形の寄与は符号が反転するので、穴を時計回りで与えれば、外側と穴の寄与をすべて足すだけでも同じ結果になります。
整数座標なら area2, mx, my はすべて整数で、重心は g x = mx / ( 3 ⋅ area2 ) g_x = \texttt{mx} / (3 \cdot \texttt{area2}) g x = mx / ( 3 ⋅ area2 ) という分数です。2 つの図形の重心の x x x 座標の大小や、重心がある点と一致するかどうかは、分母を払って整数のまま比べられます(分母の符号に注意してください)。centroid() は double を返すので、厳密な判定が必要なときはメンバを直接使います。
ライブラリにはありませんが、同じ考え方で二次モーメントも辺ごとに分解できます。
I x x = ∬ D x 2 d A = 1 12 ∑ i ( p i × p i + 1 ) ( x i 2 + x i x i + 1 + x i + 1 2 ) 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) I xx = ∬ D x 2 d A = 12 1 i ∑ ( p i × p i + 1 ) ( x i 2 + x i x i + 1 + x i + 1 2 )
(x i x_i x i は p i p_i p i の x x x 座標。I y y I_{yy} I y y も同様)。L 字形で計算すると I x x = 3 I_{xx} = 3 I xx = 3 になり、長方形ごとに積分した 8 3 + 1 3 \frac{8}{3} + \frac{1}{3} 3 8 + 3 1 と一致します。
二次モーメントがあると、たとえば図形内の一様ランダムな点と点 c c c の距離の 2 乗の期待値が
I x x + I y y S − 2 c ⋅ g + ∣ c ∣ 2 \frac{I_{xx} + I_{yy}}{S} - 2 \, c \cdot g + |c|^2 S I xx + I y y − 2 c ⋅ g + ∣ c ∣ 2
で求まります。物理でいう慣性モーメント(回転させにくさ)も、この I x x + I y y I_{xx} + I_{yy} I xx + I y y です。
k k k 次モーメントは「重さ × 位置の k k k 乗」の合計で、図形なら積分。零次は面積、一次は「面積 × 重心」
モーメントは図形を分割すると足し算・引き算できるが、重心はそのままでは足せない。だからモーメントで持って、最後に割る
多角形は原点と各辺の三角形に符号付きで分けられるので、モーメントは辺ごとの寄与の和になる
寄与の累積和を取れば、部分多角形の面積と重心が O ( 1 ) O(1) O ( 1 ) で求まる。PolygonMoment はそのための型