ポリゴンの重心を求める

アルゴリズム

点Pi(i = 0 ~ n - 1)によって作られるポリゴンについて考える。

1. 初期化 P = (0, 0, 0), area_sum = 0.0
2. ポリゴンの各点Pi(i = 1 ~ n - 2)について次の計算を繰り返す。
   1. ベクトルP0-Pi、P0-Pi+1の外積を2で割った値(a)を求める。
      これは符号付の三角形(P0、Pi、Pi+1)の面積になる。
   2. P0、Pi、Pi+1によって作られる三角形の中心点(Pc)を求める。
   3. area_sum += a
   4. P += a * Pc
3. P /= area_sum
4. Pが求める重心点である。

三角形の中心点を求める

1. ある点の中線を求める。
   中線とはある点と、その対辺の中点とを結んだ直線である。
2. もう一つの点の中線を求める。
3. 上の二つの中線の交点(Pc)が求める中心点になる。

注意

辺同士が交わるようなポリゴンに対しては上のアルゴリズムは成り立たない。