Math
Voronoi und Delaunay
Nächste-Nachbar-Zellen, die sich umformen, während man ihre Punkte zieht, die dazu duale Delaunay-Triangulation mit ihren leeren Kreisen, Scheiben, die in die Zellen hineinwachsen, und Lloyds Relaxation, die sie zu Sechsecken macht.
Was passiert
Vierzig Punkte auf einem Quadrat, und jeder Ort des Quadrats gehört zum nächsten Punkt: diese eine Regel zeichnet die Grenzen. Jede Zelle ist im Farbton ihres Punktes gemalt und mit Licht umrandet; zieh einen Punkt, und jede Zelle formt sich im selben Bild um, denn eine Zelle ist nichts als das Quadrat, beschnitten von den Mittelsenkrechten zwischen ihrem Punkt und allen anderen. Das Duale: zwei Zellen mit gemeinsamer Grenze geben eine Kante zwischen ihren Punkten, und wo drei Zellen in einer Ecke zusammentreffen, bilden die drei Punkte ein Dreieck - das ist die Delaunay-Triangulation, und mit h Punkten auf der äußeren Hülle hat sie genau 3N − 3 − h Kanten und 2N − 2 − h Dreiecke (Eulers Zählung, live geprüft). Jedes ihrer Dreiecke hat einen leeren Umkreis: schalte die Kreise ein und sieh, dass kein Punkt in einen fällt und jede Zellecke von ihren drei Punkten gleich weit entfernt ist. Die Wachstumsszene lässt um jeden Punkt eine Scheibe mit gleicher Geschwindigkeit wachsen: die Scheiben treffen sich genau auf den Zellgrenzen, weil eine Grenze dort liegt, wo zwei Punkte gleich nah sind, und das Quadrat ist an der fernsten Zellecke voll. Lloyds Relaxation verschiebt jeden Punkt in den Schwerpunkt seiner Zelle, Schritt für Schritt: die Energie Σ∫|x − Punkt|² über die Zellen fällt monoton, die Flächen gleichen sich an und die Zellen werden sechseckig - aus 9 Sechsecken werden 15 von 40 in dreißig Schritten.
Gleichungen des Moduls
Gleichungen
Zelle: V_i = {x : |x − s_i| ≤ |x − s_j| für alle j} = das Quadrat, geschnitten durch die Halbebenen (s_j − s_i)·x ≤ (|s_j|² − |s_i|²)/2, eine pro anderem Zentrum, in Indexreihenfolge (Sutherland–Hodgman); jede Kante merkt sich das Zentrum, das sie geschnitten hat
dual: eine Delaunay-Kante s_i s_j existiert, wenn V_i und V_j eine Kante gemeinsam haben; ein Dreieck s_i s_j s_k, wenn die drei Zellen in einer Ecke zusammentreffen - die Ecke ist der Umkreismittelpunkt, und kein Zentrum liegt im Umkreis; entnommen aus dem Diagramm, das auf eine 1000-mal so breite Box zugeschnitten ist, da zwei Zentren der konvexen Hülle sich erst außerhalb des Quadrats treffen können (98 der 105 Kanten erscheinen darin)
Euler: h Zentren auf der konvexen Hülle (Andrews Monotone-Chain-Verfahren): E = 3N − 3 − h, T = 2N − 2 − h; N = 40, Seed 5: h = 12, E = 105, T = 66; 219 Zellecken, 5.475 pro Zelle; die Zellen pflastern das Quadrat: Σ Flächen = 4
Wachstum: Kreisscheibe mit Radius r um jedes Zentrum, auf seine Zelle beschnitten (ein regelmäßiges 32-Eck); überdeckter Anteil 0.260 / 0.694 bei r = 0.1 / 0.2; voll bei r = max über alle Zellen der am weitesten entfernten Ecke = 0.5126; die Kreisscheiben treffen sich an den Grenzen, weil eine Grenze dort verläuft, wo zwei Zentren gleich weit entfernt sind
Lloyd: s_i ← centroid(V_i) = (1/6A) Σ (x_k + x_{k+1})(x_k y_{k+1} − x_{k+1} y_k), dann neu aufbauen; Energie F = Σ_i ∫_{V_i} |x − s_i|² dx (ein Fächer aus Dreiecken ab s_i, ∫ = A(a² + b² + a·b)/6 je Dreieck) fällt monoton: 0.1355 → 0.0954 nach einem Schritt → 0.0681 nach dreißig; Streuung der Flächeninhalte 0.0596 → 0.0149; Sechsecke 9 → 15 von 40
