Math
Woronoj i Delaunay
Komórki najbliższego sąsiada, które przebudowują się, gdy przeciągasz ich punkty, dualna do nich triangulacja Delaunaya z pustymi okręgami, dyski rosnące w komórki i relaksacja Lloyda, która zamienia je w sześciokąty.
Co się dzieje
Czterdzieści punktów na kwadracie, a każde miejsce kwadratu należy do najbliższego z nich: ta jedna reguła rysuje granice. Każda komórka pomalowana jest odcieniem swojego punktu i obwiedziona światłem; przeciągnij punkt, a każda komórka przebuduje się w tej samej klatce, bo komórka to nic innego jak kwadrat przycięty symetralnymi między jej punktem a wszystkimi pozostałymi. Dualność: dwie komórki ze wspólną granicą dają krawędź między ich punktami, a gdzie trzy komórki schodzą się w narożniku, trzy punkty tworzą trójkąt - to triangulacja Delaunaya, a przy h punktach na otoczce zewnętrznej ma ona dokładnie 3N − 3 − h krawędzi i 2N − 2 − h trójkątów (rachunek Eulera, sprawdzany na żywo). Każdy jej trójkąt ma pusty okrąg opisany: zaznacz okręgi i zobacz, że żaden punkt nie wpada do żadnego z nich, a każdy narożnik komórki jest równo oddalony od swoich trzech punktów. Scena wzrostu powiększa dysk wokół każdego punktu z równą prędkością: dyski spotykają się dokładnie na granicach komórek, bo granica jest tam, gdzie dwa punkty są jednakowo blisko, a kwadrat wypełnia się przy najdalszym narożniku komórki. Relaksacja Lloyda przesuwa każdy punkt do środka masy jego komórki, krok po kroku: energia Σ∫|x − punkt|² po komórkach maleje monotonicznie, pola się wyrównują, a komórki stają się sześciokątne - 9 sześciokątów zmienia się w 15 z 40 w trzydziestu krokach.
Równania modułu
Równania
komórka: V_i = {x : |x − s_i| ≤ |x − s_j| dla wszystkich j} = kwadrat przecięty półpłaszczyznami (s_j − s_i)·x ≤ (|s_j|² − |s_i|²)/2, po jednej na każdy inny ośrodek, w kolejności indeksów (Sutherland–Hodgman); każda krawędź pamięta ośrodek, który ją odciął
dualność: krawędź Delaunaya s_i s_j istnieje, gdy V_i i V_j mają wspólną krawędź; trójkąt s_i s_j s_k powstaje, gdy trzy komórki spotykają się w jednym rogu - ten róg jest środkiem okręgu opisanego i żaden ośrodek nie leży wewnątrz okręgu opisanego; wzięte z diagramu przyciętego do pudełka 1000 razy szerszego, ponieważ dwa ośrodki otoczki wypukłej mogą się spotkać dopiero poza kwadratem (98 ze 105 krawędzi widać wewnątrz niego)
Euler: h ośrodków na otoczce wypukłej (łańcuch monotoniczny Andrewa): E = 3N − 3 − h, T = 2N − 2 − h; N = 40, ziarno 5: h = 12, E = 105, T = 66; 219 rogów komórek, 5.475 na komórkę; komórki pokrywają kwadrat: Σ pól = 4
wzrost: koło o promieniu r wokół każdego ośrodka, przycięte do jego komórki (foremny 32-kąt); pokryty ułamek 0.260 / 0.694 dla r = 0.1 / 0.2; pełne pokrycie dla r = max po komórkach odległości do najdalszego wierzchołka = 0.5126; koła spotykają się na granicach, ponieważ granica jest tam, gdzie dwa ośrodki leżą jednakowo blisko
Lloyd: s_i ← centroid(V_i) = (1/6A) Σ (x_k + x_{k+1})(x_k y_{k+1} − x_{k+1} y_k), następnie przebudowa diagramu; energia F = Σ_i ∫_{V_i} |x − s_i|² dx (wachlarz trójkątów wychodzących z s_i, ∫ = A(a² + b² + a·b)/6 na trójkąt) maleje monotonicznie: 0.1355 → 0.0954 po jednym kroku → 0.0681 po trzydziestu; rozrzut pól 0.0596 → 0.0149; sześciokąty 9 → 15 z 40
