routee_compass_core/model/map/
spatial_index.rs

1use std::sync::Arc;
2
3use super::{
4    GeometryModel, MapEdgeRTreeObject, MapError, MapVertexRTreeObject, NearestSearchResult,
5    SpatialIndexType,
6};
7use crate::model::network::{Graph, Vertex};
8use geo::Point;
9use rstar::RTree;
10use uom::si::f64::Length;
11
12pub enum SpatialIndex {
13    VertexOrientedIndex {
14        rtree: RTree<MapVertexRTreeObject>,
15        tolerance: Option<Length>,
16    },
17    EdgeOrientedIndex {
18        rtree: RTree<MapEdgeRTreeObject>,
19        tolerance: Option<Length>,
20    },
21}
22
23impl SpatialIndex {
24    /// build a spatial index of the declared [`SpatialIndexType`]
25    pub fn build(
26        spatial_index_type: &SpatialIndexType,
27        graph: Arc<Graph>,
28        geometry_models: &[GeometryModel],
29        tolerance: Option<Length>,
30    ) -> SpatialIndex {
31        match spatial_index_type {
32            SpatialIndexType::VertexOriented => {
33                SpatialIndex::new_vertex_oriented(&graph.clone().vertices, tolerance)
34            }
35            SpatialIndexType::EdgeOriented => {
36                SpatialIndex::new_edge_oriented(graph, geometry_models, tolerance)
37            }
38        }
39    }
40
41    /// creates a new instance of the rtree model that is vertex-oriented; that is, the
42    /// rtree is built over the vertices in the graph, and nearest neighbor searches return
43    /// a VertexId.
44    pub fn new_vertex_oriented(vertices: &[Vertex], tolerance: Option<Length>) -> Self {
45        let entries: Vec<MapVertexRTreeObject> =
46            vertices.iter().map(MapVertexRTreeObject::new).collect();
47        let rtree = RTree::bulk_load(entries);
48        Self::VertexOrientedIndex { rtree, tolerance }
49    }
50
51    /// creates a new instance of the rtree model that is edge-oriented; that is, the
52    /// rtree is built over the edges in the graph, and nearest neighbor searches return
53    /// the edge's destination vertex.
54    /// - future work: make SearchOrientation set which incident vertex is returned.
55    pub fn new_edge_oriented(
56        graph: Arc<Graph>,
57        geometry_models: &[GeometryModel],
58        tolerance: Option<Length>,
59    ) -> Self {
60        let entries: Vec<MapEdgeRTreeObject> = graph
61            .edges()
62            .zip(geometry_models.iter().flat_map(|g| g.geometries()))
63            .map(|(e, g)| MapEdgeRTreeObject::new(e, g))
64            .collect();
65        let rtree = RTree::bulk_load(entries.to_vec());
66
67        Self::EdgeOrientedIndex { rtree, tolerance }
68    }
69
70    /// gets the nearest graph id, which is a VertexId or EdgeId depending on the orientation
71    /// of the RTree.
72    pub fn nearest_graph_id(&self, point: &Point<f32>) -> Result<NearestSearchResult, MapError> {
73        match self {
74            SpatialIndex::VertexOrientedIndex { rtree, tolerance } => {
75                let nearest = rtree.nearest_neighbor(point).ok_or_else(|| {
76                    MapError::MapMatchError(String::from("no map vertices exist for matching"))
77                })?;
78                nearest.within_distance_threshold(point, tolerance)?;
79                Ok(NearestSearchResult::NearestVertex(nearest.vertex_id))
80            }
81            SpatialIndex::EdgeOrientedIndex { rtree, tolerance } => {
82                let nearest = rtree.nearest_neighbor(point).ok_or_else(|| {
83                    MapError::MapMatchError(String::from("no map vertices exist for matching"))
84                })?;
85                nearest.within_distance_threshold(point, tolerance)?;
86                Ok(NearestSearchResult::NearestEdge(
87                    nearest.edge_list_id,
88                    nearest.edge_id,
89                ))
90            }
91        }
92    }
93
94    /// builds an iterator over map edges ordered by nearness to the given point.
95    /// applies the (map-matching) distance tolerance filter.
96    pub fn nearest_graph_id_iter<'a>(
97        &'a self,
98        point: &'a Point<f32>,
99    ) -> Box<dyn Iterator<Item = Result<NearestSearchResult, MapError>> + 'a> {
100        match self {
101            SpatialIndex::VertexOrientedIndex { rtree, tolerance } => {
102                let iter = rtree
103                    .nearest_neighbor_iter_with_distance_2(point)
104                    .map_while(|(obj, _)| {
105                        let valid = match obj.test_threshold(point, tolerance) {
106                            Ok(v) => v,
107                            Err(e) => return Some(Err(e)),
108                        };
109                        if valid {
110                            Some(Ok(NearestSearchResult::NearestVertex(obj.vertex_id)))
111                        } else {
112                            None
113                        }
114                    });
115                Box::new(iter)
116            }
117            SpatialIndex::EdgeOrientedIndex { rtree, tolerance } => {
118                let iter = rtree
119                    .nearest_neighbor_iter_with_distance_2(point)
120                    .map_while(|(obj, _)| {
121                        let valid = match obj.test_threshold(point, tolerance) {
122                            Ok(v) => v,
123                            Err(e) => return Some(Err(e)),
124                        };
125                        if valid {
126                            Some(Ok(NearestSearchResult::NearestEdge(
127                                obj.edge_list_id,
128                                obj.edge_id,
129                            )))
130                        } else {
131                            None
132                        }
133                    });
134                Box::new(iter)
135            }
136        }
137    }
138
139    /// Returns true if this is an edge-oriented spatial index.
140    pub fn is_edge_oriented(&self) -> bool {
141        matches!(self, SpatialIndex::EdgeOrientedIndex { .. })
142    }
143}
144
145#[cfg(test)]
146mod test {
147    use std::path::PathBuf;
148
149    use super::*;
150    use crate::{
151        model::network::{Vertex, VertexId},
152        util::fs::read_utils,
153    };
154    use geo;
155
156    #[test]
157    fn test_vertex_oriented_e2e() {
158        let vertices_filepath = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
159            .join("src")
160            .join("model")
161            .join("map")
162            .join("test")
163            .join("rtree_vertices.csv");
164
165        // let query_filepath = PathBuf::from(env!("CARGO_MANIFEST_DIR"))
166        //     .join("src")
167        //     .join("model")
168        //     .join("map")
169        //     .join("test")
170        //     .join("rtree_query.json");
171
172        let vertices: Box<[Vertex]> =
173            read_utils::from_csv(&vertices_filepath.as_path(), true, None, None).unwrap();
174        let index = SpatialIndex::new_vertex_oriented(&vertices, None);
175
176        // test nearest neighbor queries perform as expected
177        let o_result = index
178            .nearest_graph_id(&geo::Point(geo::Coord::from((0.101, 0.101))))
179            .unwrap();
180        let d_result = index
181            .nearest_graph_id(&geo::Point(geo::Coord::from((1.901, 2.101))))
182            .unwrap();
183        match o_result {
184            NearestSearchResult::NearestEdge(_, _) => panic!("should find a vertex!"),
185            NearestSearchResult::NearestVertex(vertex_id) => assert_eq!(vertex_id, VertexId(0)),
186        }
187        match d_result {
188            NearestSearchResult::NearestEdge(_, _) => panic!("should find a vertex!"),
189            NearestSearchResult::NearestVertex(vertex_id) => assert_eq!(vertex_id, VertexId(2)),
190        }
191    }
192}
routee_compass_core/model/map/spatial_index.rs

routee_compass_core/model/map/
spatial_index.rs
