osmgraph/graph/
node.rs

1use core::fmt;
2use std::collections::{HashSet, HashMap};
3use std::error::Error;
4
5use crate::graph::way::OSMWay;
6use crate::api::Element;
7
8type OSMTag = Option<HashMap<String, String>>;
9
10/// OSMNode contains all information that we might care about in a node. Currently, it contains a
11/// node ID (as defined in Overpass API) a latitude and a longitude.
12#[derive(Clone, PartialEq, Debug, Default)]
13pub struct OSMNode {
14    id: u64,
15    lat: f64,
16    lon: f64,
17    tags: OSMTag
18}
19
20impl fmt::Display for OSMNode {
21    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
22        write!(f, "OSMNode(id: {}, lat: {}, lon: {})", self.id, self.lat, self.lon)
23    }
24}
25
26//Just getters and setters for now
27impl OSMNode {
28
29    /// Create a new OSMNode from fields.
30    pub fn new(id: u64, lat: f64, lon: f64, tags: OSMTag) -> Self {
31        OSMNode { id, lat, lon, tags}
32    }
33
34    /// Get the node ID.
35    pub fn id(&self) -> u64 {
36        self.id
37    }
38    /// Get the node latitude.
39    pub fn lat(&self) -> f64 {
40        self.lat
41    }
42    /// Get the node longitude. 
43    pub fn lon(&self) -> f64 {
44        self.lon
45    }
46
47    /// Get a reference tags associated with this node
48    pub fn tags(&self) -> &OSMTag {
49        &self.tags
50    }
51}
52
53/// Compute the [haversine distance](https://en.wikipedia.org/wiki/Haversine_formula)
54/// (in meters) between two sets of coordinates, assuming those coordinates are in radians.
55fn haversine_dist(lat1: f64, lon1: f64, lat2: f64, lon2: f64) -> f64 {
56    let dlat = lat2 - lat1;
57    let dlon = lon2 - lon1;
58
59    let a = (dlat / 2.).sin().powi(2) + lat1.cos() * lat2.cos() * (dlon / 2.).sin().powi(2);
60    let c = 2. * a.sqrt().asin();
61    let earth_radius = 6371009.;
62
63    earth_radius * c
64}
65
66/// Get the distance between two nodes using the haversine distance.
67pub(super) fn node_dist(n1: &OSMNode, n2: &OSMNode) -> f64 {
68    haversine_dist(
69        n1.lat.to_radians(), n1.lon.to_radians(),
70        n2.lat.to_radians(), n2.lon.to_radians()
71    )
72}
73
74/// Given a json type structure, this function tries to parse all `OSMNodes` out of that json.
75pub fn get_osm_nodes(elements: &Vec<Element>) -> Result<Vec<OSMNode>, Box<dyn Error>> {
76
77    //Only get OSM elements that are nodes
78    let node_elements: Vec<OSMNode> = elements.into_iter()
79        .filter_map(|e| {
80            if let Element::Node { id, lat, lon, tags } = e {
81                Some(OSMNode { id: *id, lat: *lat, lon: *lon, tags: tags.clone() })
82            } else {
83                None
84            }
85        })
86        .collect();
87
88    Ok(node_elements)
89}
90
91/// Given a set of nodes and ways, this function tries to parse all `OSMNodes` that lie
92/// on one of the ways provided.
93pub fn filter_unconnected_nodes(ways: &Vec<OSMWay>, nodes: Vec<OSMNode>) -> Vec<OSMNode> {
94
95    //Create set of node ids
96    let mut node_ids: HashSet<u64> = HashSet::with_capacity(ways.len());
97    for way in ways {
98        for id in way.nodes().clone() {
99            node_ids.insert(id);
100        }
101    }
102
103    //Filter anything not in the hashset
104    nodes
105        .into_iter()
106        .filter(|node| node_ids.contains(&node.id))
107        .collect()
108}
109
110/// Given a json type structure and a `Vec<OSMWay>`, this function tries to
111/// parse all `OSMNodes` out of that json if and only if the node lies on one of the ways provided.
112pub fn get_nodes_from_ways(elements: &Vec<Element>, ways: &Vec<OSMWay>)
113    -> Result<Vec<OSMNode>, Box<dyn Error>> { 
114
115    //Create set of node ids
116    let mut node_ids: HashSet<u64> = HashSet::with_capacity(ways.len());
117    for way in ways {
118        for id in way.nodes().clone() {
119            node_ids.insert(id);
120        }
121    }
122
123    //Only get OSM elements that are nodes
124    let node_elements: Vec<OSMNode> = elements.clone().into_iter()
125        .filter_map(|e| {
126            if let Element::Node { id, lat, lon, tags } = e {
127
128                if node_ids.contains(&id) {
129                    Some(OSMNode { id, lat, lon, tags})
130                } else {
131                    None
132                }
133            } else {
134                None
135            }
136        })
137        .collect();
138
139    Ok(node_elements)
140}
141
142
143//This test is needed in this file since the havesine function is private to this module
144#[cfg(test)]
145mod haversine_tests {
146    use super::*;
147    
148    // Floating point tolerance
149    const EPSILON: f64 = 0.1;
150
151    fn approx_equal(a: f64, b: f64, epsilon: f64) -> bool {
152        (a - b).abs() < epsilon
153    }
154
155    #[test]
156    fn test_zero_distance() {
157        let (lat, lon): (f64, f64) = (52.5200, 13.4050);
158
159        let dist = haversine_dist(
160            lat.to_radians(),
161            lon.to_radians(),
162            lat.to_radians(),
163            lon.to_radians()
164        );
165        assert!(approx_equal(dist, 0.0, EPSILON));
166    }
167
168    #[test]
169    fn test_berlin_paris() {
170        let (lat1, lon1): (f64, f64) = (52.5200, 13.4050);
171        let (lat2, lon2): (f64, f64) = (48.8566, 2.3522);
172
173        let dist = haversine_dist(
174            lat1.to_radians(),
175            lon1.to_radians(),
176            lat2.to_radians(),
177            lon2.to_radians()
178        );
179        assert!(approx_equal(dist, 877464.57, EPSILON));
180    }
181
182    #[test]
183    fn test_new_york_los_angeles() {
184        let (lat1, lon1): (f64, f64) = (40.7128, -74.0060);
185        let (lat2, lon2): (f64, f64) = (34.0522, -118.2437);
186        
187        let dist = haversine_dist(
188            lat1.to_radians(),
189            lon1.to_radians(),
190            lat2.to_radians(),
191            lon2.to_radians()
192        );
193        assert!(approx_equal(dist, 3935751.81, EPSILON));
194    }
195
196    #[test]
197    fn test_poles_distance() {
198        let (lat1, lon1): (f64, f64) = (90.0, 0.0);
199        let (lat2, lon2): (f64, f64) = (-90.0, 0.0);
200        
201        let dist = haversine_dist(
202            lat1.to_radians(),
203            lon1.to_radians(),
204            lat2.to_radians(),
205            lon2.to_radians()
206        );
207        assert!(approx_equal(dist, 20015115.07, EPSILON));
208    }
209
210    #[test]
211    fn test_equator_distance() {
212        let (lat1, lon1): (f64, f64) = (0., 0.);
213        let (lat2, lon2): (f64, f64) = (0., 90.);
214
215        let dist = haversine_dist(
216            lat1.to_radians(),
217            lon1.to_radians(),
218            lat2.to_radians(),
219            lon2.to_radians()
220        );
221        // Should be quarter of the Earth's circumference
222        assert!(approx_equal(dist, 10007557.53, EPSILON));
223    }
224}
osmgraph/graph/node.rs

osmgraph/graph/
node.rs
