geomotif.motifs.voronoi

Voronoi diagrams, the Delaunay triangulation, and Lloyd's relaxation.

Scatter some points and ask, of every place on the page, "which of you is nearest?". The answer divides the plane into one convex cell per point -- the Voronoi diagram -- and joining the points whose cells touch gives the Delaunay triangulation, the same figure read the other way round.

Everything in this module is built from one construction: a site's cell is the region rectangle, clipped by the perpendicular bisector between that site and each of its Delaunay neighbours. No other bisector reaches it, which is what makes this cheap: the neighbours are a handful rather than the whole set, and one triangulation answers every question asked below.

The triangulation itself comes from scipy's Qhull binding, which makes this the one module in the catalog behind an optional dependency::

pip install 'geomotif[scipy]'

That dependency is real rather than a convenience. Points sharing a circle -- a plain square grid, which this library will happily hand you -- are exactly where a hand-rolled incremental triangulator has to break a tie arbitrarily and can then contradict itself; getting that right is Qhull's day job.

scipy is imported when a design is built, not when this module is imported, so these motifs can still be listed, described and reported as unavailable on a machine without it. They carry requires="scipy" in the registry for exactly that reason.

Classes:

Name	Description
Delaunay	The triangulation that joins points whose Voronoi cells touch.
Voronoi	The map of which point is nearest, drawn as its borders.
VoronoiCells	The same map, drawn one closed region at a time.
LloydRelaxation	Points nudged toward the middle of their own cells, over and over.

Delaunay dataclass

Delaunay(points: Sequence[Point], *, merge: bool = False, show_nodes: bool = False)

Bases: SegmentMotif

The triangulation that joins points whose Voronoi cells touch.

Of all the ways to cut a point set into triangles, this is the one that avoids thin ones: no point ever falls inside another triangle's circumcircle, which maximizes the smallest angle in the whole mesh. That is why it is what meshers, terrain models and low-poly renderers use, and why a scatter drawn this way reads as a surface rather than a tangle.

Parameters:

Name	Type	Description	Default
points	sequence of (float, float)	The sites to triangulate. At least three, not all on one line.	required

Voronoi dataclass

Voronoi(points: Sequence[Point], region: Bounds | None = None, *, merge: bool = False, show_nodes: bool = False)

Bases: SegmentMotif

The map of which point is nearest, drawn as its borders.

Each border is drawn once, however many cells meet along it, so the result is a plotter's diagram rather than a stack of outlines -- merge=True then chains those borders into long strokes. :class:VoronoiCells is the same figure when each region matters more than the lines between them.

Parameters:

Name	Type	Description	Default
points	sequence of (float, float)	The sites. At least three, not all on one line.	required
region	Bounds	Where to cut off the cells of the outermost sites, whose borders otherwise run to infinity. Defaults to the points' own extent, grown by a tenth.	None

Methods:

Name	Description
cells	Return one convex cell per site, clipped to the region.
corners	Return the shared corner table and each cell as indices into it.

cells

cells() -> tuple[tuple[Point, ...], ...]

Return one convex cell per site, clipped to the region.

Source code in src/geomotif/motifs/voronoi.py

def cells(self) -> tuple[tuple[Point, ...], ...]:
    """Return one convex cell per site, clipped to the region."""
    sites = tuple(self.points)
    return _cells(sites, _region_for(sites, self.region))

corners

corners() -> tuple[tuple[Point, ...], tuple[tuple[int, ...], ...]]

Return the shared corner table and each cell as indices into it.

Source code in src/geomotif/motifs/voronoi.py

def corners(self) -> tuple[tuple[Point, ...], tuple[tuple[int, ...], ...]]:
    """Return the shared corner table and each cell as indices into it."""
    sites = tuple(self.points)
    region = _region_for(sites, self.region)
    return _welded(_cells(sites, region), _WELD * max(region.width, region.height, 1.0))

VoronoiCells dataclass

VoronoiCells(points: Sequence[Point], region: Bounds | None = None, inset: float = 0.0)

Bases: PolygonMotif

The same map, drawn one closed region at a time.

Each cell is its own closed path, so a border shared by two of them is drawn twice -- the price of having each region be a thing in itself, which is what you want to fill, color, or cut. inset pulls every cell back from its neighbours and gives the cracked-mud look the diagram is usually drawn for.

Parameters:

Name	Type	Description	Default
points	sequence of (float, float)	The sites. At least three, not all on one line.	required
region	Bounds	Where to cut off the outermost cells. Defaults to the points' own extent, grown by a tenth.	None
inset	float	Fraction of the way each cell is pulled toward its own middle. 0 leaves the cells touching; 0.5 halves them.	0.0

LloydRelaxation dataclass

LloydRelaxation(points: Sequence[Point], iterations: int = 3, region: Bounds | None = None)

Bases: Motif

Points nudged toward the middle of their own cells, over and over.

Lloyd's algorithm, and the cheapest way to turn a clumped scatter into an even one that still looks unplanned. Each pass replaces every point with the center of area of its Voronoi cell; a point in a crowd is off-center in its own cell and drifts away from the crowd, a point in a gap is already central and stays. The fixed point of that -- reached in a handful of passes -- is a centroidal diagram, which is what stippling, dot art and object scattering all want.

Produces loose points, not strokes: the result is the input to the other motifs here rather than a drawing of its own.

Parameters:

Name	Type	Description	Default
points	sequence of (float, float)	The sites to even out. At least three, not all on one line.	required
iterations	int	Passes to run. Most of the work happens in the first three.	3
region	Bounds	The area the points are kept inside. Defaults to their own extent, grown by a tenth, and is fixed at the start so the set cannot creep.	None

Methods:

Name	Description
relaxed	Return the points after the relaxation, ready to feed another motif.

relaxed

relaxed() -> tuple[Point, ...]

Return the points after the relaxation, ready to feed another motif.

Source code in src/geomotif/motifs/voronoi.py

def relaxed(self) -> tuple[Point, ...]:
    """Return the points after the relaxation, ready to feed another motif."""
    sites = tuple(self.points)
    return _relaxed(sites, _region_for(sites, self.region), self.iterations)