Visualize Lloyd Relaxation of a Planar Voronoi Tessellation

Visualize the convergence of a random planar point set toward a centroidal Voronoi configuration through changes in cell shapes and areas

A Voronoi tessellation partitions the plane into cells, where each cell contains the points closest to a given generator. Lloyd's algorithm refines the tessellation by repeatedly moving each generator to the centroid of its cell, producing more balanced cell areas and more regular cell shapes. This example applies the algorithm for 25 iterations and visualizes each stage as an area-colored mosaic to show the geometric convergence.

Generate 30 random seed points in the interior of the unit square (points are initialized away from the boundary to avoid degenerate cells at the first tessellation step):

In[1]:=

SeedRandom[17];seedPts=RandomReal[{0.05,0.95},{30,2}];

Define one Lloyd iteration by constructing the Voronoi mesh on the unit square, replacing each generator with its cell centroid, and clipping the updated points to an interior margin:

In[2]:=

lloydStep[pts_]:=Module[{mesh,cells,centroids},mesh=VoronoiMesh[pts,{{0,1},{0,1}}];cells=MeshPrimitives[mesh,2];centroids=RegionCentroid/@cells;Clip[#,{0.02,0.98}]&/@centroids]

Run 25 iterations starting from the initial seed points, recording every intermediate configuration:

In[3]:=

allConfigs=NestList[lloydStep,seedPts,25];

Define a rendering function that smooths the Voronoi cells and colors them by normalized area, with smaller cells shown darker and larger cells shown brighter:

In[4]:=

renderState[pts_]:=Module[{mesh,cells,areas,colors},mesh=VoronoiMesh[pts,{{0,1},{0,1}}];cells=MeshPrimitives[mesh,2];areas=Area/@cells;colors=ColorData["SolarColors"][Rescale[#,MinMax[areas]]]&/@areas;Graphics[MapThread[{#1,#2}&,{colors,cells}],BackgroundGrayLevel[0.08],PlotRange{{0,1},{0,1}},ImageSize320,FrameFalse]]

Compare the initial, intermediate, and final tessellations. The cells become more uniform across the iterations:

In[5]:=

GraphicsGrid[{renderState/@allConfigs〚{1,13,26}〛},Spacings{0.02,0}]

Out[5]=

Animate the full 26-step sequence:

In[6]:=

Animate[renderState[allConfigs〚i〛],{i,1,26,1},AnimationRate4,DisplayAllStepsTrue,ControlPlacementTop,SaveDefinitionsTrue]

Out[6]=

Source Metadata

Citation:
- Stuart P. Lloyd, "Least Squares Quantization in PCM," IEEE Transactions on Information Theory, 28(2), 129–137, 1982. DOI: 10.1109/TIT.1982.1056489
- Qiang Du, Vance Faber, and Max Gunzburger, "Centroidal Voronoi Tessellations: Applications and Algorithms," SIAM Review, 41(4), 637–676, 1999. DOI: 10.1137/S0036144599352836

Publisher Information

Contributed by: Wolfram Staff

License Information

This work is licensed under a Creative Commons Attribution 4.0 International License

Wolfram Language Example Repository

Visualize Lloyd Relaxation of a Planar Voronoi Tessellation

Source Metadata

See Also

Publisher Information

License Information

Visualize Lloyd Relaxation of a Planar Voronoi Tessellation

Source Metadata

See Also

Related Symbols

Publisher Information

License Information