 |
|---|
| 1000 Voronoi cells in a concave arc segment |
This is Lloyd's algorithm implemented with WebGPU. The implementation is similar to the one used in the Swingline Voronoi Stippling Library.
I'm glad you asked! Lloyd's algorithm is a method for finding evenly spaced points within a Euclidean subplane by iteratively constructing Voroni diagrams which partition a subset of the plane into regions called "cells" or "Voronoi cells." Each cell comprises the coordinates closest to the point inside it. Here's an example of a Voronoi diagram of 100 random points on a plane. The cells are color-coded for clarity:
 |
|---|
| Vornoi diagram of 100 random points on a plane |
For an example of a practical application, imagine the dots represent items on a screen and you want to highlight the item closest to the user’s mouse. In this scenario, you can render a hidden Voronoi diagram and highlight a dot when the mouse is over that dot's respective cell. If you want to know more about Voronoi Diagrams, I suggest reading Francesco S. Bellelli's excellent article The fascinating world of Voronoi diagrams.
Lloyd's algorithm operates through a series of steps aimed at making increasingly more uniform Voronoi cells.Those steps are as follows:
- Start with an initial set of points, distributed randomly within the target space
- Create a Voronoi diagram around those points
- Calculate the centroid (geometric center) of each cell.
- Move each point to the centroid of its cell
- Repeat steps 2 through 5
With each iteration the distance between a point and the centroid of its cell diminishes and the diagram converges to a mesh of relatively uniform cells, like the one pictured at the top of this article.
The project is built with, Webpack and Yarn. You will also need a browser that supports WebGpu
To run this project locally use yarn develop and then visit http://localhost:4000/.