tsnav

Constrained Delaunay triangulation (CDT) toolkit for TypeScript — a faithful port of rsnav's triangle crate (itself a port of Jonathan Shewchuk's triangle.c, CDT subset).

Draw arbitrary polygons (concave or convex, with holes) and triangulate them with a robust CDT, then label / rasterize the result by region. CDT is heavier than scanline fill for that job, but it is exact, handles holes and concave boundaries cleanly, and leaves a navigable mesh behind.

Quick start

npm install
npm test          # vitest — 24 parity tests
npm run dev       # serve the SPA demo (Vite) → open the printed localhost URL
npm run build     # emit the library to dist/
npm run build:demo  # bundle the SPA to dist-demo/

The demo (SPA)

npm run dev opens an interactive playground:

• Click to drop polygon vertices; double-click or Enter closes a loop.
• Tick "Next closed loop is a hole" before closing a loop to punch it out.
• Triangulate runs the full CDT pipeline; Load sample drops a concave star with a central square hole.
• Toggle Rasterize interior to overlay a grid where each cell is labeled inside/outside via BSP locate — the CDT-as-rasterizer.
• Triangles are filled by connected region (NavMesh component labelling); move the cursor to run BSP locate (triangle under the cursor, highlighted white) and, when outside the mesh, BSP nearest (closest point on the walkable surface, drawn with a dashed leader).
• The Tool switch picks Draw / Path / Visibility. In Path mode, click a start and a goal to route an A* + funnel path (the green polyline, over a faint A* triangle channel); the clearance slider keeps the route an agent radius off the walls. In Visibility mode, the cursor casts a visibility region (the yellow star-shaped polygon).

Constrained segments render in orange (the "segment labeling"); interior Delaunay edges in grey. Multiple disjoint polygons, concavities, and holes are all handled: only true polygon interiors survive carving.

Library API

import { triangulate, extractMesh, pslgVertex, pslgSegment, vertex } from "tsnav";

const pslg = {
  vertices: [vertex(0, 0), vertex(4, 0), vertex(4, 4), vertex(0, 4)].map((p) => pslgVertex(p)),
  segments: [pslgSegment(0, 1), pslgSegment(1, 2), pslgSegment(2, 3), pslgSegment(3, 0)],
  holes: [],
};

const cdt = triangulate(pslg);         // CdtMesh
const { vertices, triangles, edges } = extractMesh(cdt);
// edges[i].constrained === true for PSLG segments

From a carved CDT you can build the runtime navmesh and a spatial index:

import { buildFromCdt, Bsp } from "tsnav";

const nav = buildFromCdt(cdt);          // flat NavMesh: adjacency, edge markers,
                                        // per-triangle area/centroid, region IDs
nav.regionCount;                        // # connected walkable components
nav.regionArea(0);                      // total area of region 0
nav.randomPoint(Math.random);           // area-uniform spawn point

const bsp = Bsp.build(nav);             // BVH over the triangles
bsp.locate(nav, { x, y });              // TriangleId | null  — O(log n)
bsp.nearest(nav, { x, y });             // { triangle, point, distance } — snap to mesh
bsp.queryAabb(box, (t) => { /* ... */ }); // broad-phase box query

Pathfinding and queries over the navmesh:

import { findPath, pathClear, lineOfSight, visibilityRegion } from "tsnav";

const r = findPath(nav, bsp, start, goal, { distanceFromWall: 8 });
if (r.ok) r.points;                     // string-pulled polyline (A* + funnel)
else r.error;                           // "start-outside-mesh" | "goal-outside-mesh" | "unreachable"

pathClear(nav, bsp, [a, b, c]);         // cheap "do I need to replan?" after the mesh changes
lineOfSight(nav, bsp.locate(nav, a)!, a, b);        // { kind: "clear" | "blocked" | ... }
visibilityRegion(nav, bsp, eye, radius, 200);       // star-shaped visibility polygon

Load / save the rsnav v1 binary format (byte-for-byte compatible — bake a mesh server-side in Rust, query it in the browser):

import { navmeshFromBytes, navmeshToBytes } from "tsnav";

const nav = navmeshFromBytes(await fetch("/level.navmesh").then((r) => r.arrayBuffer()));
const bytes = navmeshToBytes(nav); // Uint8Array a Rust NavMesh::from_bytes loads

See INTEROP.md for the rsnav ↔ tsnav workflow (who builds, who loads, trimming files, versioning).

Lower-level building blocks (delaunay, formSkeleton, carveHoles, flip/unflip, the Otri/Osub half-edge handles, robust orient2d / incircle) are all exported for direct use.

Port status

Layer	rsnav crate / module	tsnav	State
Robust predicates (orient2d, incircle)	triangle/predicates.rs	src/common/predicates.ts	✅ parity-tested (BigInt oracle)
Geometry primitives	rsnav-common	src/common/{vertex,ids}.ts	✅ (subset used by CDT)
PSLG input	triangle/pslg.rs	src/triangle/pslg.ts	✅
Half-edge mesh + handles	triangle/mesh.rs	src/triangle/mesh.ts	✅
Vertex sort (Dwyer)	triangle/sort.rs	src/triangle/sort.ts	✅
Divide-and-conquer Delaunay	triangle/divconq.rs	src/triangle/divconq.ts	✅ (200-pt stress)
Edge flips	triangle/flip.rs	src/triangle/flip.ts	✅
Constraint segment insertion	triangle/segment.rs	src/triangle/segment.ts	✅
Hole carving	triangle/holes.rs	src/triangle/holes.ts	✅
Aabb + geom helpers	rsnav-common	src/common/{aabb,geom}.ts	✅
Runtime NavMesh + builder	rsnav-navmesh	src/navmesh/	✅ regions, area, boundary, sampling
BSP (BVH locate/nearest/box)	rsnav-bsp	src/bsp/	✅ parity vs brute force
A* + funnel pathfinding	rsnav-navigation	src/navigation/	✅ portal-crossing A*, clearance
Line-of-sight / path revalidation	navigation/los.rs, path.rs	src/navigation/	✅
Visibility regions	navigation/visibility.rs	src/navigation/	✅
Navmesh binary format (v1)	navmesh/binary.rs	src/navmesh/binary.ts	✅ byte-exact, cross-language tested
.poly / .node file I/O	triangle/io.rs	—	⬜ not ported
crowd / local avoidance	rsnav-crowd	—	⬜ later

Self-intersecting PSLG input (Steiner points at crossings) and quality refinement are intentionally not ported, matching rsnav's v1: a crossing raises SegmentInsertError.

Design notes

• Predicates are hand-ported, not from npm. src/common/predicates.ts mirrors rsnav's predicates.rs so we keep bit-for-bit parity. JS number is IEEE-754 binary64 and does not fuse multiply-add, so Shewchuk's error-free transforms port exactly.
• All coordinates are f64 (JS number), matching rsnav.
• The Rust Otri/Osub (Copy structs, &mut Otri) become small mutable classes: lnext/lprev/sym return fresh handles; set(...) is the in-place reassignment.
• Encoded handles pack (index, orient) into an unsigned 32-bit number, exactly like the Rust EncodedTri/EncodedSub.
• Single package, modular folders (src/{common,triangle}); can split into a workspace later.

Tests

npm test runs the ported parity suites:

• predicate kernel incl. a BigInt-oracle stress over a 7⁴ integer grid
• half-edge bond/sym/lnext navigation and handle encoding
• D&C Delaunay: Euler relation, CCW orientation, and a full empty-circumcircle check over 200 deterministic pseudo-random points
• constraint insertion (forced diagonal, hull marking)
• hole carving (square hole, concave L-shape, the demo's star-with-hole scene)
• navmesh build (region partition, even area split, symmetric adjacency, boundary-edge tracing, area-weighted random sampling)
• BSP locate / nearest / queryAabb all checked against brute force, plus empty-mesh safety
• navigation: A* + funnel paths (straight in open regions, bends around holes, commits to the shorter channel around an offset hole), clearance gating of narrow squeezes, line-of-sight, path revalidation, and visibility occlusion
• binary format: round-trip, recompute-on-load from minimal sections, unknown- section tolerance, and cross-language loading of an rsnav-written fixture (with byte-identical re-serialization)