Voronoi Diagram from Random Seeds

Math essence

argmin_i || (x, y) - pts_i ||^2 over all pixels (x, y). Lloyd relaxation approximates: pts_i := mean(pixel : argmin = i) using a 32x32 subsample for speed.

Parameters

Reference

First 60 lines of reference.py. Full source: library_external/reas_processing/voronoi/reference.py

from __future__ import annotations

from typing import ClassVar

import numpy as np


class Voronoi:
    """Voronoi diagram from jittered random seed points.

    A set of *num_seeds* points is sampled inside the canvas; each pixel
    is colored with the seed's color whose point it is closest to. On
    each ``step`` every seed drifts a small random amount, so the cell
    mosaic slowly shifts, grows, and merges. Lloyd relaxation (``n``
    rounds) snaps seeds toward their cell centroids before the first
    render, producing the smooth, even cells popular in Casey Reas's
    generative art canon.
    """

    family: ClassVar[str] = "reas_processing"
    sketch: ClassVar[str] = "voronoi"

    def __init__(
        self,
        dim: int = 320,
        num_seeds: int = 60,
        lloyd_steps: int = 6,
        step_jitter: float = 6.0,
        palette_mode: str = "rainbow",
        seed: int | None = None,
    ) -> None:
        self.dim = dim
        self.num_seeds = num_seeds
        self.lloyd_steps = lloyd_steps
        self.step_jitter = step_jitter
        self._palette_mode = palette_mode
        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_step(self.pts)

    def _lloyd_step(self, pts: np.ndarray) -> np.ndarray:
        n = self.dim
        # coarse sub-sampling 32x32 instead of n*n for speed
        sub = 32
        grid = np.stack(
            np.meshgrid(
                np.linspace(0, n - 1, sub),
                np.linspace(0, n - 1, sub),
                indexing="ij",
            ),
            axis=-1,
        ).reshape(-1, 2)