str8-path

Central path-finding through a polygon via its straight skeleton.

Give it a container polygon and two endpoints — points, or whole regions — and it routes a "nice" path between them that travels through the middle of the shape, keeping clearance from the walls. Built on @matthewjacobson/str8 (CGAL straight skeleton compiled to WebAssembly) and JSTS for the geometry model.

Inputs and outputs are JSTS geometries, so it drops into a JSTS pipeline.

Install

npm install str8-path jsts

jsts is a regular dependency; you'll also use it directly to build the geometries you pass in.

Usage

import { PathFinder } from 'str8-path';
import GeometryFactory from 'jsts/org/locationtech/jts/geom/GeometryFactory.js';

await PathFinder.init(); // loads the str8 WASM + jsts once

const gf = new GeometryFactory();
// ...build a container Polygon and a source/sink with jsts...

const pf = new PathFinder(containerPolygon);     // precomputes skeleton, graph, index
const result = pf.findPath(source, sink, { centrality: 0.6 });

if (result) {
  result.line;            // jsts LineString
  result.length;          // number
  result.clearance;       // { min, mean } distance to the walls along the path
  result.points;          // [{x, y}, ...] (source end first)
}

source and sink can be any JSTS geometry — a Point (point-to-point), a Polygon or LineString (boundary-to-boundary, the best entry/exit is chosen for you), or a Multi*. Geometries outside the container fall back to the nearest point on the container.

API

await PathFinder.init()

Loads the WASM straight-skeleton engine and JSTS. Call once before constructing.

new PathFinder(polygon, options?)

• polygon — a JSTS Polygon (with optional holes), the container/domain.
• options.boundarySamples — boundary sampling resolution for region sources/sinks (divisor of the container's span; default 60).

Precomputes the straight skeleton, its edge graph, and an STRtree index of the boundary used for fast clearance / nearest-point queries.

pathFinder.findPath(source, sink, options?) → PathResult | null

• options.centrality — 0 = shortest / taut, 1 = hug the centre. Default 0.5.
• options.smooth — round the path (clearance-safe). Default true.

Returns { line, length, clearance: { min, mean }, points }, or null if no path exists.

How it works

1. The container's straight skeleton is the polygon's "spine"; each skeleton vertex carries a time value that equals its clearance to the nearest wall.
2. source/sink are reduced to boundary sample points; each attaches to the skeleton at the best visible node of the face it lands in, biased toward the other endpoint.
3. A virtual super-source/super-sink over those samples lets one Dijkstra pick the optimal entry/exit pair.
4. The route is string-pulled (a clearance bound set by centrality: 0 pulls taut, higher keeps it central) and smoothed without crossing walls.

A note on the centrality dial

Skeleton routing is central by construction. The centrality dial visibly changes the path where there's a genuine choice — open space to cut across, or holes/branches offering alternative routes. On a simple hole-free polygon the skeleton route between two points is unique, so 0 and 1 can coincide; the true shortest (wall-hugging geodesic) is deliberately not what this computes.

License

MIT. Uses @matthewjacobson/str8 (CGAL's Straight_skeleton_2 is GPL — review CGAL's licensing for your use) and JSTS (EDL/EPL).