Matrices distances vers coordonées

[Cliffe]

Bonjour,

Je demande de l'aide pour mettre au point un algo qui me donne les coordonnées (x,y) de 'n' points sachant que je connais les distances entre chaque paire de points (sous forme de matrice).

Exemple : 3 points A, B et C avec :
[CENTER]
[/CENTER]

ça nous donne un triangle que l'on peut pivoter et translater dans tous les sens :

[CENTER] [/CENTER]

[fatal_error]

salut,

tu peux déjà considérer A(0,0) et B(4,0)
ensuite tu prends un point (par exemple C)
C a deux possibilités (vu la symétrie avec [AB])

t'es libre tu places n'importe ou.
Ensuite tu prends D.
tu regardes A et B.
D a deux possibilités.
Tu regardes pour ces deux possibilités laquelle respecte la distance DC. Tu places D.

etc...

[Skullkid]

Bonjour, pour mettre de l'eau au moulin, l'algorithme décrit par fatal_error a une complexité linéaire (juste, ne pas oublier les tests pour vérifier que la matrice correspond bien à un ensemble de points, ils peuvent se faire au fur et à mesure, à partir du troisième point) donc c'est sans doute dur de faire mieux.

Edit : en fait si on fait tous les tests sur la matrice ça va plutôt donner une complexité quadratique.