Force-based layout

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant la géométrie image illustrant l’informatique
Cet article est une ébauche concernant la géométrie et l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Les algorithmes de dessin basé sur les forces (Force-based ou Force-directed algorithms) permettent de positionner les nœuds d'un graphe pour faciliter sa visualisation en utilisant un système de force appliqués entre les nœuds et les arcs.

Méthode[modifier | modifier le code]

L'algorithme peut être décrit comme une analogie physique des composants du graphe :

  • Les nœuds sont représentés par des particules de même charge
  • Les arcs sont assimilables à des ressorts

À chaque passe, l'algorithme fait la somme des forces appliquées sur chacun des nœuds puis les déplace suivant des règles de physique classique jusqu'à trouver un état stable.

Avantages[modifier | modifier le code]

  • Interactivité: les nœuds peuvent être replacés à la volée pendant le calcul, être ajoutés ou supprimés.

Inconvénients[modifier | modifier le code]

  • Ce sont des algorithmes souvent coûteux en puissance de calcul.
  • Ces algorithmes souffrent pour la plupart de ne terminer que dans un état qui est un minimum local du problème d'optimisation à l'origine de la modélisation physique.

Voir aussi[modifier | modifier le code]