How to Create Voronoi Diagrams and Delaunay Triangulation with d3-delaunay

d3-delaunay provides fast O(n log n) Delaunay triangulation and Voronoi diagram generation through the Delaunay and Voronoi classes, exposing methods like Delaunay.from(), delaunay.voronoi(), and voronoi.cellPolygons() for building and rendering spatial meshes.

The d3-delaunay module is the standard computational geometry library for the D3 ecosystem, offering a thin, ergonomic wrapper around the Delaunator algorithm. Whether you need to create Voronoi diagrams and Delaunay triangulation with d3-delaunay for interactive data visualization, spatial analysis, or generative art, this library provides efficient indexed structures for nearest-neighbor queries and polygonal mesh generation directly in the browser or Node.js.

Core Architecture and Classes

According to the d3/d3-delaunay source code, the library exposes two primary constructs that work in tandem:

• Delaunay (defined in src/delaunay.js): Stores the triangulation topology for a set of 2-D points using compact typed arrays (points, triangles, halfedges). It provides the geometric foundation and methods to navigate the mesh.
• Voronoi (defined in src/voronoi.js): Represents the dual graph of the Delaunay triangulation, partitioning the plane into cells where each cell contains all points closer to one input point than any other.

The Delaunay class computes the initial planar triangulation, while the Voronoi class derives cell boundaries from the circumcenters of adjacent Delaunay triangles. This design allows you to reuse the same triangulation data for both structures, minimizing memory overhead and computation time.

Creating a Delaunay Triangulation

To initialize a triangulation, use the static Delaunay.from() method, which accepts any iterable of points and optional accessor functions for extracting coordinates.

import { Delaunay } from "d3-delaunay";

// Array of [x, y] coordinates
const points = [[10, 20], [30, 40], [50, 60], [70, 80]];
const delaunay = Delaunay.from(points);

For raw performance, you can also pass a flat Float64Array directly to the constructor:

const coords = new Float64Array([10, 20, 30, 40, 50, 60]);
const delaunay = new Delaunay(coords);

The resulting object exposes three key index arrays defined in src/delaunay.js:

• delaunay.triangles: Uint32Array where each triple of indices defines one triangle.
• delaunay.halfedges: Int32Array encoding the opposite half-edge for each edge, enabling mesh traversal.
• delaunay.hull: Uint32Array of indices forming the convex hull in counterclockwise order.

Navigating the Triangulation

Once constructed, the Delaunay mesh supports efficient spatial queries. The half-edge structure allows you to walk neighboring triangles without recomputing geometry.

Find the nearest point to any coordinate using delaunay.find(), which implements a walk across the Delaunay graph with O(log n) average query time:

const index = delaunay.find(25, 35); // Returns index of closest input point
const [x, y] = [delaunay.points[index * 2], delaunay.points[index * 2 + 1]];

Iterate over neighbors of a specific point using delaunay.neighbors(i), which returns a generator of adjacent point indices:

for (const neighborIndex of delaunay.neighbors(0)) {
  console.log(`Point 0 is connected to point ${neighborIndex}`);
}

Generating Voronoi Diagrams

To create Voronoi diagrams and Delaunay triangulation with d3-delaunay in a single workflow, call delaunay.voronoi() with a bounding box array [xmin, ymin, xmax, ymax]. This instantiates the Voronoi class defined in src/voronoi.js, computing cell polygons as the dual of the existing triangulation.

const bounds = [0, 0, 640, 480];
const voronoi = delaunay.voronoi(bounds);

The Voronoi object provides several critical methods for working with the diagram:

• voronoi.cellPolygons(): Returns an iterable of polygon arrays, one per input point, suitable for rendering as SVG paths or Canvas polygons.
• voronoi.contains(i, x, y): Tests whether a point lies within a specific cell.
• voronoi.neighbors(i): Returns adjacent cell indices (always a subset of Delaunay neighbors).

Rendering and Visualization

Both classes expose Canvas-2D rendering helpers that accept any context-compatible object. In src/delaunay.js, the delaunay.render(context) method draws every edge of the triangulation:

const canvas = document.getElementById("canvas");
const ctx = canvas.getContext("2d");
delaunay.render(ctx); // Strokes the entire mesh

For Voronoi cells, defined in src/voronoi.js, you can render individual cells or the complete diagram:

// Render all cells
voronoi.render(ctx);

// Render specific cell
voronoi.renderCell(5, ctx);

// Render bounding box
voronoi.renderBounds(ctx);

When no context is provided, these methods return SVG path strings, making it trivial to integrate with D3 selections:

svg.selectAll("path")
  .data(voronoi.cellPolygons())
  .join("path")
  .attr("d", d => "M" + d.join("L") + "Z");

Complete Workflow Example

This self-contained example demonstrates building a colored Voronoi tessellation from random points:

import * as d3 from "d3";
import { Delaunay } from "d3-delaunay";

const width = 640;
const height = 480;
const points = d3.range(100).map(() => [Math.random() * width, Math.random() * height]);

const delaunay = Delaunay.from(points);
const voronoi = delaunay.voronoi([0, 0, width, height]);

const svg = d3.select("svg");
const color = d3.scaleSequential(d3.interpolateRainbow).domain([0, 100]);

svg.selectAll("path")
  .data(voronoi.cellPolygons())
  .join("path")
  .attr("d", d => "M" + d.join("L") + "Z")
  .attr("fill", (_, i) => color(i))
  .attr("stroke", "#333");

Summary

• d3-delaunay wraps the Delaunator library to provide O(n log n) Delaunay triangulation via the Delaunay class in src/delaunay.js.
• Construct triangulations using Delaunay.from() for iterables or new Delaunay() for raw Float64Array coordinates.
• Navigate the mesh using delaunay.find() for nearest-point queries and delaunay.neighbors() for adjacency lists.
• Generate Voronoi diagrams by calling delaunay.voronoi([xmin, ymin, xmax, ymax]), which returns a Voronoi instance from src/voronoi.js.
• Access cell geometry through voronoi.cellPolygons() and render to Canvas or SVG using render(), renderCell(), or path string generation.

Frequently Asked Questions

What is the difference between the Delaunay and Voronoi classes in d3-delaunay?

The Delaunay class represents the triangulation mesh connecting input points into triangles, while the Voronoi class represents the dual graph where each cell contains all points closest to one input site. As implemented in src/delaunay.js and src/voronoi.js, you must first create a Delaunay instance and then call delaunay.voronoi() to generate the Voronoi diagram, as the latter reuses the triangulation topology to compute cell boundaries from triangle circumcenters.

How do I find the nearest point to a specific coordinate using d3-delaunay?

Use the delaunay.find(x, y, i?) method defined in src/delaunay.js, which performs a walk across the Delaunay graph starting from an optional initial guess index i. This algorithm runs in O(log n) average time and returns the index of the input point closest to the query coordinates, allowing you to build interactive hover effects or spatial lookups efficiently.

Can I render Voronoi diagrams to SVG instead of Canvas?

Yes. Both Delaunay and Voronoi classes support SVG generation by omitting the context argument in their render methods. According to the source in src/voronoi.js, calling voronoi.render() without arguments returns an SVG path string, while voronoi.cellPolygons() provides raw coordinate arrays that you can format into <path d="M...Z"> elements using D3 or vanilla JavaScript.

What is the time complexity for creating a Voronoi diagram with d3-delaunay?

Creating the initial Delaunay triangulation requires O(n log n) time, where n is the number of input points. Generating the Voronoi diagram via delaunay.voronoi() adds O(n) overhead for computing circumcenters and clipping cells to the bounding box. The half-edge data structure stored in delaunay.halfedges ensures that subsequent neighbor queries and point location operations remain efficient for interactive applications.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}