Math
Voronoï et Delaunay
Des cellules du plus proche voisin qui se reforment quand on déplace leurs points, la triangulation de Delaunay qui leur est duale avec ses cercles vides, des disques qui grandissent jusqu'à remplir les cellules, et la relaxation de Lloyd qui en fait des hexagones.
Ce qui se passe
Quarante points sur un carré, et chaque lieu du carré appartient au point le plus proche : cette seule règle trace les frontières. Chaque cellule est peinte de la teinte de son point et cernée de lumière ; déplace un point et chaque cellule se reforme dans la même image, car une cellule n'est rien d'autre que le carré découpé par les médiatrices entre son point et tous les autres. Le dual : deux cellules qui partagent une frontière donnent une arête entre leurs points, et là où trois cellules se rejoignent en un coin, les trois points forment un triangle - c'est la triangulation de Delaunay, et avec h points sur l'enveloppe extérieure elle a exactement 3N − 3 − h arêtes et 2N − 2 − h triangles (le compte d'Euler, vérifié en direct). Chacun de ses triangles a un cercle circonscrit vide : coche les cercles et vois qu'aucun point ne tombe dans aucun d'eux, et que chaque coin de cellule est équidistant de ses trois points. La scène de croissance fait grandir un disque autour de chaque point à vitesse égale : les disques se rencontrent exactement sur les frontières, car une frontière est là où deux points sont aussi proches l'un que l'autre, et le carré est plein au coin de cellule le plus lointain. La relaxation de Lloyd déplace chaque point vers le centre de masse de sa cellule, pas à pas : l'énergie Σ∫|x − point|² sur les cellules décroît de façon monotone, les aires s'égalisent et les cellules deviennent hexagonales - 9 hexagones deviennent 15 sur 40 en trente pas.
Équations du module
Équations
cellule : V_i = {x : |x − s_i| ≤ |x − s_j| pour tout j} = le carré découpé par les demi-plans (s_j − s_i)·x ≤ (|s_j|² − |s_i|²)/2, un par autre site, dans l'ordre des indices (Sutherland–Hodgman) ; chaque arête mémorise le site qui l'a coupée
dual : une arête de Delaunay s_i s_j existe lorsque V_i et V_j partagent une arête ; un triangle s_i s_j s_k lorsque les trois cellules se rencontrent en un coin - le coin est le centre du cercle circonscrit et aucun site ne se trouve à l'intérieur du cercle circonscrit ; obtenu à partir du diagramme découpé dans une boîte 1000 fois plus large, car deux sites de l'enveloppe convexe peuvent ne se rencontrer qu'à l'extérieur du carré (98 des 105 arêtes apparaissent à l'intérieur)
Euler : h sites sur l'enveloppe convexe (chaîne monotone d'Andrew) : E = 3N − 3 − h, T = 2N − 2 − h ; N = 40, graine 5 : h = 12, E = 105, T = 66 ; 219 coins de cellules, 5.475 par cellule ; les cellules pavent le carré : Σ aires = 4
croissance : disque de rayon r autour de chaque site, restreint à sa cellule (un 32-gone régulier) ; fraction couverte 0.260 / 0.694 pour r = 0.1 / 0.2 ; couverture totale pour r = max sur les cellules du sommet le plus éloigné = 0.5126 ; les disques se touchent sur les frontières car une frontière est l'endroit où deux sites sont à égale distance
Lloyd : s_i ← centroid(V_i) = (1/6A) Σ (x_k + x_{k+1})(x_k y_{k+1} − x_{k+1} y_k), puis reconstruction ; énergie F = Σ_i ∫_{V_i} |x − s_i|² dx (un éventail de triangles issus de s_i, ∫ = A(a² + b² + a·b)/6 par triangle) décroît de façon monotone : 0.1355 → 0.0954 après une étape → 0.0681 après trente ; dispersion des aires 0.0596 → 0.0149 ; hexagones 9 → 15 sur 40
