Fast and Exact Constrained Delaunay Triangulation in JavaScript

A constrained Delaunay triangulation (CDT) triangulates a set of 2D points and keeps chosen edges in the output. Those edges can be an outline, the rim of a hole, or a feature line. trueform does it with tf.cdt. Constraint edges may cross each other; the crossings are split for you. It works in JavaScript and TypeScript with one npm install, WebAssembly-powered, in Node.js and the browser with the same API. Typed arrays in, typed arrays out. This tutorial covers plain Delaunay, outlines with holes, crossing constraints and index maps, then shows measured times against Delaunator and cdt2d.

Install

npm install @polydera/trueform

The package ships TypeScript types. The WebAssembly binary loads on first use. In the browser, multithreading needs SharedArrayBuffer headers; see the installation guide.

Loading the points

tf.cdt takes an [N, 2] point array and, optionally, an [E, 2] int32 array of constraint edges that index into it. No mesh object is needed.

import * as tf from "@polydera/trueform";

const n = 1000;
const raw = new Float32Array(2 * n);
for (let i = 0; i < raw.length; i++) raw[i] = Math.random() * 2 - 1;

const points = tf.ndarray(raw, [n, 2]);

If your points come from a 3D file, read it with tf.readStl or tf.readObj and project to two coordinates first.

Delaunay triangulation

Without edges you get the Delaunay triangulation of the convex hull:

const { faces, points: outPoints } = tf.cdt(points);
// faces:     NDArrayInt32   [K, 3]
// outPoints: NDArrayFloat32 [1000, 2]

The faces index outPoints, not your input array. The output order can differ from the input order. To map between them, use returnIndexMap: true (below).

An outline with a hole

Pass the outline and the hole as constraint edges. Every constraint edge is a wall by default. Triangles inside an odd number of walls are kept, so a ring of walls inside another ring is a hole.

const nSteiner = 500;
const ring = new Float32Array(2 * (8 + nSteiner));
ring.set([
  -1, -1,  1, -1,  1, 1,  -1, 1,              // outer square
  -0.4, -0.4,  0.4, -0.4,  0.4, 0.4,  -0.4, 0.4, // inner square
]);
for (let i = 16; i < ring.length; i++) ring[i] = Math.random() * 2 - 1;
const ringPoints = tf.ndarray(ring, [8 + nSteiner, 2]);

const ringEdges = tf.ndarray(new Int32Array([
  0, 1,  1, 2,  2, 3,  3, 0,   // outer square
  4, 5,  5, 6,  6, 7,  7, 4,   // inner square: the hole
]), [8, 2]);

const { faces, points: outPoints } = tf.cdt(ringPoints, { edges: ringEdges });

The interior points inside the hole are dropped. The triangles cover 3.36, the square's 4 minus the hole's 0.64.

Crossing constraints and feature lines

Constraints may cross. The crossing point is added to the output:

const outer = tf.ndarray(new Float32Array([-1, -1,  1, -1,  1, 1,  -1, 1]), [4, 2]);
const diagonals = tf.ndarray(new Int32Array([0, 2,  1, 3]), [2, 2]);

const crossed = tf.cdt(outer, { edges: diagonals });
crossed.points.shape;   // [5, 2]: the four corners and the crossing at (0, 0)

To keep a constraint as an edge without making it a wall, pass an edgeMask. 1 marks a wall, 0 a feature line that splits nothing:

const edges = tf.ndarray(new Int32Array([
  0, 1,  1, 2,  2, 3,  3, 0,   // outline: walls
  0, 2,  1, 3,                 // diagonals: feature lines
]), [6, 2]);
const edgeMask = tf.ndarray(new Int8Array([1, 1, 1, 1, 0, 0]), [6]).as("bool");

const quarters = tf.cdt(outer, { edges, edgeMask });
quarters.faces.shape;   // [4, 3]: four quarter triangles, the square stays solid

If crossings are not allowed in your data, pass splitConstraints: false. The call then returns an empty result on the first crossing. The empty result is the answer to "do these constraints cross", not an error.

const verbatim = tf.cdt(outer, { edges: diagonals, splitConstraints: false });
verbatim.faces.shape[0] > 0;   // false: the diagonals cross

Working with results

faces is [K, 3] int32 and points is [M, 2] in the input dtype. Pass Float64Array points for float64 output.

To trace input points through the triangulation, ask for the index map:

const { faces, points: outPoints, indexMap } =
  tf.cdt(ringPoints, { edges: ringEdges, returnIndexMap: true });

const { f, keptIds } = indexMap;
const sentinel = f.length;
const dropped = f.eq(sentinel);         // input points that fell outside the kept region
const created = keptIds.eq(sentinel);   // output points made at constraint crossings

f[i] is the output index of input point i. keptIds[k] is the input index of output point k.

To lift a 2D triangulation into 3D, add a third coordinate and wrap it as a mesh. The triangles come out clockwise in the plane, so their normals point down -z. Reverse the winding if you want them up:

const m = outPoints.shape[0], src = outPoints.data;
const p3 = new Float32Array(3 * m);
for (let i = 0; i < m; i++) {
  p3[3 * i] = src[2 * i];
  p3[3 * i + 1] = src[2 * i + 1];
}

const mesh = tf.reverseWinding(tf.mesh(faces, tf.ndarray(p3, [m, 3])));
const objBytes = tf.writeObj(mesh).data;   // write to disk or wrap in a Blob

For large inputs, run it off the main thread:

const result = await tf.async.cdt(ringPoints, { edges: ringEdges });

The same CDT triangulates the cut surfaces in mesh booleans.

Related tutorials

• Fast and Robust Mesh Slicing and Cross-Sections in JavaScript — plane sections, layers and slabs of a mesh.
• Fast Mesh Booleans in JavaScript — exact union, intersection and difference of two meshes.
• Fast and Robust Isocontours on a Triangle Mesh in JavaScript — curves and bands of equal value on a scalar field.
• Fast STL and OBJ Reading in JavaScript — load and write meshes, the first step of every pipeline.

Performance

Unconstrained Delaunay triangulation of 1M random points. Delaunator computes unconstrained Delaunay only.

Apple M4 Max 16 threads Node.js WebAssembly

For constrained input, the benchmark triangulates a wiggly closed contour. trueform takes 45.8 ms on a 100,000-vertex contour. cdt2d, the constrained triangulator we compared against, was measured only up to 10,000 vertices.

Median of three fresh-process medians. Benchmark run with trueform npm 0.10.2, Delaunator 5.1.0 and cdt2d 1.0.0.

Full benchmarks · Documentation

@article{polydera:constrained-delaunay-triangulation-in-javascript,
  title={Fast and Exact Constrained Delaunay Triangulation in JavaScript},
  author={Sajovic, {\v{Z}}iga, Polydera},
  year={2026},
  url={https://polydera.com/tutorials/constrained-delaunay-triangulation-in-javascript},
  organization={Polydera}
}