generation aleatoire de polygones

Version imprimable

22/07/2005, 12h42
cedriku

generation aleatoire de polygones

Bonjour a tous.

Voila, je veux faire un programme qui recoit en entree 4 parametres :
- nombre de cases horizontales d'une grille
- nombre de cases verticales
- nombres de polygones
- densité en pourcentage de la place prise par les polygones sur l'ensemble de la grille

Ensuite avec ces parametres, je veux afficher aleatoirement sur la grille mes polygones. J'utilise tcl/tk pout l'affichage sur linux mandriva.

Seulement je n'arrive pas à trouver un algorithme efficace pour cette affichage aleatoire.
(je precise quil ne faut pas non plus que les polygones se chevauchent)

Voici ce que j'ai fais :
- creation d"un tableau t{nbr_ligne * nbr_colonne] dont les cases sont des coordonnees
- choix d'un indice aleatoirement
- on colorie donc la case t[indice]
- on supprime la case t[indice] du tableau t afin quelle ne soit plus choisie.
- je construit mon polygone autour de cette case

mais ca ne marche pas tres bien car les polygones se "touchent" et des fois j'ai des plantages, je pense dans le cas ou il arrive dans un coin de la grille et il ne trouve pas de case alentour libre où colorier...

merci de votre aide.
22/07/2005, 22h49
cedriku

snif personne pour m'aider a resoudre mon probleme...
24/07/2005, 01h19
ceugniet

Bon, pleure pas ! Tu n'as pas beaucoup de réponses, c'est peut-être parce que tu n'es pas assez précis ! De quels polygones s'agit-il ? Des triangles, des quadrilatères, des octogones ? Réguliers ? Quelconques ?

Je suis tellement dans le vague que je me suis abstenu jusqu'à maintenant. Tu dois préciser un peu les choses ; peut-être alors que quelqu'un aura une idée, pas forcément moi d'ailleurs...
24/07/2005, 20h56
cedriku

ui desole je precise:

les polygones se construisent en coloriant les cases de la grille (donc deja un triangle c pas possible) et doivent avoir n'importe quelle forme, les polygones n'ont pas tous non plus forcement la meme taille. Enfin tout est entierement aleatoire, il fo juste colorier les cases de la grille pour former les polygones !
24/07/2005, 23h20
ceugniet

Citation:

Envoyé par cedriku

ui desole je precise:

les polygones se construisent en coloriant les cases de la grille (donc deja un triangle c pas possible) et doivent avoir n'importe quelle forme, les polygones n'ont pas tous non plus forcement la meme taille. Enfin tout est entierement aleatoire, il fo juste colorier les cases de la grille pour former les polygones !

Pour éviter que les polygones ne se touchent, ne peux-tu pas éviter de colorier une case lorsque tu vois que cela va faire se toucher deux polygones ? Apparamment, tes polygones ne suivent aucune règle ! Je ne vois pas ce qui pourrait les empêcher de se toucher à part ce que je viens de dire...
25/07/2005, 10h01
diogene

ceugniet a raison : Comment veux-tu obtenir une réponse à ta question sans fournir plus de détails.

Citation:

- je construit mon polygone autour de cette case

Comment , selon quels critères ce polygone sera t-il construit ?

Citation:

Enfin tout est entierement aleatoire

mais obéit à des règles déterministes. Lesquelles ?
Si tu ne précises rien, tu auras forcément des réponses aléatoires à ta question :D
25/07/2005, 10h15
cedriku

lol ui mai quan je dis aleatoire, vraiment aleatoire justement....
ils ne respectent pas de forme precises, si ce n'est qu'un coté d'un polygone ne peut couper un carreau de la grille en 2 ( c'est pour ca qu'il ne peut pas y avoir de triangle) donc leur construction se fait par coloriage des carreau de la grille.
Le fait de choisir aleatoirement un carreau de la grille et de colorier autour pour construire mon polygone, c'est lalgorithme que j'ai essayé mais si vous avez d'autre idee...
Pour eviter que 2 polygone se touche, le probleme c'est pa de dire ne pose pas la car tu vas toucher un autre polygone, c'est de faire en sorte que lorsqu'il vas choisir aleatoirement un carreau de la grille a colorier il ne puisse pas choisir un carreau qui serait susceptible de faire toucher un autre polygone !
j'espere que j'ai été assez precis !
25/07/2005, 10h25
diogene

Citation:

Le fait de choisir aleatoirement un carreau de la grille et de colorier autour pour construire mon polygone,

On comprend bien que tu as choisi au hasard un carreau de la grille, la "graine" de ton polygone. Mais que signifie en pratique colorier autour ? Pour chaque voisin de ta graine , tu choisis au hasard de le colorier ou non ? et tu itères le processus pour les points coloriés ? comment le processus s'arrête t-il ? Tant que tu n'expliqueras pas un peu ce point de la construction de tes polygones, on ne peut pas répondre :( .
25/07/2005, 11h12
cedriku

lol justement c'est ce que j'aimerais savoir !!! Comment faire apres avoir choisi une graine ? Est ce qu'il y a une methode plus rapide qu'une autre pour construire le polygone a partir de la graine ?
Moi ce que j'ai fais :

- Je choisis aleatoirement une des cases possibles autour de ma graine
- je colorie la case choisie
- et je fais pareil pour cette case, je regarde autour les possibilité qu'il y a pour en placer une autre puis jen choisi une aleatoirement et je colorie et ....

seulement des fois je me retrouve avec des segmentation fault car si par exemple mon repere commence a la case (0,0) et que la graine de mon polygone est choisie en (1,0) ensuite s'il choisit (1,1) puis il choisi (0,1) et enfin il choisi (0,0) et la il peut plus choisir car il n'y a aucune case de libre autour de (0,0)... donc cet algorithme ne marche pas dans tous les cas !!!

donc ma question est : est ce qu'il existe une autre facon de proceder ?
25/07/2005, 12h13
diogene

Citation:

- Je choisis aleatoirement une des cases possibles autour de ma graine
- je colorie la case choisie
- et je fais pareil pour cette case, je regarde autour les possibilité qu'il y a pour en placer une autre puis jen choisi une aleatoirement et je colorie et ....

Voila des précisions utiles. Il manque encore une information : Comment décide t-on de s'arrêter ? Sinon on va remplir entierement la grille. Est-ce que, par exemple, on a tiré aléatoirement également la surface du polygone (donc le nombre N de cases à colorier) ?Si on part de cette hypothèse, il faut s'assurer qu'un bloc de N cases soit disponible autour de la graine initiale.

Citation:

et enfin il choisi (0,0) et la il peut plus choisir car il n'y a aucune case de libre autour de (0,0)... donc cet algorithme ne marche pas dans tous les cas !!!

Ce n'est pas trop grave, il suffit de repartir de la case précédente (0,1) et si ce n'est pas possible non plus, de la case d'avant (1,1),...
25/07/2005, 18h56
cedriku

ben au depart on a la taille de la grille en parametres, et la densité en % que les polygones doivent prendre sur la surface de la grille donc on peu savoir le nombre de cases totales que prendra la surface de tous les polygones reunis ! on peut ensuite decider que chaque polygone ait la meme surface ou non ca c'est pas important...

et ui javai pensé a cette solution de revenir sur la case davan.. mai la complexité serai grande, jai trouvé une autre technique je crois mais je l'ai pa encore implementé:

- Je choisi la graine de mon premier polygone
- jenregistre les case autour disponibles dans une liste chainee (chaque polygone a sa liste chainee)
- je choisi aleatoiremen une des cases qui est dan la liste chainee associé a mon polygone et je la colorie, je suprime la case que je vien de choisir de la liste et je regarde les cases alentour que je rajoute a ma liste chainee
- je procede comme ca jusqua la fin de mon polygone, ainsi jaurai toujour une case possible autour de mon polygone
- la fin de mon polygone est atteinte lorsque: densité * surface_grille / nombre_polygones est atteint
- et je fai pareil pour tou mes polygone

reste plu qua implementer en C... je sens que je vai mamuser !!