J'ai implémenté mon algo de mon côté, pour le fun https://xenos.reinom.com/mdn/voronoi-con...ained.html
Résultat:
Avec paramétrage possible. Libre à toi de reprendre le code sans condition (même si être au moins cité, ça fait plaisir ).
PS: les cellules sont bien plus irrégulières qu'avec la méthode des barycentres, trop "hexagonale-convergente" à mon gout :/
Pour reprendre l'algo:
Initialisation:
- Répartition de N points au pif dans la carte (mes "points d'origine", aka les centre des cellules de Voronoi) => Ce sont les points rouges de la variable "cells"
Itérations:
- Construction du diagramme de Voronoi (c'est le plus compliqué je dirai, mais des libs doivent exister) => Finalement, pas compliqué: on prend chaque pixel, et on cherche le centre de cellule le plus proche. Pas efficace du tout, mais rapide quand même en JS
- Calcul de la surface de chaque cellule => il suffit de compter les pixels de la cellule
- Comptage des cellules "trop grandes" et éventuellement, des cellules "trop petites" => ce sont les tooBig/SmallCellsCount
- calcul du max de ces deux nombres => c'est le invalidCellsCount, qui permet d'avoir une correspondance simple 1-1 entre les cellules trop grandes à "scinder" et les trop petites à fusionner
- 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é) => tooBig/SmallCells
- 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) => le forEach dessous
- Réitérer jusqu'à avoir des listes vides => le if invalidCellsCount === 0 break
C'est extensible à d'autres conditions que la taille mini/maxi des cellules. => A vous de trouver lesquelles vous voulez
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) => Finalement, en 3-4 itérations, c'est réglé... mais cela doit dépendre des conditions fixées (nota: je n'ai pas implémenté de mécanisme bloquant les requêtes sans solution, par exemple un canvas de 100x100 avec 100 cellules d'au moins 101 pixel, ce sera impossible et l'algo ne s'arrêtera jamais)
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. => Je ne l'ai pas implémenté, mais c'est simple à faire: on prend chaque pixel, on regarde sa cellule de Voronoi associée, on prend chacun de ses voisins, et on a donc 4 couples de cellules de voronoi qui sont voisines. On conserve une liste unique de ces couples, en ignorant les couples A-A (la même cellule 2 fois dans le couple) et c'est réglé.
Résultat:
Avec paramétrage possible. Libre à toi de reprendre le code sans condition (même si être au moins cité, ça fait plaisir ).
PS: les cellules sont bien plus irrégulières qu'avec la méthode des barycentres, trop "hexagonale-convergente" à mon gout :/
Pour reprendre l'algo:
Initialisation:
- Répartition de N points au pif dans la carte (mes "points d'origine", aka les centre des cellules de Voronoi) => Ce sont les points rouges de la variable "cells"
Itérations:
- Construction du diagramme de Voronoi (c'est le plus compliqué je dirai, mais des libs doivent exister) => Finalement, pas compliqué: on prend chaque pixel, et on cherche le centre de cellule le plus proche. Pas efficace du tout, mais rapide quand même en JS
- Calcul de la surface de chaque cellule => il suffit de compter les pixels de la cellule
- Comptage des cellules "trop grandes" et éventuellement, des cellules "trop petites" => ce sont les tooBig/SmallCellsCount
- calcul du max de ces deux nombres => c'est le invalidCellsCount, qui permet d'avoir une correspondance simple 1-1 entre les cellules trop grandes à "scinder" et les trop petites à fusionner
- 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é) => tooBig/SmallCells
- 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) => le forEach dessous
- Réitérer jusqu'à avoir des listes vides => le if invalidCellsCount === 0 break
C'est extensible à d'autres conditions que la taille mini/maxi des cellules. => A vous de trouver lesquelles vous voulez
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) => Finalement, en 3-4 itérations, c'est réglé... mais cela doit dépendre des conditions fixées (nota: je n'ai pas implémenté de mécanisme bloquant les requêtes sans solution, par exemple un canvas de 100x100 avec 100 cellules d'au moins 101 pixel, ce sera impossible et l'algo ne s'arrêtera jamais)
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. => Je ne l'ai pas implémenté, mais c'est simple à faire: on prend chaque pixel, on regarde sa cellule de Voronoi associée, on prend chacun de ses voisins, et on a donc 4 couples de cellules de voronoi qui sont voisines. On conserve une liste unique de ces couples, en ignorant les couples A-A (la même cellule 2 fois dans le couple) et c'est réglé.