1 use crate::{Bounds, Distance, Pt2D};
2 use aabb_quadtree::geom::{Point, Rect};
3 use aabb_quadtree::QuadTree;
4 use geo;
5 use geo::algorithm::contains::Contains;
6 use geo::prelude::{ClosestPoint, EuclideanDistance};
7 use std::collections::BTreeMap;
8
9 // TODO Maybe use https://crates.io/crates/spatial-join proximity maps
10
11 pub struct FindClosest<K> {
12 // TODO maybe any type of geo:: thing
13 geometries: BTreeMap<K, geo::LineString<f64>>,
14 quadtree: QuadTree<K>,
15 }
16
17 impl<K> FindClosest<K>
18 where
19 K: Clone + Ord + std::fmt::Debug,
20 {
new(bounds: &Bounds) -> FindClosest<K>21 pub fn new(bounds: &Bounds) -> FindClosest<K> {
22 FindClosest {
23 geometries: BTreeMap::new(),
24 quadtree: QuadTree::default(bounds.as_bbox()),
25 }
26 }
27
add(&mut self, key: K, pts: &Vec<Pt2D>)28 pub fn add(&mut self, key: K, pts: &Vec<Pt2D>) {
29 self.geometries.insert(key.clone(), pts_to_line_string(pts));
30 self.quadtree
31 .insert_with_box(key, Bounds::from(pts).as_bbox());
32 }
33
all_close_pts( &self, query_pt: Pt2D, max_dist_away: Distance, ) -> Vec<(K, Pt2D, Distance)>34 pub fn all_close_pts(
35 &self,
36 query_pt: Pt2D,
37 max_dist_away: Distance,
38 ) -> Vec<(K, Pt2D, Distance)> {
39 let query_geom = geo::Point::new(query_pt.x(), query_pt.y());
40 let query_bbox = Rect {
41 top_left: Point {
42 x: (query_pt.x() - max_dist_away.inner_meters()) as f32,
43 y: (query_pt.y() - max_dist_away.inner_meters()) as f32,
44 },
45 bottom_right: Point {
46 x: (query_pt.x() + max_dist_away.inner_meters()) as f32,
47 y: (query_pt.y() + max_dist_away.inner_meters()) as f32,
48 },
49 };
50
51 self.quadtree
52 .query(query_bbox)
53 .into_iter()
54 .filter_map(|(key, _, _)| {
55 if let geo::Closest::SinglePoint(pt) =
56 self.geometries[&key].closest_point(&query_geom)
57 {
58 let dist = Distance::meters(pt.euclidean_distance(&query_geom));
59 if dist <= max_dist_away {
60 Some((key.clone(), Pt2D::new(pt.x(), pt.y()), dist))
61 } else {
62 None
63 }
64 } else if self.geometries[&key].contains(&query_geom) {
65 // TODO Yay, FindClosest has a bug. :P
66 Some((key.clone(), query_pt, Distance::ZERO))
67 } else {
68 None
69 }
70 })
71 .collect()
72 }
73
74 // Finds the closest point on the existing geometry to the query pt.
closest_pt(&self, query_pt: Pt2D, max_dist_away: Distance) -> Option<(K, Pt2D)>75 pub fn closest_pt(&self, query_pt: Pt2D, max_dist_away: Distance) -> Option<(K, Pt2D)> {
76 self.all_close_pts(query_pt, max_dist_away)
77 .into_iter()
78 .min_by_key(|(_, _, dist)| *dist)
79 .map(|(k, pt, _)| (k, pt))
80 }
81 }
82
pts_to_line_string(raw_pts: &Vec<Pt2D>) -> geo::LineString<f64>83 fn pts_to_line_string(raw_pts: &Vec<Pt2D>) -> geo::LineString<f64> {
84 let pts: Vec<geo::Point<f64>> = raw_pts
85 .iter()
86 .map(|pt| geo::Point::new(pt.x(), pt.y()))
87 .collect();
88 pts.into()
89 }
90