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.
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 + 1, and
3*t + 2.
- The triangle of half-edge id e is
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.
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:
A triangle is formed from three consecutive half-edges,
3*t + 1,
3*t + 2. Each half-edge e starts at
points[e], so we can connect those three points into a triangle.
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:
A Voronoi diagram is built by connecting the Delaunay triangle circumcenters together using the dual of the Delaunay graph.
- Calculate the circumcenters of each triangle
- Construct the Voronoi edges from two circumcenters
- Connect the edges into Voronoi cells
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:
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[nextHalfedge(e)]. The Voronoi half-edge connects the circumcenters of two triangles,
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:
nextHalfedge(e)to go to the next outgoing half-edge in the current triangle
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.
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:
- Ignore it. Make sure never to circulate around points on the convex hull.
- Change the code.
- Check for -1 in all code that looks at
- Change the
edgesAroundPointloop to start at the “leftmost” half-edge so that by the time it reaches -1, it has gone through all the triangles.
- Check for -1 in all code that looks at
- Change the data. Remove the convex hull by wrapping the mesh around the “back”. There will no longer be any -1
- 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.
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:
- edge → edges:
- edge → points:
- edge → triangle:
- triangle → edges:
- triangle → points:
- triangle → triangles:
- point → incoming edges:
- point → outgoing edges:
- point → points:
- point → triangles: