Triangles and cells from points

Delaunay triangulation Connect the points with triangles so that the circle through the three corners of every triangle holds no other point. This avoids long thin triangles as far as the points allow. Wikipedia

Voronoi diagram Every point owns the part of the plane that is closer to it than to any other point. The borders of these cells are the dual of the Delaunay triangles: each cell corner is the circle center of one triangle. Wikipedia

Bowyer-Watson Start with one huge triangle around all points. Insert the points one by one. Remove every triangle whose circle holds the new point, then connect the new point to the border of the hole. Wikipedia

Original work

• Adrian Bowyer; David F. Watson (1981): Computing Dirichlet tessellations; Computing the n-dimensional Delaunay tessellation
• Boris Delaunay (1934): Sur la sphère vide
• Georgy Voronoy (1908): Nouvelles applications des paramètres continus à la théorie des formes quadratiques

How it works

Three far away corner points form the first triangle. Each insertion finds the triangles whose circumcircle holds the new point (the bad triangles), takes the border of their union (the cavity) and fills the cavity with new triangles. Step mode shows these three phases.

• Triangles are kept counter-clockwise and cache their circumcircle, so the test is one distance compare.
• The cavity edges are the edges of bad triangles whose opposite edge is not in a bad triangle.
• The Voronoi cell of a point is the polygon of the circle centers of its triangles. The corner points keep the outer cells closed, then the polygons are clipped to the canvas.
• Drawing uses Canvas 2D with requestAnimationFrame outside the Angular zone. A drag only marks the diagram as dirty, and each frame rebuilds it at most once.

Source code:delaunay.tsvoronoi.ts

Note Simplifications in this demo:

• The triangulation uses plain floating point numbers with a small tolerance. It is not exact for nearly degenerate input.
• The search for triangles to remove checks all triangles, so the build time grows with the square of the point count.
• A point on top of another point is skipped. Cells are clipped to the canvas, which is 1000 x 1000 world units.