Un diagrama de Voronoi divide el plano en regiones donde cada punto pertenece al sitio generador más cercano. Esta partición aparece naturalmente en territorios animales, estructuras celulares, cristales y redes de telecomunicaciones. Es una de las estructuras geométricas más ubicuas en la naturaleza.
Lo que observarás en esta simulación
- Celdas coloreadas: cada región contiene todos los puntos más cercanos a su semilla
- Bordes de Voronoi: equidistantes de exactamente dos semillas (mediatrices)
- Vértices: equidistantes de exactamente tres semillas (circuncentros)
- Triangulación de Delaunay: el grafo dual que conecta semillas vecinas
- Circuncentros: centros de circuncírculos que definen los vértices de Voronoi
Conceptos Fundamentales
Celda de Voronoi
V(p) = {x : d(x,p) ≤ d(x,q) para todo q}. La región de puntos más cercanos al sitio p que a cualquier otro sitio.
Mediatriz
Cada borde de Voronoi yace sobre la mediatriz de dos sitios vecinos: la línea donde ambas distancias son iguales.
Triangulación de Delaunay
El grafo dual: conecta sitios cuyas celdas comparten borde. Maximiza el ángulo mínimo de todos los triángulos.
Circuncírculo Vacío
Propiedad clave de Delaunay: ningún otro sitio cae dentro del circuncírculo de cualquier triángulo.
La Dualidad
Voronoi
Vértices ↔ Triángulos
Aristas ↔ Aristas
Celdas ↔ Vértices
Delaunay
Triángulos ↔ Vértices
Aristas ↔ Aristas
Vértices ↔ Celdas
Los vértices de Voronoi son exactamente los circuncentros de los triángulos de Delaunay. Esta dualidad permite calcular uno a partir del otro eficientemente.
Definición Matemática
La simulación usa el algoritmo de Bowyer-Watson para construir la triangulación de Delaunay incrementalmente, y luego deriva el diagrama de Voronoi conectando los circuncentros.
Experimento 1: Construcción Interactiva
Objetivo: Entender cómo se forman las celdas
- Haz clic en "Limpiar Todo" para empezar con un canvas vacío.
- Añade un solo punto. No hay diagrama con un solo sitio (toda el área le pertenece).
- Añade un segundo punto. Aparece una línea recta: la mediatriz entre ambos sitios.
- Añade un tercer punto. Ahora hay un vértice de Voronoi donde convergen tres mediatrices.
- Continúa añadiendo puntos y observa cómo cada celda es un polígono convexo.
- Arrastra un punto existente y observa cómo se recalcula todo el diagrama en tiempo real.
Conclusión: Las celdas de Voronoi son siempre polígonos convexos. Las celdas del borde son infinitas (se extienden hasta el límite del canvas).
Experimento 2: La Dualidad Voronoi-Delaunay
Objetivo: Visualizar la relación dual
- Carga el preset "10 Aleatorios" para tener suficientes puntos.
- Activa "Mostrar triangulación Delaunay" (aparece en azul cyan).
- Observa que cada triángulo de Delaunay tiene exactamente un vértice de Voronoi en su centro.
- Activa "Mostrar circuncentros" para ver estos puntos en morado.
- Cada arista de Delaunay (conectando dos sitios) es perpendicular a la arista de Voronoi correspondiente.
- Mueve un punto y observa cómo ambas estructuras se actualizan manteniendo la dualidad.
Conclusión: Voronoi y Delaunay son dos caras de la misma moneda. Calcular uno te da el otro.
Experimento 3: Configuraciones Especiales
Objetivo: Explorar patrones de simetría
- Carga el preset "Grilla". Observa que las celdas son cuadrados perfectos debido a la simetría.
- Carga "Círculo". Los 12 puntos en círculo crean celdas triangulares/trapezoidales, con el punto central teniendo una celda dodecagonal.
- Carga "Espiral". Las celdas se alargan siguiendo la curva, más estrechas hacia el centro.
- Carga "Clusters". Los grupos de puntos compiten por espacio, creando fronteras complejas entre clusters.
- En cada configuración, activa la triangulación de Delaunay para ver cómo conecta los puntos.
Conclusión: La distribución de los sitios determina completamente la estructura del diagrama. Patrones regulares producen celdas regulares.
Experimento 4: Animación y Dinámicas
Objetivo: Ver cómo evoluciona el diagrama
- Carga "50 Aleatorios" para tener un diagrama complejo.
- Activa "Animar puntos" y ajusta la velocidad a 1.0x.
- Observa cómo las celdas cambian de forma continuamente a medida que los puntos se mueven.
- Los puntos rebotan en los bordes. Nota cómo los vecinos topológicos pueden cambiar.
- Desactiva "Mostrar celdas coloreadas" y activa solo los bordes para ver mejor la estructura.
- Pausa la animación cuando veas una configuración interesante.
Conclusión: El diagrama de Voronoi cambia continuamente, pero la topología (qué celdas son vecinas) solo cambia cuando tres circuncentros se alinean.
Aplicaciones
Contexto Histórico
René Descartes usó diagramas similares en 1644 para describir la estructura del sistema solar en su teoría de vórtices. Pero fue Georgy Voronoi quien formalizó el concepto matemáticamente a principios del siglo XX, estudiándolo en dimensiones arbitrarias.
Descartes: Usa particiones similares en "Principia Philosophiae" para modelar vórtices cósmicos.
Dirichlet: Estudia dominios de puntos más cercanos en el contexto de formas cuadráticas.
Voronoi: Generaliza a n dimensiones en su trabajo sobre formas cuadráticas positivas.
Delaunay: Introduce la triangulación dual que maximiza ángulos mínimos.
Bowyer y Watson: Publican independientemente el algoritmo incremental que usa esta simulación.
Conexiones Interdisciplinarias
Para Explorar Más
- Aurenhammer, F. (1991) - "Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure"
- Fortune, S. (1987) - "A Sweepline Algorithm for Voronoi Diagrams" - algoritmo O(n log n)
- Simulación: Juego del Caos - Fractales por iteración
- Simulación: Grupos de Simetría - Patrones periódicos en el plano