Finden der Koordinaten der Punkte aus der Distanzmatrix

Ich habe eine Menge von Punkten (mit unbekannten Koordinaten) und die Distanzmatrix. Ich muss die Koordinaten dieser Punkte finden, um sie zu zeichnen und die Lösung meines Algorithmus zu zeigen.Finden der Koordinaten der Punkte aus der Distanzmatrix

Ich kann einen dieser Punkte in der Koordinate (0,0) zur Vereinfachung festlegen und die anderen finden. Kann mir jemand sagen, ob es möglich ist, die Koordinaten der anderen Punkte zu finden, und wenn ja, wie?

Vielen Dank im Voraus!

EDIT vergessen zu sagen, dass ich die Koordinaten x-y nur

Quelle

2012-06-09 Trino00

Das ... wird eine Menge Brute-Forcing brauchen ... –

Betrachten Sie drei Punkte (ein Dreieck). Es gibt zwei Orientierungen und eine unendliche Anzahl von Drehungen, die die gleiche Abstandsmatrix ergeben würden. –

Ein Schritt weiter, sprechen wir einen eindimensionalen Raum, oder zwei oder drei oder vier .... Die Antwort wird sich in jedem Fall ändern. Nach (0,0), sollten wir seine zweidimensionale akzeptieren? – Rasman

Schritt 1, beliebig zuordnen einem Punkt P1 als (0,0) benötigen.

Schritt 2, beliebig einen Punkt P2 entlang der positiven x-Achse zuweisen. (0, Dp1p2)

Schritt 3, einen Punkt P3 finden, so dass

Dp1p2 ~= Dp1p3+Dp2p3 
Dp1p3 ~= Dp1p2+Dp2p3 
Dp2p3 ~= Dp1p3+Dp1p2

und stellt diesen Punkt in dem „positiven“ Y-Bereich (wenn es eines dieser Kriterien erfüllt, soll der Punkt gesetzt werden, auf der P1P2-Achse).
die Cosinusgesetz Verwenden Sie den Abstand zu bestimmen:

cos (A) = (Dp1p2^2 + Dp1p3^2 - Dp2p3^2)/(2*Dp1p2* Dp1p3) 
P3 = (Dp1p3 * cos (A), Dp1p3 * sin(A))

Sie haben erfolgreich einen orthonormal Raum gebaut jetzt und legte drei Punkte in diesem Raum.

Schritt 4: Um alle anderen Punkte zu bestimmen, wiederholen Sie Schritt 3, um eine vorläufige y-Koordinate zu erhalten. (Xn, Yn).
Vergleichen Sie den Abstand {(Xn, Yn), (X3, Y3)} zu Dp3pn in Ihrer Matrix. Wenn es identisch ist, haben Sie die Koordinate für Punkt n erfolgreich identifiziert. Sonst ist der Punkt n bei (Xn, -Yn).

Hinweis gibt es eine Alternative zu Schritt 4, aber es ist zu viel Mathe für einen Samstagnachmittag

Quelle

2012-06-09 18:11:02 Rasman

@BrunoBruck das Kosinusgesetz geben den Winkel (die erste Gleichung) zwischen P1P2 und P1P3. Der nächste Teil besteht darin, die Projektion von P3 auf die P1P2-Achse zu erhalten. Wenn Sie den Abstand P1P3 kennen und ihn als Hypotenuse eines Dreiecks definieren, sind die X- und Y-Werte einfach die Kosinus- bzw. Sinus-Zeiten der Hypotenuse. – Rasman

Was Sie mit P2 gemacht haben, ist in Ordnung, aber im Fall von P3 kann ich keinen Punkt meiner Menge auswählen, der nicht in der gleichen Linie von P1 und P2 ist, und sicher sagen, dass er auf der Y-Achse ist. – Trino00

Ok, ich glaube ich habe es verstanden. Zuerst geben wir an, dass P3 auf der y-Achse liegt, um ein rechtes Dreieck zu erhalten, und in diesem Fall können wir die Gleichungen für die Koordinaten erstellen. Aber wir kennen den tatsächlichen Abstand zwischen P3 und P2, so dass wir den realen Winkel zwischen P1P2 und P1P3 erhalten können, und in den Gleichungen für die Koordinaten können wir die realen Werte für Xp3 und Yp3 erhalten. Habe ich richtig verstanden? – Trino00

Wenn für die Punkte p, q und r Sie pq haben, qr und rp in Ihrer Matrix, Sie haben ein Dreieck.

Wo immer Sie ein Dreieck in Ihrer Matrix haben, können Sie eine von zwei Lösungen für dieses Dreieck berechnen (unabhängig von einer euklidischen Transformation des Dreiecks in der Ebene). Das heißt, für jedes von Ihnen berechnete Dreieck ist das Spiegelbild auch ein Dreieck, das die Abstandsbeschränkungen für p, q und r erfüllt. Die Tatsache, dass es sogar zwei Lösungen für ein Dreieck gibt, führt zu dem Chiralitätsproblem: Man muss die Chiralität (Orientierung) jedes Dreiecks wählen, und nicht jede Wahl kann zu einer realisierbaren Lösung des Problems führen.

Trotzdem habe ich ein paar Vorschläge. Wenn die Anzahl der Einträge klein ist, sollten Sie in Betracht ziehen, simulated annealing zu verwenden. Sie könnten Chiralität in den Glühschritt einbauen. Dies wird bei großen Systemen langsam sein, und es kann nicht zu einer perfekten Lösung konvergieren, aber für einige Probleme ist es das Beste, was Sie tun.

Der zweite Vorschlag gibt Ihnen keine perfekte Lösung, aber es wird den Fehler verteilen: method of least squares. In Ihrem Fall ist die Zielfunktion der Fehler zwischen den Entfernungen in Ihrer Matrix und den tatsächlichen Entfernungen zwischen Ihren Punkten.

Quelle

2012-06-09 18:20:02

Danke für die Antwort. Ich weiß nicht, ob dies der beste Ansatz ist, weil ich in manchen Fällen sehr viele Punkte habe und eine Metaheuristik nicht immer die optimale Lösung oder in diesem Fall eine praktikable Lösung liefert. Ich könnte also viel Zeit damit verbringen und bekomme immer noch keine brauchbare Antwort. – Trino00

@DeepYellow: Ich mag deine Antwort teilweise, weil sie helfen kann, eine andere, schwierigere Frage zu beantworten, die gestern von einem anderen Benutzer gestellt wurde. Ich versuchte diese andere Frage zu beantworten und scheiterte. Wenn die Herausforderung Sie interessiert, hier ist die URL: http://stackoverflow.com/questions/10957359/minimal-rectangle-containing-all-intersections-of-lines – thb

@thb: Danke für das Zeigen dieser Frage aus. Ich habe gepostet, was ich für eine korrekte Lösung halte, lass mich wissen, was du denkst. –

Die auf Winkeln basierenden Antworten sind umständlich zu implementieren und können nicht einfach auf Daten in höheren Dimensionen verallgemeinert werden.Ein besserer Ansatz ist, dass in meinem und WimC die Antworten erwähnt here: angesichts der Distanzmatrix D(i, j) definieren

M(i, j) = 0.5*(D(1, j)^2 + D(i, 1)^2 - D(i, j)^2)

, die eine positive Halb definite Matrix mit Rang gleich dem minimalen euklidischen Dimension sein sollte k, in dem die Punkte eingebettet sein. Die Koordinaten der Punkte können dann aus den k Eigenvektoren erhalten werden v(i) von M zu Nicht-Null-Eigenwerten entsprechen q(i): Platzieren der Vektoren sqrt(q(i))*v(i) als Spalten in einer Matrix n x kX; dann ist jede Reihe von X ein Punkt. Mit anderen Worten, sqrt(q(i))*v(i) gibt die i te Komponente aller Punkte an.

die Eigenwerte und Eigenvektoren einer Matrix kann in den meisten Programmiersprachen leicht erhalten werden (zum Beispiel unter Verwendung von GSL in C/C++, die eingebaute Funktion eig in Matlab, Numpy in Python, etc.)

Beachten Sie, dass diese bestimmte Methode immer den ersten Punkt im Ursprung platziert, aber jede Drehung, Reflexion oder Translation der Punkte entspricht auch der ursprünglichen Abstandsmatrix.

Quelle

2013-06-18 20:01:41 Legendre17

Dies sollte die Antwort sein. Es gibt keine Notwendigkeit, es selbst zu kodieren, Multi-Dimensional Scaling-Funktionen können in Python oder R gefunden werden. –

Dies ist ein mathematisches Problem. Um die Koordinatenmatrix X abzuleiten, die nur durch ihre Abstandsmatrix gegeben ist.

Allerdings gibt es eine effiziente Lösung - Multidimensional Scaling, die einige lineare Algebra tun. Einfach ausgedrückt, es erfordert eine paarweise euklidische Abstandsmatrix D, und die Ausgabe ist die geschätzte Koordinate Y (vielleicht gedreht), die eine Nähe zu X ist. Aus Gründen der Programmierung verwenden Sie einfach SciKit.manifold.MDS in Python.

Quelle

2015-09-15 23:02:39 Hualin

Finden der Koordinaten der Punkte aus der Distanzmatrix

Antwort

Verwandte Themen