n角形の重心を求めるアルゴリズム

質問

平面2次元のn角形の頂点のデータがあります。n点の座標ですから(x,y)がn個並んでいます。そのような図形の図心（重心）の座標を計算するアルゴリズムがないでしょうか。最終的にはプログラムとして離散的な処理をするため、１％ぐらいの誤差は許容範囲です。n角形と言ってもせいぜいn=3,4,5,6程度です。

欲を言うと、３次元も考えており、平面に含まれることが分かっているn個の点（３次元空間内）を平面の２次元空間に変換して重心を求め、それを３次元空間に引き戻せば３次元での重心となります。そのためにも２次元での重心の座標を求めるアルゴリズムが必要なのです。

よろしくお願いします。

回答No.2

arrysthmia · ベストアンサー

ｎ角形の頂点を、辺を一周する順に番号付けて P[k],　k = 0,1,2,…,n-1 とします。

図形を分割すると、重心は、分割された各部品の重心を、各部品の面積で加重平均
したものになりますから、同じ平面内に点 Q をとって、
△QP[k]P[k+1],　k = 0,1,2,…,n-1 （ただし P[n] は P[0] の別名とする）
の重心 (Q + P[k] + P[k+1]) / 3 を、△QP[k]P[k+1] の面積を重みとして
加重平均すればよいことになります。Q は、P[n-1] を採用してかまいません。

その際、△QP[k]P[k+1] がｎ角形の中にあるか外にあるかに従って、面積に正負を
付けて扱う必要があるため、面積 △QP[k]P[k+1] = (1/2)|↑QP[k]×↑QP[k+1]| の
替わりに、絶対値をつけない ↑QP[k]×↑QP[k+1] そのものを重みとして扱うほうが
便利でしょう。スカラーの計算で済ますために、ｎ角形が乗っている面に平行でない
ベクトル V をひとつ固定して、↑QP[k]×↑QP[k+1]・V を重みにすれば、尚よい。
外積との内積だから、スカラー三重積ですね。平面の方程式が既知ならば、その
法線ベクトルが V として使えるし、そうでなければ、V = ↑QP[0]×↑QP[1] と
してもよいです。

以上まとめると…
Q = P[n-1] とする。
V = ↑QP[0]×↑QP[1] とする。
k = 0,1,2,…,n-3 の夫々について、
　　X[k] = (Q + P[k] + P[k+1]) / 3 と
　　w[k] = ↑QP[k]×↑QP[k+1]・V を求める。
重心は、(Σ w[k] X[k]) / (Σ w[k]) である。

← No.1
順序付けの自動化は、原理的に無理でしょう。
頂点の集合が同じでも、順序付けが異なると、ｎ角形は別のものになる訳ですから。

お礼

回答有難うございます。
紙と鉛筆で外積と内積を計算したらすぐにプログラムが組めそうです。Ｑを多角形の構成点P[n-1]にするというのもなるほどと思います。アルゴリズム上Qは平面上のどの点でもよいことになると思いますが、物凄く遠方だったら精度は落ちていくでしょうから構成点付近にしておくというのは分かります。全構成点の単純平均でも良いかも知れません。

有難うございました。

回答No.3

gatch_ky

公式を即席で作りました。

0=(0,0)
a=(a1,a2)
b=(b1,b2)
c=(c1,c2)
として
ベクトルa,b,cが時計と反対まわりとする。
三角形0,a,bの重心g(0,a,b)と面積S(0,a,b)
重心・・・g(0,a,b)=(a+b)/3
面積・・・S(0,a,b)=(a×b)/2=(a1*b2-a2*b1)/2

四角形0,a,b,cの重心は
(S(0,a,b)*g(0,a,b)+S(0,b,c)*g(0,b,c))/(S(0,a,b)+S(0,b,c))

n角形でも同じ

お礼

回答有難うございます。
基本は、ｎ角形を頂点を１つ共有する3角形でn-2個に分割し、その各3角形の重心を面積の重み付き平均すればよいということですか。
また、重心の座標がg(0,a,b)=(a+b)/3という簡単な式に表示できるとは知りませんでした。中学校の数学で内心、外心などともに出てきたでしょうか。すっかり抜け落ちておりました。

回答No.1

noname#101087

一例です。

　http://www5d.biglobe.ne.jp/~noocyte/Programming/Geometry/PolygonMoment-jp.html#Problem
>多角形の面積，重心(図心)，断面Ｎ次モーメントの公式 ......

頂点座標の順序付けをしておくと、あとの勘定が楽チンなのですね。
順序付けの「アルゴ」も探せばありそう ..... 。

お礼

このサイトは有用でした。有難うございます。
どこかにあるはずだとは思っていましたが。このようなプログラムって理論は簡単で実際にやってみるとややこしくて、加齢によるボケ封じにはもってこいなのですが、世界に１つだけあればいいプログラムですから、コツコツやるとイライラしてくるものですよね。