Was ist der beste Weg, um einen 3D (oder n-D) Schwerpunkt zu berechnen?

Question

Im Rahmen eines Projektes bei der Arbeit habe ich den Schwerpunkt eine Reihe von Punkten im 3D-Raum zu berechnen. Im Moment mache ich es in eine Weise, die einfach, aber naiv scheint - durch den Durchschnitt jeden Satz von Punkten unter, wie in:

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

wobei x, y und z sind Anordnungen von Gleitkommazahlen. Ich glaube ich zu erinnern, dass es ein Weg gibt, um einen genaueren Schwerpunkt zu bekommen, aber ich habe nicht einen einfachen Algorithmus für so tun gefunden. Wer irgendwelche Ideen oder Anregungen? Ich benutze Python für diese, aber ich kann Beispiele aus anderen Sprachen anpassen.

Answer 1

Im Gegensatz zu dem gemeinsamen Refrain hier gibt es verschiedene Möglichkeiten (und berechnen) ein Zentrum einer Punktwolke zu definieren. Die erste und häufigste Lösung wird bereits von Ihnen vorgeschlagen, und ich will nicht argumentieren, dass es etwas falsch mit dieser ist:

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

Das „Problem“ ist hier, dass es „verzerren“ Ihr Mitte-Punkt auf der Verteilung Ihrer Punkte abhängig. Wenn zum Beispiel annehmen, dass Sie, dass alle Ihre Punkte in einem kubischen Kasten sind oder eine andere geometrische Form, aber die meisten von ihnen zufällig in der oberen Hälfte platziert werden, Ihr Mittelpunkt auch in dieser Richtung verschieben.

Als Alternative könnte man die mathematische Mitte (der Mittelwert der Extrema) in jeder Dimension verwenden, um dies zu vermeiden:

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

Sie können diese verwenden, wenn Sie viel über die Anzahl der Punkte, die nicht egal, aber mehr über den globalen Begrenzungsrahmen, denn das ist alles, das ist -. Das Zentrum des Begrenzungsrahmen um Ihre Punkte

Schließlich könnte man auch die median verwenden (das Element in der Mitte) in jeder Dimension:

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

Nun wird diese Art tun, die gegenüber dem middle und tatsächlich helfen Sie Ausreißer in Ihrer Punktwolke ignorieren und einen Mittelpunkt finden basierend auf die Verteilung Ihrer Punkte.

Eine weitere und robuste Art und Weise einen „guten“ Mittelpunkt finden könnte sein, die oberen und unteres 10% in jeder Dimension zu ignorieren und dann die average oder median zu berechnen. Wie Sie sehen können, können Sie den Mittelpunkt auf verschiedene Weise definieren. Im Folgenden wird ich Ihnen Beispiele von 2 2D-Punktwolken mit diesen Vorschlägen im Sinne bin zeigen.

Der dunkelblaue Punkt ist der Durchschnitt (arithmetisches Mittel) Schwerpunkt. Der Median ist in grün dargestellt. Und die Mitte ist in rot dargestellt. Im zweiten Bild sehen Sie, genau das, was ich sprach früher: Der grüne Punkt ist „näher“ an den dichtesten Teil der Punktwolke, während der rote Punkt aus weiter Weg ist, unter Berücksichtigung der extremsten Grenzen der Punktwolke.

Answer 2

Nein, das ist die einzige Formel für den Schwerpunkt einer Ansammlung von Punkten. Siehe Wikipedia: http://en.wikipedia.org/wiki/Centroid

Answer 3

Sie vage erwähnt „eine Möglichkeit, einen genaueren Schwerpunkt zu erhalten“. Vielleicht zu einem Schwerpunkt reden Sie, die nicht durch Ausreißer beeinflusst wird. Zum Beispiel ist der Durchschnitt Haushaltseinkommen in den USA wahrscheinlich sehr hoch, weil eine kleine Anzahl von sehr Reichen die durchschnittliche Skew; sie sind die „Ausreißer“. Aus diesem Grund verwenden die Statistiker die mittlere statt. Eine Möglichkeit, den Median zu erhalten ist, die Werte zu sortieren, dann den Wert wählt die Mitte der Liste.

Vielleicht sind Sie auf der Suche nach so etwas wie diese, aber für 2D- oder 3D-Punkte. Das Problem ist, in 2D und höher, können Sie nicht sortieren. Es gibt keine natürliche Ordnung. Dennoch gibt es Möglichkeiten, befreien von Ausreißern zu bekommen.

Eine Möglichkeit ist die konvexe Hülle der Punkte zu finden. Die konvexe Hülle hat alle Punkte auf der „Außenseite“ des Satzes von Punkten. Wenn Sie dies tun, und die Punkte werfen, die auf dem Rumpf sind, werden Sie die Ausreißer werfen, und die Punkte, die einen „repräsentativen“ Schwerpunkt geben bleiben. Sie können auch diesen Vorgang mehrmals wiederholen und das Ergebnis ist eine Art wie eine Zwiebel schälen. In der Tat ist es „konvexe Hülle Peeling“ bezeichnet.

Answer 4

Sie können Genauigkeit Summierung verwenden erhöhen - Summierung Kahan - war es das, was du im Sinn hatte?

Answer 5

Potenziell effizienter: Wenn Sie diese mehrere Male sind zu berechnen, können Sie dies auf ziemlich viel beschleunigen, indem sie zwei stehenden Variablen

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

dann Ändern N und Summen, wenn Punkte geschaffen oder zerstört werden. Dadurch ändert sich die Dinge von O (N) bis O (1) für die Berechnungen auf Kosten von mehr Arbeit jedes Mal, wenn ein Punkt erzeugt wird, bewegt oder zerstört wird.

Answer 6

A „genauer Schwerpunkt“ Ich glaube, Schwerpunkt, wie Sie es berechnet somit kann es definiert ist kein „genauer Schwerpunkt“.

Answer 7

Ja, das ist die richtige Formel.

Wenn Sie eine große Anzahl von Punkten haben Sie die Symmetrie des Problems ausnutzen können (sei es zylindrisch, sphärisch, Spiegel). Andernfalls können Sie von Statistiken ausleihen und eine Zufallszahl der Punkte im Durchschnitt und haben nur ein wenig Fehler.

Answer 8

Du hast es. Was Sie Berechnung ist der Schwerpunkt oder der mittlere Vektor.