math - tridimensionale - php distanza tra coordinate




Trovare le coordinate dei punti dalla matrice della distanza (3)

Le risposte basate sugli angoli sono difficili da implementare e non possono essere facilmente generalizzate ai dati in dimensioni superiori. Un approccio migliore è quello menzionato nelle risposte di my e WimC qui : 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 dimensione Euclidea minima k in cui i punti possono essere incorporati. Le coordinate dei punti possono quindi essere ottenute dai k autovettori v(i) di M corrispondenti agli autovalori diversi da zero q(i) : posizionare i vettori sqrt(q(i))*v(i) come colonne in un nxk matrice X ; allora 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 gli autovettori di una matrice possono essere ottenuti facilmente nella maggior parte dei linguaggi di programmazione (ad esempio, utilizzando GSL in C / C ++, usando la funzione incorporata eig in Matlab, usando 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.

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 Hai dimenticato di dire che ho bisogno delle coordinate solo su xy


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

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

Passaggio 3, trova un punto P3 tale

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

e imposta quel punto nel dominio y "positivo" (se soddisfa uno qualsiasi di questi criteri, il punto deve essere posizionato sull'asse P1P2).
Usa 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 hai costruito con successo uno spazio ortonormale e hai posizionato 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 tua matrice. Se è identico, hai identificato correttamente le coordinate per il punto n. Altrimenti, il punto n è a (Xn, -Yn).

Nota c'è un'alternativa al passaggio 4, ma è troppa matematica per un sabato pomeriggio


Se per i punti p, qe r hai pq, qr e rp nella tua matrice, hai un triangolo.

Ovunque tu abbia un triangolo nella tua matrice, puoi 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 ricottura simulata . È 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: il metodo dei minimi quadrati . Nel tuo caso la funzione obiettivo sarà l'errore tra le distanze nella tua matrice e le distanze effettive tra i tuoi punti.





triangulation