Si vous avez déja eu l'occasion de travailler avec des réseaux de données ( une liste d'objet et de liens entre ces objets ) vous avez du être confronté à la difficultée de les représenter graphiquement. Il existe plusieurs algorithmes plus ou moins adaptés mettant en oeuvre des modèles de forces ( électrique, magnétique, gravitationnelles,.. ) A ma connaissance, ces algorithmes n'ont pas été portés en PHP.

Le code que je vous propose ici permet de représenter des réseaux de données en utilisant une implémentation de l'algorithme de force / répulsion ( aussi appelé Spring forces ). Le rendus est effectué via la librairie GD2. Quelques images illustrent cette articles, elles ont toutes été générées par ce script. Le modèle d'attraction / répulsion est simple à construire, il consiste à calculer les vecteurs de forces appliqués à chaques noeuds provenant de chaques autre noeuds. Deux règles s'appliquent : Deux noeuds liés subiront une force d'attraction proportionelle à la distance qui les sépare. Deux noeuds appliqueront l'un par rapport à l'autre une force de répulsion inversement proportionelle à la distance qui les sépare.

Pour calculer ces vecteurs il est nécessaire de faire quelques calculs trigonométriques.

$Distance = sqrt(($X2-$X)*($X2-$X)+($Y2-$Y)*($Y2-$Y)); if ( $X2 < $X ) { $Sinus = abs($X-$X2) / $Distance; if ( $Y > $Y2 ) $Angle = 360 - asin($Sinus) * (180/3.1418); else $Angle = 180 + asin($Sinus) * (180/3.1418); } else { $Sinus = abs($Y2-$Y) / $Distance; if ( $Y > $Y2 ) $Angle = 90 - asin($Sinus) * (180/3.1418); else $Angle = 90 + asin($Sinus) * (180/3.1418); }

Les vecteurs sont caractérisés par un angle et une force. La force doit dépendre de la distance entre les objets. Pour environ 20 objets, les valeurs suivantes permettent d'obtenir des graphs de qualité : $RepFactor = 14; $RepAtt = 20; $AttFactor = 20; $AttAtt = 70; // Vecteur d'attraction $Factor = (log($AttAtt) - log($Distance)); $Force = $AttFactor * $Factor; // Vecteur de répulsion $Factor = (log($RepAtt/10) - log($Distance/10)); $Force = $RepFactor * $Factor;

Une fois tous les vecteurs calculés pour chaques noeuds, il reste à les appliquer. Les étapes calcul / déplacement doivent être répétées suffisamment de fois pour que l'équilibre des noeuds soit atteint. Dans certaines configuration cela est impossible.


Je vous invite à télécharger ce script pour essayer de jouer avec les différents paramètres ( principalement $RepulsionFactor, $RepulsionAtt, $AttractionFactor, $AttractionAtt ). Il convient des les adapter suivant le nombre de noeuds et de liaisons.

Pour télécharger ce script, cliquez ici.

Au début du script vous trouverez 3 méthodes pour générer des réseaux : "Every nodes connected to all nodes" génère un réseau ou tous les noeuds sont reliés à tous les noeuds, "All nodes connected to a single same node" génère un réseau ou tous les noeuds sont reliés à un noeud central, "All nodes with random connection to another node" probablement le plus intéressant car les connections sont aléatoires. Le nombre de noeuds est définis par la variable $MaxNodes. Vous pouvez exécuter ce script en utilisant PHP-CLI :


Le fichier final.jpg sera alors généré dans le même répertoire.

Commentaires  | Ajouter un commentaire

-

Rechercher sur internet  ?  | Rechercher!

Trackback

Utilisez le lien http://www.sunyday.net/trackback-Dessiner-un-reseau-de-donnees-en-PHP pour faire un trackback vers cette article depuis votre site web. Les trackbacks sont soumis à une approbation mutuelle et susceptibles d'être supprimés si jugés indésirables.