27-08-2018, 07:23 PM
Salut,
ça "fait carré" parce que tu as dû positionner tes points centraux selon une grille... carrée
Pour générer un truc comme ça, perso, je procèderai ainsi:
Initialisation:
- Répartition de N points au pif dans la carte (mes "points d'origine", aka les centre des cellules de Voronoi)
Itérations:
- Construction du diagramme de Voronoi (c'est le plus compliqué je dirai, mais des libs doivent exister)
- Calcul de la surface de chaque cellule
- Comptage des cellules "trop grandes" et éventuellement, des cellules "trop petites", calcul du max de ces deux nombres
- Création de deux listes de longueur égale à ce max: la liste des cellules (les coordonnées de leur centre) les plus grandes (qui contiendra donc la liste des cellules "trop grandes") et la liste des cellules les plus petits. Si les listes se chevauchent, repartir de zéro (les points tirés au pif ont vraiment chié)
- Déplacer tous les points de la liste des "petites cellules" pour les mettre à proximité d'une grande cellule (pour chaque point de la liste des petites cellules, prendre une grande cellule au pif, et déplacer ce point à une distance R du centre de la grande cellule; on peut approximer R par racine_carrée[surface de la grande cellule]/Pi)
- Réitérer jusqu'à avoir des listes vides
C'est extensible à d'autres conditions que la taille mini/maxi des cellules.
Je ne sais pas quelle est la vitesse de convergence du truc (peut-être qu'on peut se contenter d'ailleurs de de placer des points au pif dans la carte, calculer que le diagramme soit "valide" pour les conditions qu'on fixe, et si non, retirer tous les points au pif... c'est plus simple, mais moins convergent je dirai)
Pour connaitre les cellules voisines, c'est dans la construction du Voronoï, donc, inutile de se préoccuper de cela pendant l'algorithme de répartition des centres des cellules.
ça "fait carré" parce que tu as dû positionner tes points centraux selon une grille... carrée
Pour générer un truc comme ça, perso, je procèderai ainsi:
Initialisation:
- Répartition de N points au pif dans la carte (mes "points d'origine", aka les centre des cellules de Voronoi)
Itérations:
- Construction du diagramme de Voronoi (c'est le plus compliqué je dirai, mais des libs doivent exister)
- Calcul de la surface de chaque cellule
- Comptage des cellules "trop grandes" et éventuellement, des cellules "trop petites", calcul du max de ces deux nombres
- Création de deux listes de longueur égale à ce max: la liste des cellules (les coordonnées de leur centre) les plus grandes (qui contiendra donc la liste des cellules "trop grandes") et la liste des cellules les plus petits. Si les listes se chevauchent, repartir de zéro (les points tirés au pif ont vraiment chié)
- Déplacer tous les points de la liste des "petites cellules" pour les mettre à proximité d'une grande cellule (pour chaque point de la liste des petites cellules, prendre une grande cellule au pif, et déplacer ce point à une distance R du centre de la grande cellule; on peut approximer R par racine_carrée[surface de la grande cellule]/Pi)
- Réitérer jusqu'à avoir des listes vides
C'est extensible à d'autres conditions que la taille mini/maxi des cellules.
Je ne sais pas quelle est la vitesse de convergence du truc (peut-être qu'on peut se contenter d'ailleurs de de placer des points au pif dans la carte, calculer que le diagramme soit "valide" pour les conditions qu'on fixe, et si non, retirer tous les points au pif... c'est plus simple, mais moins convergent je dirai)
Pour connaitre les cellules voisines, c'est dans la construction du Voronoï, donc, inutile de se préoccuper de cela pendant l'algorithme de répartition des centres des cellules.