pelorus 0.1.0

A high-performance GPS map-matching library for geospatial road network processing
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

pub mod graph;

use crate::road_network::types::RoadNetwork;
use geo::Point;
use petgraph::algo::dijkstra;
use std::collections::HashMap;
use std::sync::{LazyLock, Mutex};

pub use graph::NetworkGraph;

// Simplified caching with fewer conversions
type RouteKey = (u64, u64); // Hash of start and end points
type RouteCache = HashMap<RouteKey, Option<f64>>;

static ROUTE_CACHE: LazyLock<Mutex<RouteCache>> =
    LazyLock::new(|| Mutex::new(HashMap::new()));

/// Calculate the shortest route distance between two points using Dijkstra's algorithm.
/// Returns None if no path exists (disconnected components).
pub fn calculate_route_distance(
    network: &RoadNetwork,
    start_point: Point<f64>,
    end_point: Point<f64>,
) -> Option<f64> {
    // Check cache first
    let cache_key = create_cache_key(start_point, end_point);

    if let Ok(cache) = ROUTE_CACHE.lock() {
        if let Some(&cached_result) = cache.get(&cache_key) {
            return cached_result;
        }
    }

    // Build graph from network
    let graph = NetworkGraph::from_road_network(network);

    calculate_route_distance_with_graph(&graph, start_point, end_point)
}

/// Calculate route distance with a pre-built graph for better performance
/// when making multiple queries on the same network.
pub fn calculate_route_distance_with_graph(
    graph: &NetworkGraph,
    start_point: Point<f64>,
    end_point: Point<f64>,
) -> Option<f64> {
    // Check cache first
    let cache_key = create_cache_key(start_point, end_point);

    if let Ok(cache) = ROUTE_CACHE.lock() {
        if let Some(&cached_result) = cache.get(&cache_key) {
            return cached_result;
        }
    }

    // Find closest nodes to start and end points
    let start_node = graph.find_closest_node(start_point)?;
    let end_node = graph.find_closest_node(end_point)?;

    // Use petgraph's Dijkstra implementation
    let distances = dijkstra(&graph.graph, start_node, Some(end_node), |edge_ref| {
        edge_ref.weight().length
    });

    let result = distances.get(&end_node).copied();

    // Cache the result
    cache_result(cache_key, result);

    result
}

/// Clear the route cache (useful for testing or memory management)
pub fn clear_route_cache() {
    if let Ok(mut cache) = ROUTE_CACHE.lock() {
        cache.clear();
    }
}

// Simplified cache key using hash instead of coordinate conversion
fn create_cache_key(start_point: Point<f64>, end_point: Point<f64>) -> RouteKey {
    use std::collections::hash_map::DefaultHasher;
    use std::hash::{Hash, Hasher};

    let mut hasher = DefaultHasher::new();

    // Hash start point (with some precision rounding to group nearby points)
    let start_x = (start_point.x() * 1e6).round() as i64;
    let start_y = (start_point.y() * 1e6).round() as i64;
    start_x.hash(&mut hasher);
    start_y.hash(&mut hasher);
    let start_hash = hasher.finish();

    // Hash end point
    let mut hasher = DefaultHasher::new();
    let end_x = (end_point.x() * 1e6).round() as i64;
    let end_y = (end_point.y() * 1e6).round() as i64;
    end_x.hash(&mut hasher);
    end_y.hash(&mut hasher);
    let end_hash = hasher.finish();

    (start_hash, end_hash)
}

// Extracted cache management
fn cache_result(cache_key: RouteKey, result: Option<f64>) {
    if let Ok(mut cache) = ROUTE_CACHE.lock() {
        // Limit cache size to prevent memory bloat
        if cache.len() > 1000 {
            cache.clear();
        }
        cache.insert(cache_key, result);
    }
}