3D (または n-D) 重心を計算する最良の方法は何ですか?

Question

仕事のプロジェクトの一環として、3D 空間内の一連の点の重心を計算する必要があります。現在、私は単純だが素朴に見える方法で、次のように各ポイントのセットの平均を取ることを行っています。

centroid = average(x), average(y), average(z)

どこ x, y そして z は浮動小数点数の配列です。より正確な重心を取得する方法があることを思い出したようですが、そのための簡単なアルゴリズムが見つかりませんでした。何かアイデアや提案がある人はいますか?これには Python を使用していますが、他の言語の例を適用することもできます。

Answer 1

ここでの一般的なリフレインとは異なり、点群の中心を定義 (および計算) するにはさまざまな方法があります。最初の最も一般的な解決策はすでにあなたによって提案されていますので、私もそうします ない これには何か問題があると主張します。

centroid = average(x), average(y), average(z)

ここでの「問題」は、ポイントの分布に応じて中心点が「歪む」ことです。たとえば、すべての点が立方体ボックスまたはその他の幾何学的形状内にあると仮定しても、そのほとんどがたまたま上半分に配置されている場合、中心点もその方向に移動します。

別の方法として、各次元の数学的中間値 (極値の平均) を使用して、これを回避することもできます。

middle = middle(x), middle(y), middle(z)

ポイントの数はあまり気にせず、グローバル境界ボックスのことを重視する場合にこれを使用できます。これは、ポイントの周囲の境界ボックスの中心だけであるためです。

最後に、次のこともできます。 median (中央の要素) 各次元:

median = median(x), median(y), median(z)

さて、これはある意味逆のことをします middle 実際に、点群内の外れ値を無視して中心点を見つけるのに役立ちます に基づく ポイントの配分。

「適切な」中心点を見つけるためのより確実な方法は、各次元の上位 10% と下位 10% を無視して、 average または median. 。ご覧のとおり、中心点はさまざまな方法で定義できます。以下に、これらの提案を念頭に置いた 2 つの 2D 点群の例を示します。

濃い青色の点は平均 (平均) 重心です。中央値は緑色で表示されます。そして真ん中が赤で表示されます。2 番目の画像では、先ほど話したことが正確にわかります。点群の最も極端な境界を考慮すると、緑の点は点群の最も密度の高い部分に「近い」ですが、赤の点は点群から遠く離れています。

Answer 2

いいえ、これが点の集合の重心を求める唯一の式です。ウィキペディアを参照: http://en.wikipedia.org/wiki/セントロイド

Answer 3

あなたは漠然と「より正確な重心を取得する方法」について言及しています。おそらく、外れ値の影響を受けない重心について話しているのでしょう。たとえば、 平均 米国の世帯収入はおそらく非常に高いでしょう。 とても 裕福な人は平均を歪めます。彼らは「外れ値」なのです。このため、統計学者は 中央値 その代わり。中央値を取得する 1 つの方法は、値を並べ替えて、リストの中ほどにある値を選択することです。

おそらく、2D または 3D ポイントのようなものを探しているかもしれません。問題は、2D 以上では並べ替えができないことです。自然な秩序などありません。それでも、外れ値を取り除く方法はあります。

1 つの方法は、 凸包 ポイントの。凸包には、すべての点が点セットの「外側」にあります。これを実行して、ハル上にあるポイントを除外すると、外れ値が除外され、残ったポイントにより、より「代表的な」重心が得られます。このプロセスを数回繰り返すと、玉ねぎの皮をむくような仕上がりになります。実際には、これは「凸包ピーリング」と呼ばれます。

Answer 4

精度を上げるための合計 (Kahan 合計) を使用できます。それは念頭に置いていたものですか?

Answer 5

より効率的になる可能性があります:これを複数回計算する場合、2 つの定常変数を保持することでかなり高速化できます。

N  # number of points
sums = dict(x=0,y=0,z=0)  # sums of the locations for each point

次に、ポイントが作成または破壊されるたびに N と合計を変更します。これにより、ポイントが作成、移動、または破棄されるたびに、計算が O(N) から O(1) に変更され、作業量が増加します。

Answer 6

「より正確な重心」 重心はあなたが計算した方法で定義されているため、「より正確な重心」は存在しないと思います。

Answer 7

はい、それが正しい式です。

多数の点がある場合は、問題の対称性 (円筒形、球形、鏡面など) を利用できます。それ以外の場合は、統計から借用してランダムな数のポイントを平均すると、多少の誤差が生じるだけです。

Answer 8

了解しました。計算しているのは重心、つまり平均ベクトルです。