Approche 1

Une assez belle classe d'algorithmes pour la pose de graphiques sont des algorithmes à base de simulation. Dans ces algorithmes, vous modélisez votre graphique comme s'il s'agissait d'un objet physique avec des propriétés physiques.

Dans ce cas, imaginez que les nœuds du graphique sont des balles qui se repoussent, tandis que les bords sont des ressorts ou des caoutchoucs qui maintiennent le graphique ensemble. La force repoussante est plus forte plus les nœuds sont plus proches les uns des autres par exemple. carré inverse de leur distance et la force de tension de chaque ressort est proportionnelle à sa longueur. La force repoussante entraînera les nœuds d'obtenir autant que possible des autres nœuds et le graphique se débrouillera. Bien sûr, vous devrez expérimenter des coefficients un peu pour obtenir les meilleurs résultats (mais je vous garantis - c'est beaucoup de plaisir).

Les principaux avantages de cette approche sont les suivants:

1. Facile à coder - Des boucles imbriquées en calculant la force entre chaque paire de nœuds et la mise à jour de la position de nœud
2. fonctionne pour toutes sortes de graphiques de planar ou de nonplanar
3. beaucoup de plaisir à expérimenter
4. Si vous le faites interactif, par exemple. Autoriser l'utilisateur à déplacer des nœuds avec une souris - il attire les gens et tout le monde veut "jouer avec le graphique"

   Les inconvénients de cette approche sont les suivants:

   1. Il peut rester coincé dans un minimum d'énergie local (secouant ou aide manuellement)
   2. Ce n'est pas extrêmement rapide (mais peut faire une belle animation)

      une méthode similaire peut être utilisé pour la mise en page / des noeuds dénués.

      code d'échantillon xxx

      Vous pouvez voir comment ce code fonctionne ici . Actualisez la page pour obtenir différents graphiques. Bien sûr, parfois, il ne trouve pas le minimum global et il y a plus de bords croisés qu'il n'est possible, donc si les résultats ne vous satisfont pas, vous pouvez ajouter des secousses aléatoires.

      approche 2

      Ce problème est similaire au problème de routage dans la conception des PCB. Si vous n'êtes pas satisfait de la solution simple et facile fournie par APPROCHE 1, vous pouvez améliorer la solution en utilisant des méthodes d'autoroute. Par exemple. Vous pouvez mettre vos nœuds sur une grille puis utiliser un * algorithme * pour trouver les chemins les plus courts qui les connectent.

      1. Utilisez l'approche 1 pour trouver une solution initiale sous-optimale (facultatif).
      2. supprimer tous les bords. Placez les nœuds sur une grille (arrondir leurs coordonnées). La grille doit avoir suffisamment de résolution pour que les deux nœuds ne se chevauchent pas.
      3. Trier les bords de longueur approximative ascendante (utilisez une métrique Euclidean ou Manhattan).
      4. Pour chaque bord, utilisez un * algorithme pour trouver la voie la plus courte pour connecter les nœuds. En tant que fonction de coût, utilisez non seulement la distance entre le nœud source, mais aussi ajouter suffisamment de pénalité pour marcher sur les points de grille déjà pris par n'importe quel bord de bord précédemment.
      5. Marquez les points de grille sur le chemin trouvé à l'étape précédente comme "prise", de sorte que tous les bords suivants favoriseront les chemins ne pas marcher / intersecteront avec ce chemin.

         L'algorithme ci-dessus est une heuristique gourmande et il ne garantit malheureusement pas la solution optimale, car le résultat dépend de l'ordre de routage des bords. Vous pouvez améliorer encore la solution en retirant un bord aléatoire qui traverse un autre bord et le redirige.

         Étape 1. est facultatif pour rendre la disposition de graphique plus régulière et rendre la distance de connexion moyenne faible, mais il ne doit pas affecter le nombre d'intersections (si la grille a suffisamment de résolution). < / h1>

Je pense que l'algorithme basé sur la simulation serait le choix Bbest, cependant, étant donné que votre objectif est de minimiser les arcs qui se chevauchent et de ne pas optimiser la distribution des nœuds, vous devez appliquer une force repoussante entre les arcs (pas entre les nœuds) et utiliser le nœuds comme ressorts.

Itération:

1. pour chaque arc dans le graphique calculer son point central (moyennant la moyenne du point de départ avec le point de fin)
2. pour chaque couple d'arcs appliquent une répulsion entre leurs centres (les deux extrêmes de l'arc bougent en conséquence)
3. Pour chaque nœud du graphique calculer sa nouvelle position en tant que moyenne des arcs connectés et mettez à jour le point final correspondant de l'arc

   Vous pouvez également ajouter une phase de contraction avec les nœuds attirés au milieu du graphique (moyenne des coordonnées de tous les nœuds).

   Arrêtez-vous quand un seuil de stabilité est atteint.