environmentaltools.spatial.generate_CVD

environmentaltools.spatial.generate_CVD(points, iterations, bounding_box)[source]

Generate Centroidal Voronoi Diagram using Lloyd’s algorithm.

Iteratively computes a Centroidal Voronoi Diagram (CVD) where each Voronoi cell’s generator point converges to the centroid of its cell. This creates a more uniform and optimized spatial tessellation compared to standard Voronoi diagrams.

Parameters:

  • points (np.ndarray) – Initial generator points as (N, 2) array of [x, y] coordinates

  • iterations (int) – Number of Lloyd’s algorithm iterations to perform. More iterations produce better convergence to true centroids. Typical values: 5-50.

  • bounding_box (tuple or list) – Rectangular bounds as [xmin, xmax, ymin, ymax] defining the region for the Voronoi diagram

Returns:

Bounded Voronoi diagram object with additional attributes: - filtered_points: generator points within bounding box - filtered_regions: region indices corresponding to filtered points

Return type:

scipy.spatial.Voronoi

Notes

Lloyd’s algorithm (1982) iteratively: 1. Constructs bounded Voronoi diagram from current points 2. Calculates centroid of each Voronoi cell 3. Moves generator points to cell centroids 4. Repeats until convergence or max iterations reached

Reference: https://www.py4u.net/discuss/21901

Examples

>>> import numpy as np
>>> # Random initial points
>>> points = np.random.rand(20, 2) * 100
>>> # Generate CVD within 100x100 box
>>> vor = generate_CVD(points, iterations=10, bounding_box=[0, 100, 0, 100])