In generative graphics and computational design, natural organic forms—such as cracked mud, cellular membranes, dragonfly wings, and geometric low-poly terrain—are rarely modeled by hand. Instead, they are synthesized using spatial partitioning algorithms: Delaunay Triangulation and its geometric dual, the Voronoi Diagram. Generative Vector Patterns: Voronoi Diagrams & Delaunay Triangulation in SVG outlines the mathematical proofs, circumcircle test physics, sweep-line algorithms, Lloyd relaxation smoothing, and scalable SVG path serialization required to construct high-performance generative textures in the browser.
The Empty Circumcircle Criterion in Delaunay Triangulation
Given a set of $N$ points in a 2D Euclidean plane $P = \{p_1, p_2, \dots, p_n\}$, there exist many possible planar triangulations connecting all vertices. However, naive triangulation often creates long, skinny "sliver" triangles that produce jagged visual artifacts when shaded.
In 1934, mathematician Boris Delaunay established the condition for optimal planar triangulation:
A triangulation $\mathcal{DT}(P)$ is a Delaunay triangulation if and only if the circumscribed circle of every triangle contains no other points of $P$ in its interior. This condition mathematically maximizes the minimum interior angle of all triangles in the mesh, avoiding skinny polygons and creating aesthetically balanced wireframes.
Algorithmic Comparison: Planar Tessellation Strategies
| Algorithm | Time Complexity | Space Complexity | Primary Advantage |
|---|---|---|---|
| Bowyer-Watson (Incremental) | $O(N^2)$ worst, $O(N \log N)$ avg | $O(N)$ | Simple incremental point insertion into bounding super-triangle |
| Fortune's Sweep-Line | $O(N \log N)$ optimal | $O(N)$ | Deterministic single-pass parabolic wave-front progression |
| Divide-and-Conquer | $O(N \log N)$ | $O(N)$ | Recursive half-plane splitting; highly parallelizable |
| Lloyd Relaxation | $k \times O(N \log N)$ | $O(N)$ | Iteratively smooths cell distributions toward uniform centroidal Voronoi |
The In-Circle Determinant Test
Testing whether a candidate point $D(x_d, y_d)$ lies inside the circumcircle of triangle $\triangle ABC$ (with vertices ordered counter-clockwise) is evaluated using the 4x4 matrix determinant:
If the determinant is strictly greater than zero, point $D$ lies inside the circumcircle, violating the Delaunay condition. The Bowyer-Watson algorithm removes all non-compliant triangles, forms a polygonal cavity bounded by the outer edges, and connects point $D$ to each boundary vertex.
Voronoi Tessellation: The Mathematical Dual Graph
The Voronoi diagram partitions space into discrete convex polygons, where each cell $V(p_i)$ contains all points in the plane whose Euclidean distance to seed $p_i$ is less than or equal to their distance to any other seed $p_j$:
Because the Voronoi diagram is the geometric dual of Delaunay triangulation, constructing Voronoi cells from an existing Delaunay mesh is computationally direct:
- Circumcenter Mapping: The circumcenter $(U_x, U_y)$ of each Delaunay triangle becomes a Voronoi polygon vertex.
- Edge Orthogonality: For every Delaunay edge connecting points $p_i$ and $p_j$, the corresponding Voronoi edge is a segment of the perpendicular bisector connecting the circumcenters of the two triangles sharing that edge.
Lloyd Relaxation: Achieving Organic Centroidal Distributions
Randomly distributed seed points produce irregular Voronoi cells with high variance in area and shape. To achieve organic, biological textures (such as giraffe coat patterns or honeycombs), engines execute Lloyd Relaxation:
- Compute Polygon Centroid: For each closed Voronoi polygon with vertices $(x_0, y_0), \dots, (x_{k-1}, y_{k-1})$, the algorithm calculates its geometric center of mass:
C_x = \frac{1}{6A} \sum_{i=0}^{k-1} (x_i + x_{i+1})(x_i y_{i+1} - x_{i+1} y_i)
- Relocate Seed Points: Move each original seed point $p_i$ to its polygon centroid $C(p_i)$.
- Re-triangulate: Re-run Delaunay triangulation. Repeating this loop 3 to 5 times converges the mesh into a Centroidal Voronoi Tessellation (CVT) with uniformly proportioned hexagonal cells.
High-Performance SVG Path Serialization
Emitting thousands of individual <polygon> elements into the SVG DOM overburdens the browser layout engine.
Production vector generators clip external ray boundaries against the viewBox rectangle (using the Sutherland-Hodgman polygon clipping algorithm), sort vertices in clockwise order, and compile all cell outlines into a single consolidated <path> element using d="M x1 y1 L x2 y2 ... Z M x3 y3 ...". This reduces DOM node count from thousands to one, allowing smooth 60 FPS morphing and interactive pointer exploration.
Bowyer-Watson Incremental Cavity Retriangulation
When implementing Delaunay triangulation interactively in TypeScript, the Bowyer-Watson algorithm provides an elegant incremental approach. The algorithm initializes the planar coordinate space by creating an initial bounding super-triangle large enough to encompass all candidate data points. As each new point is introduced sequentially, the algorithm executes the in-circle determinant test across all existing triangles. Every triangle whose circumcircle encloses the new point is marked as invalid and excised from the triangulation, forming an empty star-shaped polygonal cavity. The algorithm then connects the newly inserted point to every exterior boundary vertex of the cavity. Finally, upon processing all data points, any triangle sharing a vertex with the initial super-triangle is discarded, yielding an exact Delaunay mesh.