Math
Voronoi and Delaunay
Nearest-neighbour cells that reshape as you drag their sites, the Delaunay triangulation dual to them with its empty circles, discs that grow into the cells, and Lloyd's relaxation that turns them into hexagons.
What happens
Forty sites on a square, and every point of the square belongs to the nearest site: that rule alone draws the borders. Each cell is painted in its site's hue and rimmed in light; drag a site and every cell reshapes in the same frame, because a cell is nothing but the square cut down by the bisectors between its site and every other. The dual: two cells that share a border give an edge between their sites, and where three cells meet at a corner the three sites make a triangle - that is the Delaunay triangulation, and with h sites on the outer hull it has exactly 3N − 3 − h edges and 2N − 2 − h triangles (Euler's count, checked live). Every one of its triangles has an empty circumcircle: tick the circles and see that no site falls inside any of them, and that every cell corner is equidistant from its three sites. The growth scene grows a disc around every site at equal speed: the discs meet exactly on the cell borders, because a border is where two sites are equally near, and the square is full at the farthest cell corner. Lloyd's relaxation moves every site to its cell's centre of mass, step by step: the energy Σ∫|x − site|² over the cells falls monotonically, the areas even out and the cells go hexagonal - 9 hexagons become 15 of 40 in thirty steps.
Equations used in the module
Equations
cell: V_i = {x : |x − s_i| ≤ |x − s_j| for all j} = the square cut by the half-planes (s_j − s_i)·x ≤ (|s_j|² − |s_i|²)/2, one per other site, in index order (Sutherland–Hodgman); each edge remembers the site that cut it
dual: a Delaunay edge s_i s_j exists when V_i and V_j share an edge; a triangle s_i s_j s_k when the three cells meet at a corner - the corner is the circumcentre and no site lies inside the circumcircle; taken from the diagram clipped to a box 1000 times wider, since two hull sites may only meet outside the square (98 of the 105 edges show inside it)
Euler: h sites on the convex hull (Andrew's monotone chain): E = 3N − 3 − h, T = 2N − 2 − h; N = 40, seed 5: h = 12, E = 105, T = 66; 219 cell corners, 5.475 per cell; cells tile the square: Σ areas = 4
growth: disc of radius r about every site, clipped to its cell (a regular 32-gon); covered fraction 0.260 / 0.694 at r = 0.1 / 0.2; full at r = max over cells of the farthest corner = 0.5126; the discs meet on the borders because a border is where two sites are equally near
Lloyd: s_i ← centroid(V_i) = (1/6A) Σ (x_k + x_{k+1})(x_k y_{k+1} − x_{k+1} y_k), then rebuild; energy F = Σ_i ∫_{V_i} |x − s_i|² dx (a fan of triangles from s_i, ∫ = A(a² + b² + a·b)/6 per triangle) falls monotonically: 0.1355 → 0.0954 after one step → 0.0681 after thirty; spread of areas 0.0596 → 0.0149; hexagons 9 → 15 of 40
