Crate route_snapper 

A Rust library to accurately project an ordered list of stops onto a route line. This version uses a high-performance greedy algorithm with single-level backtracking to robustly handle complex route overlaps.

Algorithm Overview

1. Anchoring & Spatial Index: The first stop is fixed to the start of the route (distance = 0), and the last stop is fixed to the end. An R-tree is built from the route’s line segments for fast geometric lookups.

2. Greedy Forward Search: For each intermediate stop, an adaptive search finds the most plausible forward projection. It does this by creating a small pool of valid forward candidates from the nearest segments and then selecting the one with the best geographic fit (lowest projection error).

3. Backtracking on Failure: If projecting Stop N fails (no valid forward candidates are found), the algorithm assumes the greedy choice for Stop N-1 was incorrect (e.g., snapped to an early part of a large loop). It then: a. Backtracks to Stop N-1. b. Re-runs the search for Stop N-1, explicitly excluding the previous projection. c. With a new, corrected projection for Stop N-1, it retries projecting Stop N.

Example Usage

use route_snapper::{project_stops, Stop};
use geo_types::{Coord, LineString};

fn main() {
    let route_line = LineString::from(vec![
        Coord { x: 0.0, y: 0.0 },   // Start (matches Stop "A")
        Coord { x: 100.0, y: 0.0 },
        Coord { x: 200.0, y: 0.0 }, // End of cul-de-sac
        Coord { x: 100.0, y: 0.0 },
        Coord { x: 0.0, y: 0.0 },   // End (matches Stop "D")
    ]);

    let stops = vec![
        Stop { id: "A".to_string(), location: Coord { x: 0.0, y: 1.0 } },   // First stop
        Stop { id: "B".to_string(), location: Coord { x: 99.0, y: 2.0 } },  // Intermediate
        Stop { id: "C".to_string(), location: Coord { x: 101.0, y: -2.0 } }, // Intermediate (on overlap)
        Stop { id: "D".to_string(), location: Coord { x: 0.0, y: -1.0 } },  // Last stop
    ];

    let results = project_stops(&route_line, &stops, None).unwrap();

    assert!((results[0].distance_along_route - 0.0).abs() < 1e-9);    // First stop anchored
    assert!((results[1].distance_along_route - 99.0).abs() < 1e-9);   // Snapped correctly
    assert!((results[2].distance_along_route - 299.0).abs() < 1e-9);  // Snapped correctly on return trip
    assert!((results[3].distance_along_route - 400.0).abs() < 1e-9);  // Last stop anchored
}

Structs

ProjectedStop

The output struct representing a stop’s successful projection onto the route.

ProjectionConfig

A configuration struct for the projection algorithm.

Stop

Represents a single bus stop with a unique identifier and location.

Enums

ProjectionError

Custom error types for the library.

Functions

project_stops

The main function of the library.