Voronoi Tessellation with Lloyd Relaxation

Math essence

Lloyd step: for each pixel (x, y) in a coarse grid, compute argmin_i |(x, y) - p_i|^2; for each seed, average the positions of all pixels assigned to it; blend old and new position by `relaxation_blend`. Step adds Gaussian noise to seeds before each Lloyd pass, so cells slowly drift. Render is the nearest-seed partition at full resolution, colored by the seed's palette entry.

Parameters

Reference

First 60 lines of reference.py. Full source: library_external/toxi_openframeworks/VoronoiRelaxation/reference.py

from __future__ import annotations

from typing import ClassVar

import numpy as np


class VoronoiRelaxation:
    """Voronoi tessellation with Lloyd relaxation (toxi / thi.ng style).

    Lloyd's algorithm iteratively replaces each seed with the centroid
    of its Voronoi cell, producing ever-more-uniform polygons. The
    same algorithm is the basis of Karsten Schmidt's oF Voronoi
    tessellation patches (early-2010s demos) and the
    `@thi.ng/geom-voronoi` relaxation examples. To stay interactive on
    pure numpy, the nearest-seed partition is computed on a
    ``sub`` × ``sub`` subsample for centroid estimation and on a
    full-resolution grid for the final image.
    """

    family: ClassVar[str] = "toxi_openframeworks"
    sketch: ClassVar[str] = "voronoirelaxation"

    def __init__(
        self,
        dim: int = 320,
        num_seeds: int = 64,
        lloyd_steps: int = 6,
        step_jitter: float = 4.0,
        relaxation_blend: float = 0.65,
        centroid_sub: int = 48,
        palette_mode: str = "earth",
        show_seeds: bool = True,
        seed_radius: int = 2,
        bg_color: tuple[int, int, int] = (245, 240, 230),
        seed_color: tuple[int, int, int] = (35, 35, 50),
        seed: int | None = None,
    ) -> None:
        self.dim = dim
        self.num_seeds = num_seeds
        self.lloyd_steps = lloyd_steps
        self.step_jitter = step_jitter
        self.relaxation_blend = relaxation_blend
        self.centroid_sub = centroid_sub
        self._palette_mode = palette_mode
        self.show_seeds = show_seeds
        self.seed_radius = seed_radius
        self.bg_color = np.array(bg_color, dtype=np.float32)
        self.seed_color = np.array(seed_color, dtype=np.float32)
        self._seed = seed
        self.reset()

    def reset(self, seed: int | None = None) -> None:
        if seed is not None:
            self._seed = seed
        self.rng = np.random.default_rng(self._seed)
        self.pts = self.rng.uniform(0, self.dim, size=(self.num_seeds, 2))
        self.colors = self._palette(self.num_seeds)
        for _ in range(self.lloyd_steps):
            self.pts = self._lloyd(self.pts, sub=self.centroid_sub)