Voronoi y Delaunay: territorios, biomas y regiones

0. Introducción

Voronoi y Delaunay son dos formas de mirar el mismo conjunto de puntos:

• Voronoi divide el plano en regiones: cada punto del plano pertenece al seed más cercano. El resultado son polígonos convexos.
• Delaunay conecta los seeds con aristas — y resulta ser el grafo dual del Voronoi (dos seeds están conectados si comparten un borde de región).

Ambos llegan al gameplay constantemente:

Caso	Voronoi o Delaunay
Territorios de civilización (Civ, Total War)	Voronoi
Mapa de “qué capital me queda más cerca”	Voronoi
Generación de biomas	Voronoi + ruido
Mallas para físicas / colisión	Delaunay
Grafo de adyacencia entre regiones	Delaunay
Triangulación para iluminación / pathfinding	Delaunay
NavMesh inicial	Delaunay

1. Voronoi — el cubo de pintura geométrico

Voronoi: cada celda del plano pertenece al seed más cercano. Las regiones que emergen son polígonos convexos. Arrastra los seeds para ver la forma cambiar; el toggle de métrica cambia "más cercano" entre euclidiana, Manhattan o Chebyshev.

euclideanmanhattanchebyshev

Figura 1 — Cada celda del plano se pinta con el color del seed más cercano. Arrastra los seeds para ver las regiones cambiar. El toggle de métrica cambia “más cercano”: euclidiana (curvas), Manhattan (cuadradas), Chebyshev (octagonales).

1.1 Definición formal

Dado un conjunto de puntos P = {p₁, p₂, ..., pₙ} en el plano:

Región Voronoi de pᵢ = { x ∈ plano : dist(x, pᵢ) ≤ dist(x, pⱼ) para todo j }

En lenguaje de juegos: la región de pᵢ es el conjunto de puntos cuyo seed más cercano es pᵢ.

1.2 Cómo lo computas

Tres opciones, en orden de complejidad:

1. Brute force pixel-distance — para cada píxel del raster, recorré todos los seeds, quédate con el más cercano. O(W × H × N). Es lo que hace la viz de arriba con N=8 y un raster de 200×100. Para producción off-line es viable hasta ~50000 píxeles × 100 seeds.
2. Algoritmo de Fortune — barrido del plano con una “playa” de parábolas. O((N + V) log N) donde V es el número de vértices del diagrama. Es la forma estándar en CG profesional. Difícil de implementar pero hay libs.
3. Jump Flooding (JFA) — algoritmo de paso por niveles que aprovecha shaders. O((W × H) log(max(W, H))). En GPU es virtualmente gratuito incluso a 4K. Es lo que hacen los engines modernos para Voronoi en runtime.

Para visualizaciones tutoriales: brute force y listo. Para gameplay con seeds que se mueven cada frame y mapas grandes: JFA en shader.

1.3 La métrica define la “forma” de las regiones

Cambiar dist(a, b) cambia drásticamente las regiones:

Métrica	Forma de regiones	Caso de uso típico
Euclidiana	Polígonos convexos clásicos	Mapas naturales (biomas, territorios)
Manhattan	Cuadradas/escalonadas	Grids urbanos, ciudad estilo Manhattan
Chebyshev	Octagonales	Tactical con diagonales gratis

2. Delaunay — el grafo dual

Delaunay es el grafo dual de Voronoi: dos seeds están conectados por arista si comparten un borde de región. Sirve para grafos de adyacencia, mallas para FEM, y triangulaciones óptimas.

mostrar Voronoimostrar Delaunay

Figura 2 — Voronoi (regiones tintadas) y Delaunay (aristas negras) del mismo set de puntos. Toggles para ver uno u otro. Notá que cada arista de Delaunay cruza un borde de Voronoi: son grafos duales.

2.1 Propiedad clave

Una triangulación de un set de puntos es Delaunay si:

Para cada triángulo T, ningún otro punto está dentro de su círculo circunscrito.

Esa propiedad maximiza el ángulo mínimo de los triángulos — produce mallas “lo más equiláteras posible”. En CG, eso significa:

• Mejor calidad visual para iluminación basada en mesh.
• Mejor estabilidad numérica para físicas y FEM.
• Adyacencias geométricamente “razonables” (vecinos cercanos).

2.2 Bowyer-Watson (algoritmo incremental)

function delaunay(points)
    triangulation = { superTriangle that contains all points }
    for each p in points:
        badTriangles = { t in triangulation : p is inside circumcircle(t) }
        polygonHole = boundary edges of badTriangles
        remove badTriangles from triangulation
        for each edge in polygonHole:
            add new triangle (edge.a, edge.b, p) to triangulation
    remove triangles touching superTriangle
    return triangulation

Complejidad: O(N²) en el peor caso, O(N log N) si los puntos están bien distribuidos. Para N = 100, instantáneo. Para N = 10000, hay que optimizar (delaunator).

2.3 Dualidad Voronoi ↔ Delaunay

Voronoi	Delaunay
Vértices	Triángulos
Aristas	Aristas (perpendiculares al Voronoi correspondiente)
Regiones	Vértices (los seeds originales)

Eso significa que calcular uno te da el otro casi gratis. Si haces Delaunay primero, los vértices del Voronoi son los circuncentros de los triángulos. Si haces Voronoi primero, las aristas de Delaunay son los pares de seeds adyacentes.

3. Aplicación: generación de biomas

Biomas: Voronoi base + ruido en los píxeles para fronteras orgánicas. Sin ruido las fronteras serían rectas como las de Civilization V; con ruido se ven naturales como en Civ VI o Old World.

noise amp: 20px↺ Nueva seed

Figura 3 — Voronoi base + ruido en los píxeles para fronteras orgánicas. Civ V usa Voronoi puro; Civ VI y Old World agregan ruido para que las fronteras se vean naturales. Click para regenerar; slider de amplitud de ruido.

3.1 La técnica

function biomeMap(width, height, seeds)
    for each pixel (x, y):
        // distorsionar coordenadas con ruido perlin/simplex
        nx = x + perlinNoise(x, y, freq) * amplitude
        ny = y + perlinNoise(x, y + 1000, freq) * amplitude
        // ahora el pixel "distorsionado" decide su seed
        nearestSeed = argmin(seed in seeds, dist((nx, ny), seed))
        biomeMap[x, y] = nearestSeed.biome

Sin ruido, las fronteras son rectas (Voronoi puro). Con ruido, cada píxel “ve” su mundo levemente distorsionado, y decide su biome basándose en eso. Resultado: fronteras orgánicas con dedos, islas, penínsulas.

3.2 Combinar Voronoi con otros pases

Pipeline canónico para mapas de Civ:

1. Voronoi grueso → regiones grandes (continentes).
2. Perlin noise sobre la Voronoi → fronteras orgánicas dentro de cada región.
3. Heightmap → desniveles dentro de cada bioma.
4. Filtros → islas chicas, lagos, “mar interno”, etc.

3.3 Casos canónicos

• Civilization V: Voronoi puro para influencia cultural, fronteras rectas (estilo “frontera de pizarra”).
• Civilization VI: Voronoi distorsionado, fronteras naturales.
• Old World: similar a Civ VI con ruido + ajustes manuales por desarrollador.
• Dwarf Fortress (regiones del mundo): Voronoi + capas de clima + erosión.

4. Pseudocódigo — Bowyer-Watson y el dual

function delaunay(points: List<Pt>) -> List<Tri>
    superT = makeSuperTriangle(points.boundingBox * 20)
    triangulation = [superT]
    for each p in points:
        bad = []
        for each t in triangulation:
            if p inside circumcircle(t):
                bad.append(t)
        // detectar el polígono hole
        edgeCount = Map<Edge, int>
        for each t in bad:
            for each edge in edgesOf(t):
                edgeCount[edge] += 1
        // edges que aparecen 1 vez son borde del hole
        triangulation = triangulation - bad
        for each (edge, count) in edgeCount:
            if count == 1:
                triangulation.append(triangle(edge.a, edge.b, p))
    return triangulation - trianglesUsingSuperTriangleVertices


function voronoiCellsFromDelaunay(delaunay, points) -> Map<seedIdx, List<Pt>>
    cells = Map()
    for each seed s in points:
        // seed s tiene su celda como el polígono formado por los
        // circuncentros de los triángulos que contienen s, en orden CCW
        sharedTris = triangulesContaining(s, delaunay)
        circumcenters = sharedTris.map(circumcenter)
        cells[s] = orderCCW(circumcenters)
    return cells

5. Implementación en Unity / C#

using UnityEngine;
using System.Collections.Generic;

public static class Voronoi {
    public static int[,] Rasterize(int width, int height, Vector2[] seeds) {
        var owner = new int[width, height];
        for (int y = 0; y < height; y++)
            for (int x = 0; x < width; x++) {
                int best = 0;
                float bestD = float.PositiveInfinity;
                for (int i = 0; i < seeds.Length; i++) {
                    float dx = x - seeds[i].x, dy = y - seeds[i].y;
                    float d = dx * dx + dy * dy;
                    if (d < bestD) { bestD = d; best = i; }
                }
                owner[x, y] = best;
            }
        return owner;
    }
}

public static class Delaunay {
    public struct Triangle { public int A, B, C; }

    static bool InCircumcircle(Vector2 p, Vector2 a, Vector2 b, Vector2 c) {
        float d = 2f * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
        if (Mathf.Abs(d) < 1e-9f) return false;
        float ax2 = a.sqrMagnitude, bx2 = b.sqrMagnitude, cx2 = c.sqrMagnitude;
        float ux = (ax2 * (b.y - c.y) + bx2 * (c.y - a.y) + cx2 * (a.y - b.y)) / d;
        float uy = (ax2 * (c.x - b.x) + bx2 * (a.x - c.x) + cx2 * (b.x - a.x)) / d;
        float r2 = (a.x - ux) * (a.x - ux) + (a.y - uy) * (a.y - uy);
        float dx = p.x - ux, dy = p.y - uy;
        return dx * dx + dy * dy <= r2 + 1e-9f;
    }

    public static List<Triangle> BowyerWatson(Vector2[] points) {
        // ... implementación equivalente al pseudocódigo, usando lista de triangles e
        // intercambiando bad vs new. Para producción seria, prefer 'delaunator-cs' o similar.
        return new List<Triangle>();
    }
}

6. En otros engines

• Godot: trae Geometry2D.triangulate_polygon pero no Voronoi. Plugins como voronoi-godot están disponibles.
• Unreal: FDelaunayMeshFiltering interno al sistema de Geometry Tools. Para gameplay, escribir custom es típico.
• JavaScript / TypeScript: librerías como d3-delaunay y delaunator son la opción standard. Para GPU/realtime, three-mesh-bvh con shader custom.

7. Quiz

Pon a prueba lo que entendiste

Responde una por una. La explicación aparece al elegir, correcta o no.

1. Quieres dividir un mapa en territorios donde cada región pertenece al líder más cercano. ¿Voronoi o Delaunay?

   • AVoronoi: divide el plano en regiones según seed más cercano. Cada territorio es un polígono convexo. Civilization, Total War, etc.
   • BDelaunay: traza los caminos entre líderes.
   • CFloodfill desde cada líder.

2. Tu mapa de biomas con Voronoi puro tiene fronteras rectas y se ve artificial. ¿Cómo lo arreglas?

   • ADistorsionás cada píxel con noise (Perlin/Simplex) antes de calcular el seed más cercano. Las fronteras se vuelven orgánicas, con dedos y penínsulas.
   • BAgregar más seeds para que las fronteras sean más cortas.
   • CCambiar la métrica de euclidiana a manhattan.

3. Estás generando una malla para físicas y necesitas triángulos lo más equiláteros posible. ¿Qué triangulación?

   • ADelaunay. Maximiza el ángulo mínimo de los triángulos: produce mallas estables, sin triángulos 'agudos' que causan problemas numéricos.
   • BCualquier triangulación que cubra el polígono.
   • CVoronoi (los polígonos del Voronoi).

4. El algoritmo Bowyer-Watson funciona en O(N²) en el peor caso. ¿Cuándo importa?

   • AEn generación procedural off-line con muchos puntos (10000+), preferís delaunator (O(N log N)). Para vizzes interactivas con < 100 puntos, Bowyer-Watson directo es suficiente.
   • BNunca importa: Bowyer-Watson siempre es la opción correcta.
   • CSolo en GPUs, donde el algoritmo no escala.

5. Tienes 8 capitales en un mapa y necesitas el grafo de adyacencia entre ellas (qué capitales son vecinas). ¿Voronoi o Delaunay?

   • ADelaunay. Es el grafo dual de Voronoi: dos seeds están conectados si comparten un borde de región. Adyacencia = arista de Delaunay.
   • BVoronoi y luego buscar pares con borde común.
   • CFloodfill desde cada capital.

8. Siguientes pasos