clearpath 0.1.0

Deterministic 2D obstacle-avoidance path planning and smooth cubic Bezier fitting
Documentation

clearpath

CI Slop Gate

Deterministic 2D obstacle-avoidance path planning and smooth cubic Bézier fitting, in no_std + alloc.

Given a workspace, polygonal obstacles, and two endpoints, clearpath returns either a C¹ chain of cubic Bézier segments or a rectilinear polyline. Every returned curve is collision-free with the configured margin, and the whole pipeline is deterministic: the same input produces the same output bits on the same target.

use clearpath::{BoundingBox, Point2D, Polygon, PathPlanner, RouteRequest};

let mut req = RouteRequest::new(
    BoundingBox::new(Point2D::new(0.0, 0.0), Point2D::new(10.0, 10.0)),
    Point2D::new(1.0, 5.0),
    Point2D::new(9.0, 5.0),
);
req.obstacles = vec![Polygon::new(vec![
    Point2D::new(4.0, 4.0),
    Point2D::new(6.0, 4.0),
    Point2D::new(6.0, 6.0),
    Point2D::new(4.0, 6.0),
])?];

let mut planner = PathPlanner::new();
let segments = planner.route_smooth(&req)?;
# Ok::<(), clearpath::PathPlanError>(())

Origin and provenance

This crate started life as pathplan, named after Graphviz's libpathplan — the C++ library behind Graphviz routing, which finds a path around obstacles and then fits a smooth spline through it. That is the same problem this crate solves, and it is the origin of the name and of the ambition: the same job, in safe Rust, with no_std.

No code was copied, ported, or translated. The two are related by problem, not by implementation, and the algorithms are materially different:

Graphviz's libpathplan here
Finding the path builds a visibility graph over obstacle vertices decomposes the free space into a vertical (trapezoidal) decomposition
Searching it shortest path in that graph A* over cell adjacency, monotone in the sweep direction
Shortening it — Lee–Preparata funnel: the taut string through a corridor of portals
Fitting the curve its own spline fitting minimum-curvature tangent solve, clamped to admissible sets, verified against the exact clearance

The name changed to clearpath because pathplan describes the provenance rather than the guarantee, and because it is not how a Rust crate's name reads. docs/SPEC.md keeps the old name wherever the derivation is the point.

The algorithms this actually implements:

  • the vertical (trapezoidal) decomposition of a polygonal domain — standard computational geometry;
  • Lee & Preparata, Linear-time algorithms for shortest paths in planar graphs, JCSS 1984 — the funnel;
  • a minimum-curvature variational tangent solve (Schoenberg's natural-spline family), banded and solved by Cholesky;
  • Shewchuk-style adaptive exact predicates for orientation and in-circle.

How it works

Four stages, each consuming plain data:

Stage Module What it does
1 decomp A +x sweep decomposes the free space into convex trapezoids with vertical portals.
2 funnel A* over the cell adjacency finds a corridor; the Lee–Preparata funnel pulls the shortest taut string through it.
3 corridor Each knot gets the set of tangents that keep the neighbouring control points in the free space.
4 spline A minimum-curvature tangent solve, then a repair that clamps until every control hull is clear.

Three properties are worth knowing about, because they are where the design earns its keep:

The margin is applied once, exactly. The forbidden geometry is the workspace eroded by margin and every obstacle grown by it — a square inflation of a rectilinear partition, which is exact and needs no arc approximation. A nonzero margin against a non-rectilinear obstacle is reported as MarginUnsupportedGeometry rather than approximated, because approximating it silently produces curves that pass within margin of the obstacle they were pushed off.

Testing a cell's centre is exact, not a sample. The sweep's event lines pass through every obstacle face, so no face crosses a cell's interior and a cell is wholly in or wholly out of each obstacle.

Collisions are prevented, not filtered. A cubic Bézier lies inside the convex hull of its four control points, so a clear hull is a clear curve. Every hull is tested exactly against the obstacles — vertices by distance, edges for both crossings and clearance, obstacle vertices for containment — and a route that fails is refused rather than emitted.

What it does not do

  • No incremental decomposition: the free space is rebuilt per query. A warm query therefore allocates (see the performance note below).
  • No global optimality across homotopy classes. The corridor search returns one corridor and the funnel is optimal within it.
  • No self-intersecting obstacle polygons, and no polygons with holes. A hole is expressible as a reversed-wound simple polygon.

docs/SPEC.md is the normative specification, and it is kept honest: it records every ambiguity that was resolved, including the several where the original design turned out to be unimplementable and was replaced.

Performance

Measured on an aarch64 core, release build, 1000×1000 workspace, axis-aligned boxes on a lattice. cargo bench reproduces them.

Obstacles route_smooth, margin 0 margin 1
10 26 µs 16 µs
50 118 µs 90 µs
200 713 µs 649 µs

The specification's original target was 50 µs for 10–50 boxes. It was missed by 3x when the optimisation pass started and is now met at 10 boxes with a 2x margin; 50 boxes is 2.4x over. 10 boxes went 157 µs → 26 µs and 50 boxes 510 µs → 118 µs.

The stage split is not where the design suggests, and that is the most useful thing the benchmarks produced. At 10 boxes the sweep is 7.7 µs. The funnel was 77 µs — half the query — and none of it was the funnel's geometry: it was the corridor-membership check, which sampled every segment twice per unit of length and asked each sample whether any corridor cell contained it. A sample standing in for a proof, two thousand exact predicates per long segment. Stating it exactly — a cell is a trapezoid, so containment is a pair of half-interval intersections — took that stage to 0.4 µs.

The repair had the same shape of problem. Its obstacle loop was gated on the hull's bounding box, but a control hull on a long route is long and thin, so its box is most of the workspace and every obstacle passed it: 960 segment tests per query at 10 boxes, 6000 at 50. Replacing that proxy with an exact local test — does this hull edge come within margin of this obstacle's box? — is a slab test, and it took the repair from 25 µs to 7.6 µs.

A spatial index was not built, because the measurements did not call for one. The cost was never a lack of locality in the data; it was a bad locality proxy in the query, and four comparisons answer that exactly where a lookup would answer it approximately. A grid remains the right answer for a query that genuinely spans the workspace, and is the next step if the obstacle count grows enough for the linear scan to dominate again.

A warm query makes 89 allocations at 10 boxes (232 at 50), down from 292 and 657 at the start of the optimisation work. The decomposition — the only stage that scaled with the input — now allocates nothing when warm, because it is refilled in place and owns its transient sweep state. The zero-allocation goal of docs/SPEC.md §8.1 is still not met: about 30 small Vecs remain across the other five stages, worth under a microsecond, and removing them is only worth doing for a caller who needs a genuinely allocation-free query — which argues for exposing a caller-owned scratch rather than more plumbing inside the stages.

Development

./scripts/ci.sh

builds, checks no_std, runs clippy with -D warnings, asserts src/ contains no unsafe and no #[allow(unsafe_code)], and runs the test suite six times — the property tests reseed every run, and two of the bugs found during development reproduced on only some seeds, so one green run is not evidence. cargo bench --bench route produces the tables above.

Licensed under MIT OR Apache-2.0.