Foundations of Computational Geometry: Delaunay and Voronoi
To understand weighted stippling, one must first grasp the relationship between Delaunay triangulation and Voronoi diagrams. At their core, both concepts rely on a set of seed points. A Delaunay triangulation creates a mesh of triangles where no seed point lies inside the circumcircle of any triangle in the network. This property ensures that the triangles are as 'fat' as possible, avoiding long, thin slivers. For developers using JavaScript, leveraging the d3-delaunay package is a highly efficient way to compute these structures without reinventing complex geometric algorithms from scratch.
A Voronoi diagram is the dual of the Delaunay triangulation. It partitions a two-dimensional plane into polygons, or 'cells,' where every point inside a specific cell is closer to its seed point than to any other. This is not merely a mathematical curiosity; it is a fundamental way to describe spatial distribution. In our coding context, we use D3.js to handle the heavy lifting of these calculations, passing an array of coordinates into a Delaunay object and then generating the Voronoi partition from it.
Key insight: The centers of the circumcircles of Delaunay triangles are exactly the vertices that define the Voronoi polygons.
While p5.js is excellent for rendering, D3.js provides the robust data structures needed for fast geometric lookups. Mixing these libraries allows us to maintain a high frame rate while performing complex spatial analysis on thousands of points simultaneously. When initializing your points, remember to format them as a single flat array of [x, y, x, y...] for compatibility with D3's expectations.
| Concept | Primary Characteristic | Visual Result |
|---|---|---|
| Delaunay Triangulation | Empty circumcircle property | Connected mesh of triangles |
| Voronoi Diagram | Proximity-based partitioning | Mosaic of unique polygons |
The Art of Relaxation: Implementing Lloyd's Algorithm
Randomly distributed points often look cluttered or 'noisy.' To achieve a more organized and professional aesthetic, we apply Lloyd's algorithm, also known as Voronoi relaxation. This process involves finding the centroid (the center of mass) of each Voronoi polygon and moving the seed point toward that center. By repeating this process over multiple frames, the points 'relax' into a balanced, organic distribution similar to patterns found in nature, such as the arrangement of cells in a leaf.
Calculating the centroid of a polygon requires more than just averaging the vertices. For a true geometric center, you must calculate the area and use the cross product of the vertices. This math ensures that the point moves to the precise balance point of the polygon's shape. Without this accuracy, the points might collapse into clusters or 'black holes' rather than spreading out evenly across the canvas.
- Step 1: Generate a Voronoi diagram for the current points.
- Step 2: Calculate the centroid of each resulting polygon.
- Step 3: Interpolate (lerp) the points toward their respective centroids.
- Step 4: Recompute the Voronoi diagram and repeat.
Caution: A naive average of polygon vertices is not a true centroid; it will lead to geometric instability in dense distributions.
As the points move, the Voronoi cells shift shape, which in turn changes the next centroid. This iterative feedback loop is what creates the 'breathing' effect during the relaxation phase. Using a lerp (linear interpolation) factor allows you to control the speed of this relaxation, creating a smooth animation as the points find their optimal positions. Relaxation is the secret ingredient that separates a simple random dot plot from a sophisticated geometric artwork.
Integrating Image Data: The Weighted Centroid Logic
Standard stippling uses uniform dot distributions, but to recreate an image, we must weight the dots based on pixel brightness. In a weighted Voronoi diagram, the 'mass' of each pixel within a Voronoi cell influences the final position of the centroid. Darker pixels are assigned a higher weight, pulling the seed points toward them. This creates a higher density of dots in the shadows of an image and a lower density in the highlights, mimicking the traditional artistic technique of stippling.