Math
Voronoi e Delaunay
Celle del vicino più prossimo che si rifanno mentre trascini i loro punti, la triangolazione di Delaunay a esse duale con i suoi cerchi vuoti, dischi che crescono fino a riempire le celle, e il rilassamento di Lloyd che le rende esagoni.
Cosa succede
Quaranta punti su un quadrato, e ogni luogo del quadrato appartiene al punto più vicino: quella sola regola disegna i confini. Ogni cella è dipinta nella tinta del suo punto e orlata di luce; trascina un punto e ogni cella si rifà nello stesso fotogramma, perché una cella non è altro che il quadrato tagliato dagli assi fra il suo punto e tutti gli altri. Il duale: due celle con un confine in comune danno uno spigolo fra i loro punti, e dove tre celle si incontrano in un angolo i tre punti formano un triangolo - questa è la triangolazione di Delaunay, e con h punti sull'inviluppo esterno ha esattamente 3N − 3 − h spigoli e 2N − 2 − h triangoli (il conto di Eulero, verificato dal vivo). Ogni suo triangolo ha un circocerchio vuoto: spunta i cerchi e vedrai che nessun punto cade in alcuno di essi, e che ogni angolo di cella è equidistante dai suoi tre punti. La scena di crescita fa crescere un disco attorno a ogni punto a velocità uguale: i dischi si incontrano esattamente sui confini, perché un confine è dove due punti sono ugualmente vicini, e il quadrato si riempie all'angolo di cella più lontano. Il rilassamento di Lloyd sposta ogni punto nel baricentro della sua cella, passo dopo passo: l'energia Σ∫|x − punto|² sulle celle cala monotonamente, le aree si uniformano e le celle diventano esagonali - 9 esagoni diventano 15 su 40 in trenta passi.
Equazioni del modulo
Equazioni
cella: V_i = {x : |x − s_i| ≤ |x − s_j| per ogni j} = il quadrato tagliato dai semipiani (s_j − s_i)·x ≤ (|s_j|² − |s_i|²)/2, uno per ogni altro sito, in ordine d'indice (Sutherland–Hodgman); ogni spigolo ricorda il sito che l'ha tagliato
duale: uno spigolo di Delaunay s_i s_j esiste quando V_i e V_j condividono uno spigolo; un triangolo s_i s_j s_k quando le tre celle si incontrano in un vertice - il vertice è il circocentro e nessun sito cade dentro la circonferenza circoscritta; ricavato dal diagramma ritagliato in un riquadro 1000 volte più largo, perché due siti dell'involucro possono incontrarsi solo fuori dal quadrato (98 dei 105 spigoli compaiono al suo interno)
Eulero: h siti sull'involucro convesso (catena monotona di Andrew): E = 3N − 3 − h, T = 2N − 2 − h; N = 40, seme 5: h = 12, E = 105, T = 66; 219 vertici di cella, 5.475 per cella; le celle ricoprono il quadrato: Σ aree = 4
crescita: disco di raggio r centrato in ogni sito, ritagliato sulla sua cella (un 32-agono regolare); frazione coperta 0.260 / 0.694 per r = 0.1 / 0.2; copertura totale per r = max sulle celle del vertice più lontano = 0.5126; i dischi si incontrano sui bordi perché un bordo è dove due siti sono equidistanti
Lloyd: s_i ← centroid(V_i) = (1/6A) Σ (x_k + x_{k+1})(x_k y_{k+1} − x_{k+1} y_k), poi si ricostruisce; energia F = Σ_i ∫_{V_i} |x − s_i|² dx (un ventaglio di triangoli da s_i, ∫ = A(a² + b² + a·b)/6 per triangolo) decresce in modo monotono: 0.1355 → 0.0954 dopo un passo → 0.0681 dopo trenta; dispersione delle aree 0.0596 → 0.0149; esagoni 9 → 15 su 40
