Discussion :

[Kikohs]

Bonjour,
Je suis à la recherche d'idées pour créer une représentation d'un graphe en 3D.
Jusqu'à là rien de d'extraordinaire, le problème est le suivant :

- Je n'ai que la distance entre un noeud et ses voisins.
Exemple : A->B = 2, A->C = 3; B->A = 2, B->D = 4
Je dois donc construire des coordonnées 3D sachant que je n'ai aucune coordonnées pour les points.
Tous les points ne sont pas reliés ensemble.

- 2ème contrainte, il faut que visuellement, les distances les plus courtes soient vraiment plus courte. C'est à dire qu'il ne doit pas y avoir un 'edge', vertex qui soit de 5, un autre de 3 et que le 5 soit plus près du noeud que celui de 3.

Je code en python au cas où, et pour la visualisation, je dois coder en OpenGl.
J'espère avoir été clair, merci pour toutes vos contributions !

[vic]

Hum ça n'a pas l'air simple. Ça ressemble un peu aux calculs de conformation de protéines qui sont loin d'être évidents. Il y a plusieurs problèmes :

1. Tout graphe ne sera pas forcément représentable. Tu peux avoir des contraintes qu'il est impossible de respecter en 3D.
2. La représentation n'est pas nécessairement unique.

Tu peux essayer de donner à chaque liaison nœud-nœud une force d'attraction du type interaction forte en physique, avec répulsion si les nœuds sont trop proches, attraction s'ils sont trop éloignés, et point d'équilibre à la distance voulue. Place les nœuds dans des positions quelconques puis fais évoluer ce système avec un amortissement jusqu'à obtenir un état stable. Tu peux ensuite calculer l'énergie totale du système (écarts par rapport à l'équilibre de toutes les liaisons), puis perturber le système (déplacement aléatoire d'un ou plusieurs nœuds) et tenter de trouver l'état qui a le moins d'énergie, zéro étant l'idéal.