Voronoi · math.adamdub.xyz

VORONOI

mové el cursor · clic: sembrar · mantené: remolino

C colores · S sonido · D triangulación · T estela · F pantalla completa · espacio pausa · R reiniciar · ? qué es esto

Diagrama de Voronoi

Cada puntito de la pantalla es una semilla. La celda de una semilla es todo el territorio que queda más cerca de ella que de cualquier otra. Nada más que eso. Con esa regla sola aparece todo el mosaico.

celda(p) = { x : dist(x, p) ≤ dist(x, q) para toda otra semilla q }

Las fronteras

Un borde entre dos celdas es la línea de los lugares que están a la misma distancia de las dos semillas: un tramo de la mediatriz del segmento que las une. Por eso los bordes siempre son rectos.

Donde se juntan tres celdas hay un punto que está a igual distancia de tres semillas. Es el centro de un círculo que pasa por las tres y no encierra a ninguna otra.

La otra cara: Delaunay

Si unís con una línea cada par de semillas vecinas, obtenés una red de triángulos: la triangulación de Delaunay. Es el mismo diagrama visto desde el otro lado: cada borde de Voronoi cruza en ángulo recto a una línea de Delaunay.

Lo que pasa en pantalla

Tu cursor es una semilla más: la celda oscura. Por eso las vecinas se deforman cuando lo movés.
Las celdas chicas brillan más: marcan dónde las semillas están apretadas.
Al hacer clic sembrás semillas nuevas y el territorio se reparte de nuevo al instante.
Con el sonido activado, cada vez que el cursor entra a otra celda suena una nota.

Dónde aparece

En el pelaje de la jirafa, las alas de la libélula, el barro que se agrieta al secarse y la espuma. Cada vez que algo crece desde varios centros al mismo ritmo hasta chocar con sus vecinos, dibuja un Voronoi.

También sirve para responder «¿cuál es el más cercano?»: qué hospital, qué antena o qué estación de lluvia cubre cada zona. En 1854, John Snow marcó en un mapa de Londres qué casas tenían más cerca la bomba de agua de Broad Street y así encontró el origen de una epidemia de cólera.

Un poco de historia

Descartes ya dibujó algo parecido en 1644. Dirichlet lo estudió en 1850 y el matemático ucraniano Georgy Voronoi lo generalizó en 1908; el nombre quedó por él. El meteorólogo Alfred Thiessen lo reinventó en 1911 para promediar lluvias, y por eso en geografía también se les dice polígonos de Thiessen.

Cómo se calcula acá

Primero se arma la triangulación de Delaunay y de ahí se deducen las celdas. Se rehace todo desde cero unas 60 veces por segundo, con cientos de semillas, usando la librería d3-delaunay.