Bonjour,
Le but de mon programme est de générer une image composée de disques de différentes tailles, placés de façon aléatoire et de façon à remplir le plus possible de surface avec ces disques.
La contrainte majeure est que les disques ne doivent pas se chevaucher.
Pour avoir un ordre d'idée, l'image est d'une taille comprise entre 640*400 et 1280*1024.
Et le nombre de disques se situe entre 2000 et 10000. (la rayon des disques varie entre 5 et 35 pixels).
Voila comment je m'y prends actuellement:
J'ai une structure qui permet d'enregistrer les disques deja présents.
J'ai implanté un algo naïf qui fait ceci:
1- je génére un disque ( c'est à dire un centre et un rayon).
2- je teste si ce disque ne chevauche pas les disques déja présents.
a- si le disque ne chevauche rien, je l'ajoute à ma liste et reviens en 1
b- si le disque chevauche un autre disque je reviens en 1.
Le problème est qu'après un certain nombre de disques déja présents, il devient difficile de générer un disque qui ne chevauche rien. (au bout de quelques centaines de disques générés la proportion de disques acceptés devient de plus en plus faible).
Le problème vient peut-etre de l'étape 1. Pour générer les coordonnées du centre je fais ça de façon complétement aléatoire, j'autorise toutes les coordonnées de ma surface.
J'avais pensé découper la surface totale de travail en plus petites zones pour pouvoir générer de façon plus "dynamique" les coordonées des disques, mais je ne sais pas trop d'une part si ça va être efficace, et d'autre part comment m'y prendre. (par dynamique, je veux dire en tenant compte des disques deja existants dés la phase de génération des coordonnées du centre).
Si vous avez des idées sur la façon de résoudre ce problème donnez les moi, et si vous pensez à une toute autre méthode pour parvenir au même résultat, je suis preneur aussi.
Merci d'avance pour votre aide.
PS: je fais ça en java.
