Delaunator guide

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:

Triangle ids and half-edge ids are related.

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.

  1. Calculate the circumcenters of each triangle
  2. Construct the Voronoi edges from two circumcenters
  3. Connect the edges into Voronoi cells

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, triangleOfEdge(e) and triangleOfEdge(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

Note that this requires any incoming half-edge that leads to the point. If you need a quick way to find such a half-edge given a point, it can be useful to build an index of these half-edges. For an example, see the modified version of forEachVoronoiCell at the end of the page.

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 edgesAroundPoint 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 edgesAroundPoint 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.

Summary

The Delaunator library uses half-edges to represent the relationships between points and triangles. On this page are sample functions showing how to move between types of objects: