Spaces:
Running
Running
File size: 3,257 Bytes
a8784d9 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | """Seed-point sampling for the Voronoi partition.
Bridson Poisson-disk sampling gives blue-noise seeds: random but evenly spread,
so piece areas stay within sane bounds (no slivers, no giant blobs). We target
a piece count, derive the min-distance r from area, then top up / trim to hit
the exact count.
Bridson is Theta(k) in the number of accepted samples (grid-accelerated
neighbour test), Theta(grid cells) = Theta(W*H / r^2) space.
"""
from __future__ import annotations
import math
import numpy as np
def poisson_disk(
width: int,
height: int,
radius: float,
rng: np.random.Generator,
k: int = 30,
) -> np.ndarray:
"""Bridson's algorithm. Returns (n, 2) float array of (x, y) samples."""
cell = radius / math.sqrt(2)
gw = int(math.ceil(width / cell))
gh = int(math.ceil(height / cell))
grid = -np.ones((gh, gw), dtype=np.int64)
samples: list[tuple[float, float]] = []
active: list[int] = []
def grid_xy(p):
return int(p[0] / cell), int(p[1] / cell)
first = (rng.uniform(0, width), rng.uniform(0, height))
samples.append(first)
gx, gy = grid_xy(first)
grid[gy, gx] = 0
active.append(0)
while active:
idx = active[rng.integers(len(active))]
base = samples[idx]
placed = False
for _ in range(k):
ang = rng.uniform(0, 2 * math.pi)
rad = rng.uniform(radius, 2 * radius)
cand = (base[0] + rad * math.cos(ang), base[1] + rad * math.sin(ang))
if not (0 <= cand[0] < width and 0 <= cand[1] < height):
continue
cgx, cgy = grid_xy(cand)
ok = True
for ny in range(max(0, cgy - 2), min(gh, cgy + 3)):
for nx in range(max(0, cgx - 2), min(gw, cgx + 3)):
j = grid[ny, nx]
if j >= 0:
d = math.dist(cand, samples[j])
if d < radius:
ok = False
break
if not ok:
break
if ok:
samples.append(cand)
grid[cgy, cgx] = len(samples) - 1
active.append(len(samples) - 1)
placed = True
break
if not placed:
active.remove(idx)
return np.asarray(samples, dtype=np.float32)
def sample_seeds(
width: int,
height: int,
n_pieces: int,
rng: np.random.Generator,
) -> np.ndarray:
"""Return exactly `n_pieces` blue-noise seeds (x, y) inside the page."""
n_pieces = max(2, int(n_pieces))
# r from target area per piece: area ~ W*H/n, packing factor ~0.7.
area_per = (width * height) / n_pieces
radius = math.sqrt(area_per) * 0.66
pts = poisson_disk(width, height, radius, rng)
# Top up with uniform random points if Poisson under-shot.
if len(pts) < n_pieces:
extra = rng.uniform([0, 0], [width, height], size=(n_pieces - len(pts), 2))
pts = np.vstack([pts, extra.astype(np.float32)])
# Trim deterministically if it over-shot.
if len(pts) > n_pieces:
keep = rng.choice(len(pts), size=n_pieces, replace=False)
pts = pts[keep]
return pts.astype(np.float32)
|