h3ron_graph/algorithm/
nearest_graph_nodes.rs

1use crate::error::Error;
2use crate::graph::node::NodeType;
3use crate::graph::GetCellNode;
4use h3ron::H3Cell;
5
6/// find the nearest nodes in the graph
7pub trait NearestGraphNodes {
8    /// get an iterator over the closest corresponding nodes in the graph to the
9    /// given cell. The iterator will return all nodes with the
10    /// same, smallest `k` <= `max_distance_k` which are part of the graph.
11    fn nearest_graph_nodes(
12        &self,
13        cell: &H3Cell,
14        max_distance_k: u32,
15    ) -> Result<NearestGraphNodesGetCellIter<Self>, Error>
16    where
17        Self: Sized;
18}
19
20pub struct NearestGraphNodesGetCellIter<'a, G> {
21    graph: &'a G,
22    neighbors_reversed: Vec<(u32, H3Cell)>,
23    found_max_k: u32,
24}
25
26impl<'a, G> Iterator for NearestGraphNodesGetCellIter<'a, G>
27where
28    G: GetCellNode,
29{
30    type Item = (H3Cell, NodeType, u32);
31
32    fn next(&mut self) -> Option<Self::Item> {
33        while let Some((neighbor_k, neighbor_cell)) = self.neighbors_reversed.pop() {
34            if neighbor_k > self.found_max_k {
35                break;
36            }
37
38            if let Some(node_type) = self.graph.get_cell_node(&neighbor_cell) {
39                self.found_max_k = neighbor_k;
40                return Some((neighbor_cell, node_type, neighbor_k));
41            }
42        }
43        None
44    }
45}
46
47impl<G> NearestGraphNodes for G
48where
49    G: GetCellNode,
50{
51    fn nearest_graph_nodes(
52        &self,
53        cell: &H3Cell,
54        max_distance_k: u32,
55    ) -> Result<NearestGraphNodesGetCellIter<G>, Error> {
56        let mut neighbors = cell.grid_disk_distances(0, max_distance_k)?;
57
58        // reverse the order to gave the nearest neighbors first
59        neighbors.sort_unstable_by_key(|neighbor| max_distance_k - neighbor.0);
60
61        Ok(NearestGraphNodesGetCellIter {
62            graph: self,
63            neighbors_reversed: neighbors,
64            found_max_k: max_distance_k,
65        })
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    use crate::algorithm::NearestGraphNodes;
72    use crate::graph::node::NodeType;
73    use crate::graph::GetCellNode;
74    use h3ron::collections::H3CellSet;
75    use h3ron::{H3Cell, Index};
76
77    impl GetCellNode for H3CellSet {
78        fn get_cell_node(&self, cell: &H3Cell) -> Option<NodeType> {
79            self.get(cell).map(|_| NodeType::OriginAndDestination)
80        }
81    }
82
83    #[test]
84    fn nearest_finds_given_cell_first() {
85        let cell = H3Cell::new(0x89283080ddbffff_u64);
86        let mut cellset = H3CellSet::default();
87        for ring_cell in cell.grid_disk(3).unwrap().iter() {
88            cellset.insert(ring_cell);
89        }
90        assert_eq!(cellset.nearest_graph_nodes(&cell, 3).unwrap().count(), 1);
91        assert_eq!(
92            cellset.nearest_graph_nodes(&cell, 3).unwrap().next(),
93            Some((cell, NodeType::OriginAndDestination, 0))
94        );
95    }
96
97    #[test]
98    fn nearest_finds_all_with_same_k() {
99        let cell = H3Cell::new(0x89283080ddbffff_u64);
100        let mut cellset = H3CellSet::default();
101        let mut expected = H3CellSet::default();
102        for (_, ring_cell) in cell.grid_disk_distances(2, 3).unwrap().iter().take(2) {
103            cellset.insert(*ring_cell);
104            expected.insert(*ring_cell);
105        }
106        for (_, ring_cell) in cell.grid_disk_distances(4, 5).unwrap().iter().take(2) {
107            cellset.insert(*ring_cell);
108        }
109        assert_eq!(cellset.nearest_graph_nodes(&cell, 8).unwrap().count(), 2);
110        for (nearest_cell, _, _) in cellset.nearest_graph_nodes(&cell, 8).unwrap() {
111            assert!(expected.contains(&nearest_cell));
112        }
113    }
114}
h3ron_graph/algorithm/nearest_graph_nodes.rs

h3ron_graph/algorithm/
nearest_graph_nodes.rs
