How to low poly and delaunay triangulation: the algorithm explained
- Step 1Collect the point set — Start with eight fixed anchors (corners at 0,0 / W,0 / 0,H / W,H and edge midpoints at W/2,0 / 0,H/2 / W,H/2 / W/2,H) plus N random interior points. The anchors guarantee the mesh reaches every border.
- Step 2Build a super-triangle — Compute the bounding box of all points, then build one enormous triangle (offset by ten times the larger box dimension) that contains every point. The algorithm seeds its triangle list with this single super-triangle.
- Step 3Insert each point — For each point in turn, find every existing triangle whose circumcircle contains that point. These are the 'bad' triangles whose Delaunay condition the new point violates.
- Step 4Carve the hole — Collect the three edges of each bad triangle. Drop any edge shared by two bad triangles; what remains is the boundary polygon of the hole. Remove all bad triangles from the list.
- Step 5Re-fan to the new point — Connect every boundary edge of the hole to the newly inserted point, creating a fan of new triangles. The mesh is again a valid Delaunay triangulation of all points inserted so far.
- Step 6Remove the scaffold and colour — After all points are inserted, discard every triangle that still references a super-triangle vertex. Then colour each surviving triangle by mapping its centroid's X position into the four-colour palette.
Bowyer-Watson as implemented in the generator
The exact data flow in the code. The super-triangle's vertices are stored after the real points; the final filter keeps only triangles whose three indices are all below the super-triangle's first index.
| Stage | What the code does | Result |
|---|---|---|
| Bounding box | Scan all points for min/max X and Y | Box used to size the super-triangle |
| Super-triangle | Build one triangle offset by 10× the larger box side | A triangle containing every point |
| Per-point insert | circumcircle determinant > 0 → 'bad' | Set of triangles to remove |
| Hole boundary | Keep edges that appear in exactly one bad triangle | Polygon outline of the cavity |
| Re-fan | Link each boundary edge to the new point | New triangles restoring the mesh |
| Cleanup | Drop triangles touching a super-vertex | Final mesh of real points only |
The circumcircle predicate (the in-circle test)
The code tests whether point p lies inside the circumcircle of triangle (a,b,c) using a signed determinant of points translated so p is the origin. A positive determinant means 'inside' for this winding. It is a fast, non-robust predicate — fine for low-poly art, not for adversarial inputs.
| Quantity | Expression in the code | Meaning |
|---|---|---|
| Translated a | (a.x − p.x, a.y − p.y) | Vertex relative to the query point |
| Determinant | (|a|²)(bx·cy − cx·by) − (|b|²)(ax·cy − cx·ay) + (|c|²)(ax·by − bx·ay) | Signed in-circle measure |
| det > 0 | returns true | p is inside the circumcircle → triangle is 'bad' |
| det ≤ 0 | returns false | p is on or outside the circle → triangle kept |
Cookbook
The algorithm in plain pseudocode that mirrors the implementation, then how it decides each triangle's colour.
Bowyer-Watson in pseudocode
This mirrors the generator's loop exactly: super-triangle, per-point bad set, shared-edge removal, re-fan, super-vertex cleanup.
function triangulate(points):
super = bigTriangleAround(boundingBox(points))
tris = [super]
for p in points:
bad = [t for t in tris if inCircumcircle(p, t)]
boundary = []
for t in bad:
for edge in t.edges(): # 3 edges each
if edge appears in exactly one bad triangle:
boundary.add(edge)
tris.removeAll(bad)
for edge in boundary:
tris.add(triangle(edge.a, edge.b, p))
return [t for t in tris if not t.touches(super)]The in-circle determinant
Translate a, b, c so the query point p is the origin, then take the signed determinant. Positive means p is inside the circumcircle.
function inCircumcircle(p, a, b, c):
ax = a.x - p.x; ay = a.y - p.y
bx = b.x - p.x; by = b.y - p.y
cx = c.x - p.x; cy = c.y - p.y
det = (ax*ax + ay*ay) * (bx*cy - cx*by)
- (bx*bx + by*by) * (ax*cy - cx*ay)
+ (cx*cx + cy*cy) * (ax*by - bx*ay)
return det > 0 # inside -> this triangle is 'bad'How a triangle gets its colour
Each triangle's centroid X is normalised to 0..1, scaled by the palette length, and the integer part picks the band. The browser tool then blends toward the next colour; the server engine uses the band colour flat.
cx = (a.x + b.x + c.x) / 3 t = clamp(cx / W, 0, 0.9999) idx = floor(t * paletteLength) # which band # browser: smooth blend toward the next swatch localT = t * paletteLength - idx fill = mix(palette[idx], palette[(idx+1) % n], localT) # server/API: flat band colour fill = palette[idx]
Anchors guarantee coverage
The eight fixed anchors are inserted alongside the random points, so the convex hull of the point set is always the full rectangle and the mesh reaches every corner and edge.
anchors = [ (0,0), (W/2,0), (W,0), (0,H/2), (W,H/2), (0,H), (W/2,H), (W,H) ] points = anchors + [randomPoint() for i in 1..N]
Delaunay vs a naive fan (why it matters)
A naive triangulation can leave long thin slivers; Delaunay's empty-circumcircle property maximises the minimum angle, giving rounder triangles. Conceptual contrast.
Naive fan from one point: /|\ /|\ <- thin slivers, ugly Delaunay (empty circles): /\/\/\/\ <- balanced facets Guarantee: no point lies inside any triangle's circumcircle => the 'fattest possible' triangulation.
Edge cases and what actually happens
Fewer than three points
Returns emptyThe triangulation function returns an empty triangle list if given fewer than three points. In practice this never happens here: the eight fixed anchors are always present before any interior points are added.
Two interior points land on top of each other
ToleratedRandom duplicates are vanishingly unlikely with floating-point coordinates, but if it happened the second insertion would simply find no bad triangle to carve and add no useful geometry. The mesh stays valid.
A point lies exactly on a circumcircle (det == 0)
ExcludedThe predicate uses a strict det > 0, so an exactly-cocircular point is treated as outside. This is a deliberate degeneracy choice; with random floats it almost never occurs and has no visible effect.
Super-triangle too small for outliers
GuardedThe super-triangle is offset by ten times the larger bounding-box dimension, comfortably enclosing every interior point and anchor. There is no path by which a real point falls outside it.
Non-robust predicate on pathological inputs
AcceptableThe in-circle test is a plain determinant, not an exact/adaptive predicate, so adversarial point layouts could in theory produce a degenerate mesh. For random low-poly art at a few hundred points this never bites — the code comments call it good-enough for ≤ ~500 points.
Performance at the 300-point maximum
ExpectedInsertion scans all current triangles for each point, so the cost grows roughly quadratically. At the 300-point cap (~600 triangles) it still completes in milliseconds in the browser; the 300 ceiling keeps it comfortably fast.
Colour bands look striped, not blended
By designOnly the browser tool blends between swatches per triangle. The server/runner engine paints each triangle its flat band colour with fixed opacity, so the same settings can look smoother in-tab than via the API. Both are correct outputs of the same algorithm.
You expected Voronoi cells, not triangles
Not supportedThe tool emits the Delaunay triangulation directly. Voronoi is its dual — you could derive cell boundaries from triangle circumcentres — but the generator does not output Voronoi polygons.
Frequently asked questions
What is Delaunay triangulation in one sentence?
It is the triangulation of a point set in which no point lies inside any triangle's circumcircle, which equivalently maximises the minimum interior angle — giving the 'fattest', least-sliver-prone set of triangles.
Which algorithm does the generator use?
Bowyer-Watson incremental insertion: start with a super-triangle, insert points one at a time, delete triangles whose circumcircle contains the new point, then re-fan the resulting hole to that point. At the end it removes triangles touching the super-triangle.
How does it test whether a point is 'in the circle'?
With a signed 3×3 determinant of the triangle's vertices translated so the query point is the origin. If that determinant is greater than zero, the point is inside the circumcircle and the triangle is marked for removal.
Is the predicate numerically robust?
No. It is a straightforward floating-point determinant, not an exact or adaptive predicate. That is fine for random low-poly art at a few hundred points; the code explicitly targets that regime rather than robustness against adversarial inputs.
Why does Delaunay look better than random triangulation?
Maximising the minimum angle avoids long thin slivers. The result reads as balanced, gem-like facets rather than the needles a careless triangulation produces, which is why it is the standard choice for low-poly art.
What is the relationship to Voronoi diagrams?
They are duals. Connect the seeds of adjacent Voronoi cells and you get the Delaunay triangulation; the circumcentres of Delaunay triangles are the Voronoi vertices. The generator outputs the triangulation, not the Voronoi cells.
Why are there eight extra points I didn't add?
Those are fixed anchors — four corners and four edge midpoints — inserted so the convex hull is the full rectangle and the mesh covers the whole canvas with no missing corners.
How many triangles result from N points?
For a Delaunay triangulation of P points, roughly 2P minus the hull boundary. With the eight anchors, that is about 2(N+8) − ~12 triangles, e.g. ~106 at the default 50 interior points.
Does the algorithm run on the server too?
Yes. svg-polygon-gen is in the server-safe set, so the same triangulation runs in the engine for API/runner jobs — though the engine colours triangles flat rather than blending, the geometry is identical.
Could I reproduce the exact mesh offline?
You could re-implement Bowyer-Watson with the same anchors, but you cannot match the tool's specific mesh because its interior points come from an unseeded random source. The structure would match; the exact triangles would not.
What happens to a point exactly on an edge or circle?
The strict det > 0 test treats on-circle points as outside, and on-edge cases resolve through the shared-edge removal step. With random floating-point coordinates these exact degeneracies essentially never arise.
Where can I see the algorithm produce art?
Use /svg-tools/svg-polygon-gen itself, then compare with the other generators — /svg-tools/svg-blob-generator and /svg-tools/svg-wave-divider — which use different geometry (Catmull-Rom-style blobs and sine waves) rather than triangulation.
Privacy first
Every JAD SVG tool runs entirely in your browser using the DOM API and Canvas. Your SVG files never leave your device — verified by zero outbound network requests during processing.