Ricerca delle coordinate dei punti dalla matrice delle distanze

Question

Ho una serie di punti (con coordinate sconosciute) e la matrice della distanza. Devo trovare le coordinate di questi punti per tracciarli e mostrare la soluzione del mio algoritmo.

Posso impostare uno di questi punti nella coordinata (0,0) per semplificare e trovare gli altri. Qualcuno può dirmi se è possibile trovare le coordinate degli altri punti, e se sì, come?

Grazie in anticipo!

EDIT dimenticato di dire che ho bisogno le coordinate x-y solo

Answer 1

Fase 1, arbitrariamente assegnare un punto P1 come (0,0).

Passaggio 2, assegnare arbitrariamente un punto P2 lungo l'asse x positivo. (0, Dp1p2)

Fase 3, trovare un punto P3 tale che

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

e impostare quel punto nel dominio y "positivo" (se soddisfa uno di questi criteri, il punto deve essere collocato sull'asse P1P2).
usare la legge del coseno per determinare la distanza:

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

Ora avete costruito con successo uno spazio ortonormale e messo tre punti in quello spazio.

Passaggio 4: per determinare tutti gli altri punti, ripetere il passaggio 3 per fornire una coordinata y provvisoria. (Xn, Yn).
Confronta la distanza {(Xn, Yn), (X3, Y3)} a Dp3pn nella matrice. Se è identico, hai identificato correttamente le coordinate per il punto n. Altrimenti, il punto n è a (Xn, -Yn).

notare v'è un'alternativa al punto 4, ma è troppo matematica per un pomeriggio di Sabato

Answer 2

Se per i punti p, q, e r avete pq, QR, e rp nel vostro matrice, hai un triangolo.

Ovunque si abbia un triangolo nella matrice, è possibile calcolare una delle due soluzioni per quel triangolo (indipendentemente da una trasformazione euclidea del triangolo sul piano). Cioè, per ogni triangolo che calcoli, la sua immagine speculare è anche un triangolo che soddisfa i vincoli di distanza su p, qe r. Il fatto che ci siano due soluzioni anche per un triangolo porta al problema della chiralità: devi scegliere la chiralità (orientamento) di ogni triangolo, e non tutte le scelte possono portare a una soluzione fattibile al problema.

Tuttavia, ho alcuni suggerimenti. Se le voci del numero sono piccole, prendere in considerazione l'utilizzo di simulated annealing. È possibile incorporare la chiralità nel passaggio di ricottura. Questo sarà lento per i sistemi di grandi dimensioni, e potrebbe non convergere in una soluzione perfetta, ma per alcuni problemi è meglio che tu e tu faccia.

Il secondo suggerimento non ti darà una soluzione perfetta, ma distribuirà l'errore: lo method of least squares. Nel tuo caso la funzione obiettivo sarà l'errore tra le distanze nella tua matrice e le distanze effettive tra i tuoi punti.

Answer 3

Le risposte basate su angoli sono difficili da implementare e non possono essere facilmente generalizzate ai dati di dimensioni superiori.Un approccio migliore è quella menzionata nelle mie e WimC delle risposte here: data la matrice di distanza D(i, j), definire

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

che dovrebbe essere una matrice semi-definita positiva con rango uguale alla minima dimensione euclidea k in cui i punti possono essere incorporato Le coordinate dei punti possono essere ottenuti dai k autovettori v(i) di M corrispondenti a autovalori non nulli q(i): Consiglio di vettori sqrt(q(i))*v(i) come colonne in una matrice n x kX; quindi ogni riga di X è un punto. In altre parole, sqrt(q(i))*v(i) fornisce il componente i di tutti i punti.

Gli autovalori e autovettori di una matrice può essere ottenuto facilmente in molti linguaggi di programmazione (ad esempio, utilizzando GSL in C/C++, utilizzando la funzione incorporata eig in Matlab, utilizzando Numpy in Python, ecc)

Si noti che questo particolare metodo posiziona sempre il primo punto all'origine, ma qualsiasi rotazione, riflesso o traslazione dei punti soddisferà anche la matrice della distanza originale.

Answer 4

Questo è un problema di matematica. Per derivare la matrice di coordinate X solo data dalla sua matrice di distanza.

Tuttavia c'è una soluzione efficiente a questo - Scaling multidimensionale, che fa qualche algebra lineare. In parole semplici, richiede una matrice di distanza Euclidea a coppie e l'uscita è la coordinata stimata Y (forse ruotata), che è una prossimità a X. Per ragioni di programmazione, basta usare SciKit.manifold.MDS in Python.