Trouver les coordonnées des points de la matrice de distance

Question

J'ai un ensemble de points (avec des coordonnées inconnues) et la matrice de distance. J'ai besoin de trouver les coordonnées de ces points pour les tracer et montrer la solution de mon algorithme.

Je peux définir un de ces points dans la coordonnée (0,0) pour simpifier et trouver les autres. Quelqu'un peut-il me dire s'il est possible de trouver les coordonnées des autres points, et si oui, comment?

Merci d'avance!

EDIT Mot de dire que je besoin des coordonnées x-y sur seulement

Answer 1

étape 1, affecter arbitrairement un point P1 (0,0).

Étape 2, affecter arbitrairement un point P2 le long de l'axe x positif. (0, Dp1p2)

Étape 3, trouver un point P3 tel que

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

et définir ce point dans le domaine y "positif" (si elle répond à l'un de ces critères, le point doit être placé sur l'axe P1P2).
Utilisez la loi du cosinus pour déterminer la distance:

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

Vous avez construit avec succès un espace orthonormé et placé trois points dans cet espace. Étape 4: Pour déterminer tous les autres points, répétez l'étape 3 pour obtenir une coordonnée y approximative. (Xn, Yn).
Comparez la distance {(Xn, Yn), (X3, Y3)} à Dp3pn dans votre matrice. Si elle est identique, vous avez identifié avec succès la coordonnée pour le point n. Sinon, le point n est à (Xn, -Yn).

Remarque Il existe une alternative à l'étape 4, mais il est trop mathématiques pour un samedi après-midi

Answer 2

Si pour les points p, q, et r vous avez pq, qr et rp dans votre matrice, vous avez un triangle. Où que vous ayez un triangle dans votre matrice, vous pouvez calculer l'une des deux solutions pour ce triangle (indépendamment d'une transformation euclidienne du triangle sur le plan). C'est-à-dire que, pour chaque triangle que vous calculez, son image miroir est aussi un triangle qui satisfait les contraintes de distance sur p, q et r. Le fait qu'il y ait deux solutions, même pour un triangle, conduit au problème de la chiralité: vous devez choisir la chiralité (orientation) de chaque triangle, et tous les choix ne peuvent pas conduire à une solution possible au problème.

Néanmoins, j'ai quelques suggestions. Si le nombre d'entrées est petit, utilisez simulated annealing. Vous pouvez incorporer la chiralité dans l'étape de recuit. Ce sera lent pour les grands systèmes, et il peut ne pas converger vers une solution parfaite, mais pour certains problèmes, c'est le meilleur que vous faites.

La deuxième suggestion ne vous donnera pas une solution parfaite, mais il va distribuer l'erreur: le method of least squares. Dans votre cas, la fonction objectif sera l'erreur entre les distances dans votre matrice, et les distances réelles entre vos points.

Answer 3

Les réponses basées sur les angles sont lourdes à mettre en œuvre et ne peuvent pas être facilement généralisées aux données de plus grandes dimensions.Une meilleure approche est celle qui est mentionnée dans mes et les réponses de WimC here: compte tenu de la matrice de distance D(i, j), définir

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

qui devrait être une matrice semi-définie positive avec rang égal à la dimension euclidienne minimale k dans laquelle les points peuvent être intégré. Les coordonnées des points peuvent alors être obtenus à partir des vecteurs propres kv(i) de M correspondant à des valeurs propres non nulles q(i): placer les vecteurs sqrt(q(i))*v(i) sous forme de colonnes dans une matrice n x kX; alors chaque ligne de X est un point. En d'autres termes, sqrt(q(i))*v(i) donne le i ème composant de tous les points.

Les valeurs propres et vecteurs propres d'une matrice peuvent être obtenus facilement dans la plupart des langages de programmation (par exemple, en utilisant GSL en C/C++, en utilisant la fonction intégrée eig dans Matlab, en utilisant Numpy en Python, etc.)

Notez que cette méthode particulière place toujours le premier point à l'origine, mais toute rotation, réflexion ou translation des points satisfera également la matrice de distance d'origine.

Answer 4

Ceci est un problème mathématique. Pour dériver la matrice de coordonnées X donnée seulement par sa matrice de distance.

Cependant, il existe une solution efficace à cette - Multidimensional Scaling, qui fait de l'algèbre linéaire. Autrement dit, il faut une matrice de distance euclidienne paire D, et la sortie est la coordonnée estimée Y (peut-être tournée), qui est une proximité de X. Pour des raisons de programmation, il suffit d'utiliser SciKit.manifold.MDS en Python.