How it works
// 01 DPI and pixel density
The state is an array of triangles, each storing three point indices and a precomputed circumcircle (center and radius squared). On init, the canvas seeds a super-triangle large enough to contain every future point. When a new point is added, the algorithm scans every triangle, tests whether the new point falls inside its circumcircle (a simple distance-squared comparison), and flags the triangles that do. Those are the "bad triangles."
// 02 Bleed and cut tolerance
The union of bad triangles forms a polygonal hole. The edges of the hole are the edges that appear in exactly one bad triangle (boundary edges, the interior edges appear in two bad triangles and cancel out). The algorithm walks the bad triangles, collects their edges, removes any edge that shows up twice, and uses the remaining edges to build new triangles by fanning them out to the new point.
// 03 Safe zone and trim accuracy
After every insertion, any triangle still attached to the original super-triangle vertices is discarded so the mesh only contains triangles between user points. Rendering draws each triangle as three connected line segments with a semi-transparent fill. Color per triangle is derived from the triangle's centroid position hashed into a palette entry, which gives the mesh a stable, map-like look as it grows.
// why this exists
generative graphics
Delaunay triangulation is the kind of algorithm that sounds like academic geometry until you see a single useful diagram. Given a set of points, draw the triangles that connect them such that no point falls inside any triangle's circumscribed circle. The result is a mesh where triangles are as close to equilateral as the points allow. That property is what makes Delaunay the right choice for terrain meshes, pathfinding, nearest-neighbor lookups, and most visual tessellation effects.
This widget lets you tap anywhere on the canvas to drop a seed point. Every tap triggers an incremental re-triangulation, so the mesh reshapes in real time as you build your own point set. The canvas starts with a small random seed so you can see the structure before you start adding to it. Clear it and draw your own. The mesh does not care whether your points are uniform, clustered, or deliberately ugly. It will find the optimal triangulation either way.
Under the hood the widget uses a standard Bowyer-Watson implementation. Every time a new point is added, the algorithm finds all triangles whose circumscribed circle contains the new point, removes them, and retriangulates the resulting polygonal hole by fanning new triangles out to the new point. That is the entire algorithm. It is about 150 lines of JavaScript and it runs in real time up to a few thousand points before you notice the frame rate sag.
Delaunay matters because its dual graph is the Voronoi diagram, the other half of computational geometry's most useful pair. Voronoi divides a plane into regions where each region contains the points closest to a specific seed. If you have ever looked at a map showing which cell tower serves which neighborhood, you have looked at a Voronoi diagram. Delaunay and Voronoi are mathematical complements. Build one and you get the other by connecting the circumcenters of adjacent triangles.
The widget is not trying to be a CAD tool. It is a fast demonstration of an algorithm that shows up in surprising places once you know its name. Tap to seed, long-press to remove, double-tap to clear.
Frequently asked questions
What is Delaunay triangulation in plain English?
Given a set of points, connect them into triangles so that no point falls inside any other triangle's circumscribed circle. The resulting mesh has triangles as close to equilateral as possible, which is why it shows up everywhere in computational geometry.
What is the difference between Voronoi and Delaunay?
Delaunay is a triangulation of points. Voronoi is a partition of the plane into regions closest to each point. They are geometric duals. Connect the circumcenters of adjacent Delaunay triangles and you get the Voronoi diagram.
Why is Delaunay used for terrain meshes?
Its near-equilateral triangles give the best possible approximation of a smooth surface for a given point set. Long skinny triangles produce visible artifacts; Delaunay minimizes those.
What algorithm is this using?
Bowyer-Watson. It inserts points one at a time, finds all triangles whose circumcircle contains the new point, removes them, and retriangulates the hole by fanning to the new point.
How fast is Delaunay triangulation?
The incremental Bowyer-Watson approach is O(n log n) on average with good point distributions, O(n^2) worst case. For a few thousand interactive points, it runs in real time.
Can I export the mesh?
Not directly from the widget, though the triangle array is exposed in the console as `__delaunay` for inspection. A proper JSON export is a small addition.
Why does the mesh look different from a random triangle fill?
Random triangles produce long skinny shapes that crowd unevenly. Delaunay maximizes the minimum angle across the mesh, which makes the triangles look like they were drawn on purpose.
What is a circumscribed circle?
The unique circle that passes through all three vertices of a triangle. Its center is the triangle's circumcenter. The Delaunay property says no point can be inside any triangle's circumcircle.
Is this related to low-poly art?
Yes. Most low-poly generators use Delaunay under the hood because it produces meshes that look structural and intentional rather than chaotic.