Lloyd's Algorithm: Voronoi diagrams relaxation
Implementation of Lloyd’s Algorithm in JavaScript. Also referred to as Voronoi relaxation, it is often used to evenly distribute partitions of space. It also offers nice graphical effects
Click to add a point
Frame time:
Intro
The Lloyd’s Algorithm1, often referred to as Voronoi relaxation, is a computational geometry algorithm used for distributing a set of point in the space evenly. The algorithm also partitions the space in uniformly shaped convex cells.
This finds applications in several problems that range from smoothing geometry meshes used in finite element methods to artistic patterns like stippling.
I’m usually fascinated by geometric algorithms and even more when these have beautiful graphical translations.
Since I already wrote a JavaScript implementation of Steven Fortune’s Algorithm for computing Voronoi diagrams, building a Lloyd’s Algorithm was an easy task.
I wrote below a few details about this.
The Algorithm
The algorithm is based on iteratively computing the Voronoi diagram of a set of points equal to the centroid of the Voronoi cells of the earlier iteration.
Do while the set S has not converged:
1. Generate the Voronoi tesselation for a set of points S
2. Compute the centroid of each Voronoi cell
3. Update S using the centroids
Generation of Voronoi diagram
The generation of the Voronoi diagram is the most complex step. I wrote more about it in this post. My JavaScript code is on GitHub. The code is simple and takes as input a set of points and outputs a list of polygons identified by their vertices.
Computations of centroids
Generically, the centroid of a region characterized by a density function \(\rho\) is defined as:
\[C = \frac{\int_{A}\mathbf{x}\rho(\mathbf{x}) dA}{\int_{A}\rho(\mathbf{x}) dA}\]where \(A\) is the region of interest. Assuming that the regions are convex polygons with constant density, the centroid coordinates2 can be found with:
\[C_{\mathrm x} = \frac{1}{6A}\sum_{i=0}^{n-1}(x_i+x_{i+1})(x_i\ y_{i+1} - x_{i+1}\ y_i)\]and
\[C_{\mathrm y} = \frac{1}{6A}\sum_{i=0}^{n-1}(y_i+y_{i+1})(x_i\ y_{i+1} - x_{i+1}\ y_i)\]where the polygon area \(A\) is:
\[A = \frac{1}{2}\sum_{i=0}^{n-1} (x_i\ y_{i+1} - x_{i+1}\ y_i)\]Here the vertices index is ordered along the path. Since the Voronoi algorithm returns a list of unordered vertices for each site, I first need to compute the convex hull of the cell. I discuss two methods in this post.
Convergence
The process can be simply stopped once the cumulative distance between the points of two subsequent iterations is below a certain threshold.