How to low poly and delaunay triangulation: the algorithm explained
- Step 1Understand the circumcircle criterion — For any triangle in a Delaunay triangulation, the circumcircle (the unique circle passing through all three vertices) contains no other point from the point set. This criterion maximizes the minimum angle in the triangulation, preventing degenerate thin triangles.
- Step 2Trace the algorithm — The Bowyer-Watson algorithm: start with a super-triangle containing all points. Insert points one by one. For each new point, find all triangles whose circumcircle contains the point (they become invalid). Remove them, creating a polygonal hole. Re-triangulate the hole with the new point as one vertex.
- Step 3Apply to low-poly art — For low-poly art, seed points are placed randomly or along image edges (using Canny edge detection or Sobel filter to find high-contrast boundaries). Denser point seeding near edges produces sharper feature definition in the low-poly output.
Frequently asked questions
What is the difference between Delaunay triangulation and Voronoi diagrams?+
They are dual graphs of each other. For a set of points, the Voronoi diagram partitions the plane into cells — each cell contains all points closer to one seed than any other. The Delaunay triangulation connects the seeds of adjacent Voronoi cells. Drawing lines between seeds of touching Voronoi cells produces the Delaunay triangulation.
Why does Delaunay produce better-looking low-poly than random triangulation?+
Random triangulation often creates very thin triangles that look artificial — needles and slivers that catch the eye. Delaunay's maximization of the minimum angle produces fat, equilateral-ish triangles that tile space more naturally, creating an organic appearance that resembles faceted gemstones or stained glass.
How does edge detection improve low-poly art quality?+
Placing seed points along image edges (detected by a Sobel or Canny filter) ensures the triangulation creates boundaries where colour transitions occur in the source image. This preserves the visual structure of the source — horizon lines, facial features, object boundaries — producing more recognizable low-poly art at lower triangle counts.
Is Delaunay triangulation expensive to compute for large point sets?+
The Bowyer-Watson algorithm runs in O(n log n) time for n points. For 1000 points (sufficient for most low-poly art), computation takes milliseconds in JavaScript. The JAD generator computes Delaunay triangulation entirely in the browser — no server round trip.
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.