作業中のプロジェクトの一環として、3D空間内の一連の点の重心を計算する必要があります。今のところ、私は単純に見えますが素朴な方法でそれを行っています-次のように、ポイントの各セットの平均を取ることによって。
centroid = average(x), average(y), average(z)
ここxで、、yおよびzは浮動小数点数の配列です。より正確な重心を取得する方法があることを思い出しているようですが、そのための簡単なアルゴリズムは見つかりませんでした。誰かアイデアや提案がありますか？私はこれにPythonを使用していますが、他の言語の例を適応させることができます。
「より正確な重心を取得する方法」について漠然と言及しています。外れ値の影響を受けない図心について話しているのかもしれません。たとえば、米国の平均世帯収入はおそらく非常に高いでしょう。なぜなら、少数の非常に裕福な人々が平均を歪めているからです。それらは「外れ値」です。そのため、統計家は代わりに中央値を使用します。中央値を取得する1つの方法は、値を並べ替えてから、リストの途中で値を選択することです。
たぶんあなたはこのようなものを探していますが、2Dまたは3Dポイントを探しています。問題は、2D以降では、並べ替えができないことです。自然な秩序はありません。それにもかかわらず、外れ値を取り除く方法があります。
1つの方法は、点の凸包 を見つけることです。凸包には、点のセットの「外側」にすべての点があります。これを行い、船体にあるポイントを捨てると、外れ値が捨てられ、残っているポイントはより「代表的な」重心になります。このプロセスを数回繰り返すこともでき、その結果は玉ねぎの皮をむくようなものになります。実際、それは「凸包剥離」と呼ばれています。
いいえ、これが点の集合の重心の唯一の式です。ウィキペディアを参照してください: http://en.wikipedia.org/wiki/Centroid
精度を高める総和を使用できます-カハン総和-それはあなたが念頭に置いていたものですか?
潜在的に効率的: これを複数回計算している場合、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) に変わりますが、ポイントが作成、移動、または破棄されるたびに、より多くの作業が必要になります。
「より正確な重心」重心は計算した方法で定義されるため、「より正確な重心」は存在しないと思います。
はい、それは正しい式です。
多数の点がある場合は、問題の対称性を利用できます (円筒形、球形、鏡面など)。それ以外の場合は、統計から借りて、ランダムな数のポイントを平均すると、わずかなエラーが発生する可能性があります。
了解しました。計算しているのは重心、または平均ベクトルです。