Voronoi diagrams

detroit.Voronoi(delaunay: Delaunay, bounds: tuple[float, float, float, float] | None = None)

Voronoi diagram for the given Delaunay triangulation. When rendering, the diagram will be clipped to the specified bounds = [xmin, ymin, xmax, ymax].

Parameters:

• delaunay (Delaunay) – Delaunay object

• bounds (tuple[float, float, float, float] | None) – The bounds of the viewport [xmin, ymin, xmax, ymax] for rendering the Voronoi diagram. If bounds is not specified, it defaults to [0, 0, 960, 500]

detroit.delaunay

Delaunay object

Type:

Delaunay

detroit.vectors

List \([v_{x_0}, v_{y_0}, w_{x_0}, w_{y_0}, \ldots]\) where each non-zero quadruple describes an open (infinite) cell on the outer hull, giving the directions of two open half-lines.

Type:

list[float]

detroit.circumcenters

The circumcenters of the Delaunay triangles \([c_{x_0}, c_{y_0}, c_{x_1}, c_{y_1}, \ldots]\). Each contiguous pair of coordinates \(c_x\), \(c_y\) is the circumcenter for the corresponding triangle. These circumcenters form the coordinates of the Voronoi cell polygons.

Type:

list[float]

detroit.xmin

Bound of viewport

Type:

float

detroit.xmax

Bound of viewport

Type:

float

detroit.ymin

Bound of viewport

Type:

float

detroit.ymax

Bound of viewport

Type:

float

class detroit.delaunay.voronoi.Voronoi(delaunay: Delaunay, bounds: tuple[float, float, float, float] | None = None)

Voronoi diagram for the given Delaunay triangulation. When rendering, the diagram will be clipped to the specified bounds = [xmin, ymin, xmax, ymax].

Parameters:

• delaunay (Delaunay) – Delaunay object

• bounds (tuple[float, float, float, float] | None) – The bounds of the viewport [xmin, ymin, xmax, ymax] for rendering the Voronoi diagram. If bounds is not specified, it defaults to [0, 0, 960, 500]

delaunay

Delaunay object

Type:

Delaunay

vectors

List \([v_{x_0}, v_{y_0}, w_{x_0}, w_{y_0}, \ldots]\) where each non-zero quadruple describes an open (infinite) cell on the outer hull, giving the directions of two open half-lines.

Type:

list[float]

circumcenters

The circumcenters of the Delaunay triangles \([c_{x_0}, c_{y_0}, c_{x_1}, c_{y_1}, \ldots]\). Each contiguous pair of coordinates \(c_x\), \(c_y\) is the circumcenter for the corresponding triangle. These circumcenters form the coordinates of the Voronoi cell polygons.

Type:

list[float]

xmin

Bound of viewport

Type:

float

xmax

Bound of viewport

Type:

float

ymin

Bound of viewport

Type:

float

ymax

Bound of viewport

Type:

float

cell_polygon(i: int) → list[tuple[float, float]] | None

Returns the convex closed polygon \([[x_0, y_0], [x_1, y_1], \ldots, [x_0, y_0]]\) representing the cell for the specified point i.

Parameters:

i (int) – Point index

Returns:

Convex closed polygon \([[x_0, y_0], [x_1, y_1], \ldots, [x_0, y_0]]\)

Return type:

list[tuple[float, float]] | None

cell_polygons() → Iterator[list[tuple[float, float]] | None]

Returns an iterable over the non-empty polygons for each cell, with the cell index as property.

Returns:

Non-empty polygons for each cell

Return type:

Iterator[list[tuple[float, float]] | None]

contains(i: int, x: float, y: float) → bool

Returns True if the cell with the specified index i contains the specified point \((x, y)\); i.e., whether the point i is the closest point in the diagram to the specified point. (This method is not affected by the associated Voronoi diagram’s viewport bounds.)

Parameters:

• i (int) – Cell index

• x (float) – X-coordinate point

• y (float) – Y-coordinate point

Returns:

True if cell contains the specified point

Return type:

bool

neighbors(i: int) → Iterator[int]

Returns an iterable over the indexes of the cells that share a common edge with the specified cell i. Voronoi neighbors are always neighbors on the Delaunay graph, but the converse is false when the common edge has been clipped out by the Voronoi diagram’s viewport.

Parameters:

i (int) – Cell index

Returns:

Iterable over the indexes of the cells

Return type:

Iterator[int]

render(context: Context | None = None) → str | None

Renders the mesh of Voronoi cells to the specified context. If a context is not specified, an SVG path string is returned instead.

Parameters:

context (Context | None) – Context object

Returns:

SVG path string

Return type:

str | None

render_bounds(context: Context | None = None) → str | None

Renders the viewport extent to the specified context. Equivalent to context.rect(voronoi.xmin, voronoi.ymin, voronoi.xmax - voronoi.xmin, voronoi.ymax - voronoi.ymin). If a context is not specified, an SVG path string is returned instead.

Parameters:

context (Context | None) – Context object

Returns:

SVG path string

Return type:

str | None

render_cell(i: int, context: Context | None = None) → str | None

Renders the cell with the specified index i to the specified context. If a context is not specified, an SVG path string is returned instead.

Parameters:

• context (Context | None) – Context object

• i (int) – Cell index

Returns:

SVG path string

Return type:

str | None

update() → Voronoi

Updates the Voronoi diagram and underlying triangulation after the points have been modified in-place — useful for Lloyd’s relaxation.

Returns:

Itself

Return type:

Voronoi