Math
Voronoi y Delaunay
Celdas del vecino más cercano que se rehacen mientras arrastras sus puntos, la triangulación de Delaunay dual a ellas con sus círculos vacíos, discos que crecen hasta llenar las celdas, y la relajación de Lloyd que las vuelve hexágonos.
Qué ocurre
Cuarenta puntos en un cuadrado, y cada lugar del cuadrado pertenece al punto más cercano: esa sola regla dibuja las fronteras. Cada celda se pinta con el tono de su punto y se orla de luz; arrastra un punto y cada celda se rehace en el mismo fotograma, porque una celda no es más que el cuadrado recortado por las mediatrices entre su punto y todos los demás. El dual: dos celdas que comparten frontera dan una arista entre sus puntos, y donde tres celdas se juntan en una esquina los tres puntos forman un triángulo - esa es la triangulación de Delaunay, y con h puntos en la envolvente exterior tiene exactamente 3N − 3 − h aristas y 2N − 2 − h triángulos (la cuenta de Euler, comprobada en vivo). Cada uno de sus triángulos tiene un circuncírculo vacío: marca los círculos y verás que ningún punto cae dentro de ninguno, y que cada esquina de celda equidista de sus tres puntos. La escena de crecimiento hace crecer un disco alrededor de cada punto a igual velocidad: los discos se encuentran exactamente en las fronteras, porque una frontera está donde dos puntos están igual de cerca, y el cuadrado se llena en la esquina de celda más lejana. La relajación de Lloyd mueve cada punto al centro de masas de su celda, paso a paso: la energía Σ∫|x − punto|² sobre las celdas cae monótonamente, las áreas se igualan y las celdas se vuelven hexagonales - 9 hexágonos se convierten en 15 de 40 en treinta pasos.
Ecuaciones del módulo
Ecuaciones
celda: V_i = {x : |x − s_i| ≤ |x − s_j| para todo j} = el cuadrado cortado por los semiplanos (s_j − s_i)·x ≤ (|s_j|² − |s_i|²)/2, uno por cada otro sitio, en orden de índice (Sutherland–Hodgman); cada arista recuerda el sitio que la cortó
dual: existe una arista de Delaunay s_i s_j cuando V_i y V_j comparten una arista; un triángulo s_i s_j s_k cuando las tres celdas se encuentran en una esquina - la esquina es el circuncentro y ningún sitio queda dentro de la circunferencia circunscrita; se toma del diagrama recortado a una caja 1000 veces más ancha, ya que dos sitios de la envolvente solo pueden encontrarse fuera del cuadrado (98 de las 105 aristas se ven dentro de él)
Euler: h sitios en la envolvente convexa (cadena monótona de Andrew): E = 3N − 3 − h, T = 2N − 2 − h; N = 40, semilla 5: h = 12, E = 105, T = 66; 219 esquinas de celda, 5.475 por celda; las celdas teselan el cuadrado: Σ áreas = 4
crecimiento: disco de radio r alrededor de cada sitio, recortado a su celda (un 32-gono regular); fracción cubierta 0.260 / 0.694 con r = 0.1 / 0.2; cobertura total cuando r = max sobre las celdas de la esquina más lejana = 0.5126; los discos se encuentran en los bordes porque un borde es donde dos sitios están igual de cerca
Lloyd: s_i ← centroid(V_i) = (1/6A) Σ (x_k + x_{k+1})(x_k y_{k+1} − x_{k+1} y_k), luego se reconstruye; energía F = Σ_i ∫_{V_i} |x − s_i|² dx (un abanico de triángulos desde s_i, ∫ = A(a² + b² + a·b)/6 por triángulo) decrece de forma monótona: 0.1355 → 0.0954 tras un paso → 0.0681 tras treinta; dispersión de las áreas 0.0596 → 0.0149; hexágonos 9 → 15 de 40
