Module route

Exact planar shortest paths over a visibility graph, with typed unreachable reasons.

The kernel reports that no route exists under a given envelope. It never reports that a design is non-compliant: that reading belongs to the consumer, not to geometry.

Structs

CostRegion

A polygon inside which travel costs factor times its length.

DistanceMap

Shortest-path distances from every point of a region to the nearest of several targets.

Farthest

The greatest distance from a subregion to the nearest target.

ForcedWalk

The shortest walk from an origin to a target that enters a polygon.

LengthInterval

A closed interval of lengths.

Reach

The nearest target from a point, and the route there.

Route

A shortest path and its length.

Skeleton

The skeleton: nodes and the edges joining them.

SkeletonNode

One node of the skeleton.

Wall

A wall edge: which polygon, which ring (0 the outer, k the k-th hole) and which edge of it (from point edge to the next).

WeightedForcedWalk

The cheapest walk from an origin to a target that enters a polygon, over weighted maps.

WeightedMap

Weighted distances to the nearest of several targets, bracketed.

WeightedReach

The nearest target by weighted distance, bracketed, and a walk there.

Enums

FarthestError

Why no bracket was produced.

MapError

Why no distance map was built.

NodeKind

What a skeleton node is.

RouteError

A malformed query, as opposed to an honest “no route”.

SkeletonError

Why no skeleton was built.

Unreachable

Why no path was produced.

Constants

MAX_CELLS

Cells farthest_point refines at most.

MAX_VERTICES

Maximum vertices, counting region, barrier and endpoint vertices.

MAX_WEIGHTED_NODES

Graph nodes a weighted map builds at most: region, barrier, target and cost-polygon vertices, and the points along cost edges.

Functions

distance_map

A distance map from targets over region, avoiding barriers.

distance_map_weighted

A distance map whose targets each start at their own distance: the distance from a point is the least, over targets, of the route’s length to the target plus the target’s weight (#197). For a way out that carries the rest of a walk beyond it, such as a stair landing. With every weight zero it is distance_map.

distance_map_within

distance_map with a caller-chosen vertex budget.

distance_map_within_weighted

distance_map_weighted with a caller-chosen vertex budget.

farthest_point

The greatest distance to the nearest target over the points of subregion in the map’s free space, bracketed to within tolerance.

farthest_point_within

farthest_point with a caller-chosen cell budget.

forced_walk

The shortest walk from an origin of from to a target of to that enters through, bracketed to within tolerance.

forced_walk_within

forced_walk with a caller-chosen cell budget.

shortest_path

Shortest path from start to goal inside region, avoiding barriers.

shortest_path_within

shortest_path with a caller-chosen vertex budget.

skeleton

The skeleton of region, its boundary sampled at most spacing apart, keeping the nodes whose nearest walls spread at least prune times their clearance apart (1.5 drops the spurs into right-angled corners; 0 keeps every node).

weighted_distance_map

A weighted distance map from targets over region, avoiding barriers, with travel inside costs weighted by their factors and points along cost edges at most spacing apart.

weighted_distance_map_seeded

A weighted distance map whose targets each start at their own cost: the distance from a point is the least, over targets, of the weighted cost of a walk to the target plus the target’s weight (#198), as crate::distance_map_weighted is for plain maps. With every weight zero it is weighted_distance_map.

weighted_distance_map_seeded_within

weighted_distance_map_seeded with a caller-chosen node budget.

weighted_distance_map_within

weighted_distance_map with a caller-chosen node budget.

weighted_farthest_point

The greatest weighted distance from a subregion to the nearest target over its points in the free space, bracketed to within tolerance where the map’s own bracket allows: the result is never narrower than the gap between the map’s bounds at the farthest point.

weighted_farthest_point_within

weighted_farthest_point with a caller-chosen cell budget.

weighted_forced_walk

The cheapest walk from an origin of from to a target of to that enters through, where both maps weight travel by the same cost regions (#198): forced_walk for WeightedMaps. Origins’ start weights (see crate::weighted_distance_map_seeded) count.

weighted_forced_walk_within

weighted_forced_walk with a caller-chosen cell budget.