GenerateRandomSearch

Delaunay Triangulation Generator

Of all the ways to triangulate a set of points, the Delaunay one avoids thin slivers — and the property that guarantees it is beautifully simple: no triangle's circumcircle may contain any other point. This uses that definition directly rather than an algorithm that implements it, testing every triple against every other point, which means the output cannot disagree with the property it claims. The trade is that the point count has to stay small.

What this generator does

Tests every triple of points and keeps those whose circumcircle contains no other point. It then reports the smallest angle anywhere in the triangulation, which is the quantity Delaunay maximises.

How to use this tool

  1. Choose how many points to triangulate.
  2. Generate, and look at the triangles drawn.
  3. Read the smallest angle — Delaunay makes it as large as it can be.
  4. Compare with what a careless triangulation would give.

Understanding the controls

How many points
Between 4 and 14. Every triple is tested against every other point, which is cubic work — fine at fourteen, not at forty.
Seed
Reproduces the same points and therefore the same triangles.

Common use cases

  • Mesh generation examples with a verified property
  • Showing why Delaunay avoids sliver triangles
  • Test data for a triangulation implementation
  • Teaching the duality with Voronoi diagrams
  • Reproducing the same triangulation from a seed

How this generator works

The circumcircle test is a determinant over the three triangle vertices and the point being tested, normalised by the triangle's orientation. Because the definition is used directly, the check is the same test run again — over every triangle and every point not in it.

Randomness and fairness

The point positions are random; which triples are Delaunay is decided by geometry. Seeded triangulations reproduce exactly and are therefore explicitly not cryptographically secure. Unseeded, the browser's cryptographically secure generator scatters the points.

For how randomness is produced across the whole site, see how Generate Random works.

Limitations and good to know

  • Fourteen points is the ceiling, because using the definition directly costs cubic time.
  • Points exactly on a common circle can give several equally valid triangulations; all of them are listed.
  • Two dimensions only — tetrahedralisation in three is a substantially harder problem.
  • No constrained edges — this is the unconstrained triangulation.
  • Triangulations are not stored between visits.

Privacy and your data

Points and triangles are computed in your browser. Nothing is transmitted or stored.

Related generators