Crate axiolid_route

Expand description

Exact planar shortest path over a visibility graph.

§Why exact, and what that means here

axiolid-field already answers route questions, but by sampling a grid: its answer is only as good as the resolution. On a polygon set the shortest path is exactly computable, because the optimal path is a polyline whose interior vertices are region or barrier vertices. No discretisation, no resolution parameter.

“Exact” is a claim about the COMBINATORICS, and it is earned by deciding every segment-crossing and sidedness question with certified orient2d rather than a tolerance comparison. Which edges exist in the visibility graph is therefore exact. The path LENGTH is still a sum of square roots evaluated in binary64, so it carries ordinary floating-point rounding. Overstating that as “exact length” would be a false claim, so it is not made.

§Not a verdict

The kernel owns the region, the graph, the path and the typed unreachable reason. It does not own why a route was requested, what clearance is required, or whether a length is acceptable. Same line navigate.rs draws.

§Input size is bounded explicitly

Visibility graph construction is quadratic in vertices and cubic to verify, so a large input silently becomes a hang. MAX_VERTICES caps it and oversized input is REFUSED, never truncated: truncating would answer a different question than the one asked, and the caller would not be told.

The cap is a default, not a law. shortest_path_within takes the budget as a parameter, because what is affordable depends on the caller’s deadline rather than on the kernel. And the refusal carries a PROVEN lower bound — the straight-line distance between the endpoints, which no route can beat — so an over-budget query still yields a usable fact instead of only an error.

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.