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

use crate::road_network::types::RoadNetwork;
use crate::types::{RoadSegment, SegmentId};
use geo::{Coord, Point};
use petgraph::graph::{NodeIndex, UnGraph};
use petgraph::Graph;
use std::collections::HashMap;

pub type NodeId = NodeIndex;

// Simplified: Just store the point coordinate, no extra wrapper
pub type GraphNode = Point<f64>;

#[derive(Debug, Clone, PartialEq)]
pub struct GraphEdge {
    pub segment_id: SegmentId,
    pub length: f64,
}

#[derive(Debug, Clone)]
pub struct NetworkGraph {
    pub graph: UnGraph<GraphNode, GraphEdge>,
    // Use a more efficient coordinate key for node deduplication
    node_map: HashMap<(u64, u64), NodeId>,
}

impl NetworkGraph {
    pub fn new() -> Self {
        Self {
            graph: Graph::new_undirected(),
            node_map: HashMap::new(),
        }
    }

    pub fn from_road_network(network: &RoadNetwork) -> Self {
        let mut graph = Self::new();

        for segment in network.segments.values() {
            graph.add_segment(segment);
        }

        graph
    }

    pub fn add_segment(&mut self, segment: &RoadSegment) {
        let coords: Vec<Coord<f64>> = segment.geometry.coords().cloned().collect();
        if coords.len() < 2 {
            return; // Invalid segment
        }

        let start_point = Point::new(coords[0].x, coords[0].y);
        let end_point =
            Point::new(coords[coords.len() - 1].x, coords[coords.len() - 1].y);

        let start_node_id = self.get_or_create_node(start_point);
        let end_node_id = self.get_or_create_node(end_point);

        // Calculate segment length using geo crate
        let length = {
            use geo::algorithm::euclidean_length::EuclideanLength;
            segment.geometry.euclidean_length()
        };

        // Create edge with petgraph
        let edge = GraphEdge {
            segment_id: segment.id,
            length,
        };

        self.graph.add_edge(start_node_id, end_node_id, edge);
    }

    fn get_or_create_node(&mut self, point: Point<f64>) -> NodeId {
        // Convert to fixed-precision integer coordinates for reliable hashing
        let coord_key = self.point_to_key(point);

        if let Some(&node_id) = self.node_map.get(&coord_key) {
            return node_id;
        }

        // Create new node - petgraph handles the NodeIndex generation
        let node_id = self.graph.add_node(point);
        self.node_map.insert(coord_key, node_id);

        node_id
    }

    fn point_to_key(&self, point: Point<f64>) -> (u64, u64) {
        // Use bit representation for exact f64 comparison
        (point.x().to_bits(), point.y().to_bits())
    }

    pub fn node_count(&self) -> usize {
        self.graph.node_count()
    }

    pub fn edge_count(&self) -> usize {
        self.graph.edge_count()
    }

    pub fn find_closest_node(&self, point: Point<f64>) -> Option<NodeId> {
        use geo::algorithm::euclidean_distance::EuclideanDistance;

        // Use petgraph's node_indices iterator
        self.graph.node_indices().min_by(|&a, &b| {
            let node_a = &self.graph[a];
            let node_b = &self.graph[b];
            let dist_a = node_a.euclidean_distance(&point);
            let dist_b = node_b.euclidean_distance(&point);
            dist_a
                .partial_cmp(&dist_b)
                .unwrap_or(std::cmp::Ordering::Equal)
        })
    }
}