@three-roads/cdt

Pure TypeScript/JavaScript constrained Delaunay triangulation for world-authoring topology.

The package is designed for editor inputs: road strokes, parcel boundaries, spline-flattened polygons, holes, T-junctions, overlapping collinear constraints, and crossing PSLG edits that need to be noded before triangulation.

What is included

• Runtime dependency-free TypeScript/JavaScript. No native addon, no WASM required.
• Fast advancing-hull Delaunay backend adapted from the ISC-licensed Delaunator algorithm, vendored as TypeScript and wired to this package's coordinate-form adaptive predicates.
• Exact-sign robust orientation and incircle predicates for finite IEEE-754 double coordinates, with BigInt exact fallback only inside the predicate implementation.
• Planar graph noding before triangulation:
  • exact duplicate merge;
  • optional editor snap tolerance;
  • T-junction splitting;
  • proper segment intersection splitting;
  • collinear overlap splitting into atomic edges.
• Constraint edge recovery by flips.
• Constrained Delaunay legalization while preserving recovered constraints.
• Polygon region filtering with holes.
• Tests for API normalization, degenerates, holes, crossing constraints, overlapping constraints, radial hubs, grid PSLGs, deterministic fuzzing, and local Delaunay validity.

Install from source

bun install
bun test
bun run coverage
bun run bench

Basic usage

import { triangulateCDT } from '@three-roads/cdt';

const mesh = triangulateCDT({
  points: [
    { x: 0, y: 0 },
    { x: 1, y: 0 },
    { x: 1, y: 1 },
    { x: 0, y: 1 },
  ],
  polygons: [{ outer: [0, 1, 2, 3], region: 10 }],
}, {
  validate: true,
});

console.log(mesh.points);
console.log(mesh.triangles);       // flat [a,b,c, ...], triangles are CCW
console.log(mesh.constraints);     // flat [a,b, ...]
console.log(mesh.triangleRegions); // one region id per triangle

API

triangulateCDT(input: CDTInput, options?: CDTOptions): CDTResult

CDTInput

type CDTInput = {
  points: Point2[] | number[] | Float64Array;
  edges?: [number, number][] | number[] | Uint32Array;
  polygons?: Polygon2[];
};

points can be an array of {x, y} objects or a flat x/y array:

triangulateCDT({ points: new Float64Array([0, 0, 1, 0, 1, 1, 0, 1]) });

edges are constraint edges into the original point array. Polygon boundaries are automatically added as constraints, so you do not need to duplicate them in edges.

triangulateCDT({
  points,
  edges: [[roadA, roadB], [riverA, riverB]],
  polygons: [{ outer: cityBoundary, holes: [lakeRing], region: 42 }],
});

CDTOptions

type CDTOptions = {
  snapTolerance?: number;
  keepExterior?: boolean;
  validate?: boolean;
  maxConstraintFlips?: number;
  maxLegalizeSteps?: number;
};

validate: true runs expensive mesh consistency checks and is intended for development and CI. For interactive editor dragging, leave it off and validate committed topology changes.

snapTolerance intentionally quantizes vertices before topology processing. Use it for editor UX, not as a numerical band-aid.

CDTResult

type CDTResult = {
  points: readonly Point2[];
  triangles: readonly number[];
  constraints: readonly number[];
  triangleRegions: readonly number[];
  pointSources: readonly (readonly number[])[];
  constraintSources: readonly (readonly number[])[];
  stats: CDTStats;
};

pointSources[i] tells you which original input vertices collapsed into output point i. New split/intersection points have an empty source array.

constraintSources[i] tracks the original edge or polygon-boundary source ids that produced each output atomic constraint edge.

Benchmarks from this container

bun run bench performs warmups and reports min, median, and p95 over multiple samples.

unconstrained-1000: median 2.784 ms, p95 3.812 ms
unconstrained-5000: median 15.832 ms, p95 22.030 ms
pslg-grid-5x5:      median 6.453 ms, p95 7.931 ms
pslg-grid-7x7:      median 15.497 ms, p95 17.300 ms

Known engineering boundary

This is a serious JS topology kernel, but it is not a certified replacement for full in-tree CDT or a CAD kernel. The fastest path is the unconstrained Delaunay backend. Constraint recovery is still flip-based, so extremely degenerate constraint schedules with many coincident crossing lines through the exact same non-input point should be handled carefully by the authoring layer or converted into explicit hub vertices before triangulation.

Scripts

bun run build      # compile TypeScript to dist/
bun test           # build and run Node test suite
bun run coverage   # build and run Node test coverage
bun run bench      # warmed benchmark suite