distribue aléatoirement des rectangles de différentes tailles sur un plan de taille variable (en considérant un degré de densité)

Question

Je cherche un algorithme qui distribue aléatoirement un nombre de rectangles (qui sont définis par leur largeur et leur hauteur) à l'intérieur d'un conteneur rectangle. Ce dernier n'est pas défini par sa taille, mais plutôt par son format. Il doit y avoir une autre variable qui détermine la densité du résultat, ou en d'autres termes: la distance moyenne de deux rectangles. Tous les rectangles doivent être placés, ce qui est possible, car le conteneur n'est pas limité en taille. Et il ne doit pas y avoir de chevauchement de rectangles.

Le résultat final doit être la position déterminée pour chaque rectangle ainsi que la taille du plan utilisé lui-même.

Malheureusement, je ne pouvais pas trouver un algorithme qui fait cela, ou des parties de celui-ci jusqu'à présent. J'apprécierais n'importe quelles suggestions, commentaires ou références! Il s'avère que le principal problème est de garder trace d'une liste des "espaces libres", qui est mise à jour après chaque placement en conséquence.

Dans le cas réel, j'ai besoin de cela pour, les rectangles donnés ne sont pas complètement au hasard. Ils ont presque la même taille et tendent à être beaucoup plus larges que hauts: ce ne sont que des mots tirés d'un texte qui devrait être distribué sur un plan comme un «nuage».

Answer 1

est ici quelques réflexions sur la façon de concevoir un algorithme:

• Puisque les rectangles réels ont des tailles similaires, vous pouvez probablement les regrouper en lignes et empiler plusieurs lignes pour obtenir la mise en page finale
• Utilisez le Pour déterminer l'espace libre restant après le placement des rectangles, calculez l'aire de la boîte englobante de tous les rectangles et soustrayez la somme des zones rectangle individuelles. . Cela fonctionne puisque les rectangles ne se chevauchent pas. Le taux de totalFreeSpace à boundingBoxArea vous donne la densité désirée Si ce n'est pas le cas, un algorithme O(n^2) devrait aider à calculer la densité par description du problème (en supposant que le nombre total de rectangle n'est pas trop grand).
• Une fois que vous avez ce qui précède, vous pouvez modifier les choses pour améliorer la forme du nuage. Par exemple, trier chaque ligne pour avoir les plus grands rectangles au centre.

Answer 2

Je pense que vous recherchez quelque chose comme la visualisation graphique avec une mise en page forcée. Si vous pouvez modéliser une relation entre vos mots, alors la force est le paramètre dont vous avez besoin.