Discussion :

[bilaloch]

Bonjour à tous !

Je suis en train de développer un site internet censé afficher des blocs (dont on connait la taille) dynamiquement, chaque bloc pouvant avoir un lien avec d'autres blocs (liens schématisés par des flèches). Mon souci est simplement de savoir s'il existe un algorithme permettant d'optimiser l'espace entre les blocs afin qu'ils soient à une distance optimale entre eux (plutôt proches les uns des autres), tout en prenant compte de l'existence des flèches (donc deux blocs liés devraient être plus proches l'un de l'autre, en tout cas quand c'est possible). Le nombre de blocs varient, mais disons qu'il ne sera jamais supérieur à quelques dizaines.

Voici un exemple qui, j'espère, sera un minimum clair :


Donc en gros, il y aura toujours un bloc "central", et les autres viendront se greffer tout autour de lui, sachant qu'ils peuvent aussi se greffer à d'autres blocs voire ne pas se greffer nécessairement au bloc "central". La question qui se pose est la suivante : comment coder un algo qui permette de déterminer la position optimale des différents blocs, en tenant compte des relations des uns et des autres entre eux et sans trop s'éloigner non plus ? Des idées ?

Merci d'avance pour ceux qui se casseront la tête avec et pour moi !

Belle journée à tous.

[DonQuiche]

Bonjour, voilà un problème intéressant.

J'aurais procédé de la façon suivante :
* On souhaite obtenir un cercle laissant 20% du périmètre découvert. On procède par dichotomie en faisant varier le rayon du cercle.
* Pour chaque cercle donné on cherche à le remplir dans le sens des aiguilles d'une montre sans laisser aucun espace entre les objets.
* On utilise pour ça un algorithme "best fit" : le prochain élément est l'élément qui épouse au mieux le cercle.
* L'élément qui épouse au mieux le cercle est déterminé en calculant le rapport entre la surface du rectangle et celle du segment circulaire qu'il contient.
* Chaque rectangle est testé sur quatre axes (accolé sur chacun des quatre côtés du précédent rectangle), et la position idéale sur chaque axe est calculée grâce aux points d’intersection du cercle et du rectangle. Il faut aussi vérifier à chaque fois la non-intersection avec les autres rectangles.
* Une fois tous les éléments placés le long du périmètre on mesure la fraction du périmètre découverte.

Une fois déterminé le rayon idéal, on refait tourner l'algorithme best fit en introduisant cette fois après chaque élément un espace proportionnel à la longueur de l'arc couvert par le précédent rectangle. On peut éventuellement tester toutes les permutations pour les petits n, avec l'adéquation au cercle pour critère de sélection.

Complexité : O(ln(n) * n^3)