"Schwerpunkt" zwischen einer Reihe von Punkten auf einer Toroidally-Wrapped Map, die die durchschnittliche Entfernung zu allen Punkten minimiert
edit Wie jemand gesagt hat, ist das, was ich suche, eigentlich der Punkt, der den geodätischen Gesamtabstand zwischen allen anderen Punkten minimiert.
Meine Karte ist topographisch ähnlich wie in Pac Man und Asteroiden. Wenn du an der Spitze vorbei gehst, wirst du nach unten gehen, und wenn du an der linken Seite vorbei gehst, wirst du dich nach rechts krümmen.
Sagen wir, ich habe zwei Punkte (von derselben Masse) auf der Karte und ich wollte ihren Schwerpunkt finden. Ich könnte die klassische Definition verwenden, die im Grunde der Mittelpunkt ist.
Nehmen wir jedoch an, die beiden Punkte befinden sich an gegenüberliegenden Enden der Masse. Es gibt sozusagen ein anderes Massenzentrum, das durch Umwickeln gebildet wird. Im Grunde ist es der Punkt, der zu beiden anderen Punkten äquidistant ist, aber durch "Umwickeln" der Kante verbunden ist.
Beispiel
%Vor% Zwei Punkte O . Ihr "klassischer" Mittelpunkt / Massenschwerpunkt ist der mit a markierte Punkt. Ein anderer Mittelpunkt ist jedoch auch bei b ( b ist äquidistant zu beiden Punkten, indem es umwickelt wird).
In meiner Situation möchte ich diejenige auswählen, die einen geringeren durchschnittlichen Abstand zwischen den beiden Punkten hat. In diesem Fall hat a einen durchschnittlichen Abstand zwischen den zwei Punkten von drei Schritten. b hat eine durchschnittliche Entfernung von zwei Schritten. Also würde ich b auswählen.
Eine Lösung für die Zwei-Punkt-Situation besteht darin, einfach den klassischen Mittelpunkt und den kürzesten ummittelbaren Mittelpunkt zu testen und den Knoten zu verwenden, der eine kürzere durchschnittliche Entfernung hat.
Aber! Dies lässt sich nicht leicht auf 3 Punkte oder 4 oder 5 oder n Punkte verallgemeinern.
Gibt es eine Formel oder einen Algorithmus, mit denen ich das herausfinden könnte?
(Nehmen Sie an, dass alle Punkte immer gleich groß sind. Ich verwende nur "Schwerpunkt", weil es der einzige Begriff ist, von dem ich weiß, was ich versuche zu beschreiben)
Wenn meine Erklärung unklar ist, werde ich versuchen, es besser zu erklären.
4 Antworten
Der Begriff des Massenschwerpunkts ist ein Begriff, der für affine Räume relevant ist. Der n-dimensionale Torus hat keine affine Struktur.
Was Sie wollen, ist ein Punkt, der (geodätischen) Abstand zu allen anderen Punkten minimiert.
Ich schlage folgendes vor: Sei x_1 ... x_n eine Sammlung von Punkten auf dem d-dimensionalen Torus (oder einem anderen metrischen Raum für diesen Zweck).
Ihr Problem:
Finde einen Punkt mu, so dass die Summe (dist (mu, x_k) ^ 2) minimal ist.
Im affine-euklidischen Fall erhält man den üblichen Begriff des Schwerpunkts zurück.
Dies ist ein Problem, das Sie lösen können (zum Beispiel gibt es wahrscheinlich bessere Optionen) mit dem konjugierten Gradientenalgorithmus , der in diesem Fall gut funktioniert. Beachten Sie, dass Sie ein moderates n benötigen (sagen wir n & lt; 10 ^ 3), da der Algorithmus n ^ 2 im Raum und n ^ 3 in der Zeit benötigt.
Vielleicht besser geeignet ist der Levenberg-Marquardt-Algorithmus, der auf die Minimierung der Summe der Quadrate zugeschnitten ist.
Beachten Sie, dass die Methode schneller konvergiert, wenn Sie eine gute Anfangsschätzung haben (z. B. der gewöhnliche Massenschwerpunkt der Punkte, die als Punkte in R ^ d anstelle des Torus gesehen werden).
Bearbeiten: Wenn (x1 ... xd) und (y1 ... yd) Punkte auf dem Torus sind, ist der Abstand gegeben durch dist (x, y) ^ 2 = alpha1 ^ 2 + ... + alphad ^ 2
wobei alphai = min ((xi - yi) mod 1, (yi - xi) mod 1)
Ich habe ein kleines Programm erstellt, um die Güte der beteiligten Funktionen zu überprüfen, und habe festgestellt, dass Sie mit dem Minimierungsprozess sehr vorsichtig sein sollten.
Unten sehen Sie zwei Sätze von Plots, die die Punktverteilung, die zu minimierende Funktion im euklidischen Fall und die der "torischen Metrik" entsprechende Funktion zeigen.
Wie Sie sehen, ist die euklidische Distanz sehr gut, während die torischen mehrere lokale Minima aufweisen, die das Auffinden der globalen Minima erschweren. Außerdem ist das globale Minimum im torischen Fall nicht eindeutig.
Nur für den Fall, das Programm in Mathematica ist:
%Vor%Im 1-dimensionalen Fall wäre Ihr Problem analog zum Finden eines mittleren Winkels. Der Mittelwert der Winkel a und b kann durch
berechnet werdenMittelwert = Rest (a + Rest (b-a, C) / 2,0, C) Dabei ist C das Maß eines ganzen Kreises (dh 2 * PI, wenn Sie Radiant verwenden).
Wenn Sie n Winkel a [] haben, kann der Mittelwert mit
berechnet werdenMittelwert = a [0]; für i = 1..n Mittelwert = Rest (Mittelwert + Rest (a [i] -Mittel, C) / (i + 1), C)
Also ich denke
meanX = X [0]; meanY = Y [0]
für i = 1..n
%Vor%könnte den Job erledigen.
Beachten Sie jedoch, dass dies zu -W / 2 & lt; = meanX führt
IANATopologe, und ich weiß nicht, wie klar ich mich darin mache, aber für was es wert ist, das sind einige Gedanken zu diesem Thema:
Die Verwendung von Masse und Gravitation zur Berechnung dieser Art von Dingen mag in der Tat elegant sein - ISTR, dass es eine Reihe von Bibliotheken und effizienten Algorithmen gibt, um die Gravitationsvektoren für eine beliebige Anzahl von Massen zu finden.
Wenn Sie eine sphärische Karte verwenden würden, würde ich vorschlagen, innerhalb der Kugel den tatsächlichen Schwerpunkt für Ihre N Massepunkte zu finden. Dann zeichnen Sie eine Linie von der Mitte nach außen durch diesen inneren Schwerpunkt, um den Punkt auf der Kugeloberfläche zu finden, an dem sich Ihre Massenpunkte versammeln möchten.
Eine toroidale Karte erschwert dies jedoch.
Mein Vorschlag ist also, Ihre Map zu verflachen und zu kopieren, um Ihnen eine 3 x 3-Quilt-Karte zu geben (mit einem unendlichen Feld von Maps werden bessere Ergebnisse erzielt, aber es könnte zu viel werden). Ich gebe ihnen die Koordinaten (0, 0) zu (2, 2), wobei (1, 1) deine Quellkarte ist. Finde die Punkte, zu denen die Massenpunkte deiner inneren Karte (1, 1) hingezogen werden - wenn sie alle in die Mitte deiner Karte gehen, gut: du hast deinen Schwerpunkt gefunden. Wenn nicht, wenn einer der Punkte in der Nähe der Kante in Richtung einer Massenakkumulation außerhalb Ihrer inneren Karte geht, sagen wir in Karte (2, 1), dann verwerfen Sie diesen Massenpunkt, wenn Sie Ihren Schwerpunkt berechnen. Stattdessen verwenden Sie den Massepunkt von der gegenüberliegenden Karte (in diesem Fall (0, 1)), der in Ihre mittlere Karte wandern möchte.
Wenn Sie die Beschleunigungsvektoren für diese Massepunkte hinzufügen, erhalten Sie den Schwerpunkt auf Ihrem Torus. Fertig.
Tags und Links algorithm language-agnostic math geometry topology