2. Modèle à ressorts (dessin en 2D)
Dans cet exercice on vous demande de compléter la classe
SpringDrawing_2, qui permet de calculer une représentation
d'un
graphe avec le paradigme connu sous le nom Force Directed Drawing.
L'idée à la base de cet approche est très
simple,
et illustrée par la figure ci-dessous.
On considère un modèle mécanique
constitué
de:
- un ensemble de n
particules (les sommets du graphe)
- un ensemble de e
ressorts (les aretes du graphe)
Les ressorts modélisent des forces exercées entre les
particules. Il y a bien sur une force attractive entre sommets
adjacents (exercée
par les ressort), mais aussi une force répulsive
entre tous les sommets (cela pour éviter que le
système
collapse en un seul point). L'algorithme dit "force directed"
consiste
juste à
- choisir n points aléatoirement dans le plan (ou
l'espace)
- repeter N fois les opérations suivantes:
- calculer, pour tout couple de sommets adjacents, le
déplacement du à la force attractive
- calculer, pour toute paire de sommets (toute paire de sommets!),
le
déplacement du la force répulsive
- mettre à jour la position des points, selon les
déplacements calculés précedemment.
Remarque
- la force attractive (et la repulsive) entre deux particules
dépend de leur distance.
- la direction du déplacement (correspondant à une
paire a, b) est donnée par le vecteur: b-a.
Question (pratique)
Il
ne vous reste qu'à compléter la méthode computeDrawing()
de la classe SpringDrawing_2.
Question (plus théorique)
Qu'est-ce que vous remarquez par rapport au dessin obtenu avec
cette méthode? Le dessin est-il planaire?
Peut-on reconnaitre la structure du graphe visualisé? et
pourquoi?
Sauriez-vous expliquer la "structure" des dessins qu'on obtient
(question difficile... au moins jusqu'à l'exercice 3)
