DRAFT

TODO reimplement delaunator’s demo on this page

Delaunator

Delaunator is a fast library for Delaunay triangulation. It takes as input a set of points:

and produces as output a triangulation:

The triangulation is represented as compact arrays of integers. It’s less convenient than other representations but is the reason the library is fast.

Delaunay triangles

After constructing a delaunay = Delaunator.from(points) object, it will have a triangles array and a halfedges array, both indexed by half-edge id. What’s a half-edge?

A triangle edge may be shared with another triangle. Instead of thinking about each edge A↔︎B, we will use two half-edges A→B and B→A. Having two half-edges is the key to everything this library provides.

Half-edges e are the indices into both of delaunator’s outputs:

• delaunay.triangles[e] returns the point id where the half-edge starts
• delaunay.halfedges[e] returns the opposite half-edge in the adjacent triangle, or -1 if there is no adjacent triangle

Triangle ids and half-edge ids are related.

• The half-edges of triangle t are 3*t, 3*t + 1, and 3*t + 2.
• The triangle of half-edge id e is floor(e/3).

Let’s use some helper functions for these:

It will also be useful to have some helper functions to go from one half-edge to the next and previous half-edges in the same triangle:

Note: the sample code on this page is written for readability, not performance.

Delaunay edges

We can draw all the triangle edges without constructing the triangles themselves. Each edge is two half-edges. A half-edge e starts at points[delaunay.triangles[e]]. Its opposite delaunay.halfedges[e] starts at the other end, so that tells us the two endpoints of the edge. However, the half-edges along the convex hull won’t have an opposite, so delaunay.halfedges[e] will be -1, and points[delaunay.halfedges[e]] will fail. To reliably find the other end of the edge, we need to instead use points[nextHalfedge(e)]. We can loop through the half-edges and pick half of them to draw:

Constructing triangles

A triangle is formed from three consecutive half-edges, 3*t, 3*t + 1, 3*t + 2. Each half-edge e starts at points[e], so we can connect those three points into a triangle.

Adjacent triangles

We can also use the half-edges of a triangle to find the adjacent triangles. Each half-edge's opposite will be in an adjacent triangle, and the edgeIdToTriangleId helper function will tell us which triangle a half-edge is in:

Voronoi cells

A Voronoi diagram is built by connecting the Delaunay triangle circumcenters together using the dual of the Delaunay graph.

Triangle circumcenters

The formula for circumcenters can be found on Wikipedia. The circumcenter is often but not always inside the triangle.

This convenience function will go from triangle id to circumcenter:

Voronoi edges

With the circumcenters we can draw the Voronoi edges without constructing the polygons. Each Delaunay triangle half-edge corresponds to one Voronoi polygon half-edge. The Delaunay half-edge connects two points, delaunay.triangles[e] and delaunay.triangles[nextHalfedge(e)]. The Voronoi half-edge connects the circumcenters of two triangles, edgeIdToTriangleId(e) and edgeIdToTriangleId(delaunay.halfedges[e]). We can iterate over the half-edges and construct the line segments:

Constructing Voronoi cells

To build the polygons, we need to find the triangles touching a point. The half-edge structures can give us what we need. Let’s assume we have a starting half-edge that leads into the point. We can alternate two steps to loop around:

1. Use nextHalfedge(e) to go to the next outgoing half-edge in the current triangle
2. Use halfedges[e] to go to the incoming half-edge in the adjacent triangle

Drawing Voronoi cells

To draw the Voronoi cells, we can turn a point’s incoming half-edges into triangles, and then find their circumcenters. We can iterate over half-edges, but since many half-edges lead to a point, we need to keep track of which points have already been visited.

Convex hull

There’s a problem with the cellEdgeIds loop above. Points on the convex hull won’t be completely surrounded by triangles, and the loop will stop partway through, when it hits -1. There are three approaches to this:

1. Ignore it. Make sure never to circulate around points on the convex hull.
2. Change the code.
   • Check for -1 in all code that looks at halfedges.
   • Change the cellEdgeIds loop to start at the “leftmost” half-edge so that by the time it reaches -1, it has gone through all the triangles.
3. Change the data. Remove the convex hull by wrapping the mesh around the “back”. There will no longer be any -1 halfedges.
   • Add “ghost” half-edges that pair up with the ones that point to -1.
   • Add a single ghost point at “infinity” that represents the “back side” of the triangulation.
   • Add ghost triangles to connect these ghost half-edges to the ghost point.

Here’s an example of how to find the “leftmost” half-edge:

However, even with these changes, constructing the Voronoi cell along the convex hull requires projecting the edges outwards and clipping them. The Delaunator library doesn’t provide this functionality; consider using d3-delaunay if you need it.

About this page

The code shown on this page is also running on the page, to produce the diagrams. By default the <script> tags on the page are hidden, but on this page they are made visible with CSS: script { display: block }.