geo/algorithm/
frechet_distance.rs

1use crate::coords_iter::CoordsIter;
2use crate::euclidean_distance::EuclideanDistance;
3use crate::{GeoFloat, LineString, Point};
4use num_traits::FromPrimitive;
5
6/// Determine the similarity between two `LineStrings` using the [Frechet distance].
7///
8/// Based on [Computing Discrete Frechet Distance] by T. Eiter and H. Mannila.
9///
10/// [Frechet distance]: https://en.wikipedia.org/wiki/Fr%C3%A9chet_distance
11/// [Computing Discrete Frechet Distance]: http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf
12pub trait FrechetDistance<T, Rhs = Self> {
13    /// Determine the similarity between two `LineStrings` using the [Frechet distance].
14    ///
15    /// # Examples
16    ///
17    /// ```
18    /// use geo::FrechetDistance;
19    /// use geo::line_string;
20    ///
21    /// let line_string_a = line_string![
22    ///     (x: 1., y: 1.),
23    ///     (x: 2., y: 1.),
24    ///     (x: 2., y: 2.),
25    ///     (x: 3., y: 3.)
26    /// ];
27    ///
28    /// let line_string_b = line_string![
29    ///     (x: 2., y: 2.),
30    ///     (x: 0., y: 1.),
31    ///     (x: 2., y: 4.),
32    ///     (x: 3., y: 4.)
33    /// ];
34    ///
35    /// let distance = line_string_a.frechet_distance(&line_string_b);
36    ///
37    /// assert_eq!(2., distance);
38    /// ```
39    ///
40    /// [Frechet distance]: https://en.wikipedia.org/wiki/Fr%C3%A9chet_distance
41    fn frechet_distance(&self, rhs: &Rhs) -> T;
42}
43
44impl<T> FrechetDistance<T, LineString<T>> for LineString<T>
45where
46    T: GeoFloat + FromPrimitive,
47{
48    fn frechet_distance(&self, ls: &LineString<T>) -> T {
49        if self.coords_count() != 0 && ls.coords_count() != 0 {
50            let mut data = Data {
51                cache: vec![vec![T::nan(); ls.coords_count()]; self.coords_count()],
52                ls_a: self,
53                ls_b: ls,
54            };
55            data.compute(self.coords_count() - 1, ls.coords_count() - 1)
56        } else {
57            T::zero()
58        }
59    }
60}
61
62struct Data<'a, T>
63where
64    T: GeoFloat + FromPrimitive,
65{
66    cache: Vec<Vec<T>>,
67    ls_a: &'a LineString<T>,
68    ls_b: &'a LineString<T>,
69}
70
71impl<'a, T> Data<'a, T>
72where
73    T: GeoFloat + FromPrimitive,
74{
75    fn compute(&mut self, i: usize, j: usize) -> T {
76        if self.cache[i][j].is_nan() {
77            let eucl = Point::from(self.ls_a[i]).euclidean_distance(&Point::from(self.ls_b[j]));
78            self.cache[i][j] = match (i, j) {
79                (0, 0) => eucl,
80                (_, 0) => self.compute(i - 1, 0).max(eucl),
81                (0, _) => self.compute(0, j - 1).max(eucl),
82                (_, _) => ((self.compute(i - 1, j).min(self.compute(i - 1, j - 1)))
83                    .min(self.compute(i, j - 1)))
84                .max(eucl),
85            };
86        }
87        self.cache[i][j]
88    }
89}
90
91#[cfg(test)]
92mod test {
93    use crate::euclidean_distance::EuclideanDistance;
94    use crate::FrechetDistance;
95    use crate::LineString;
96
97    #[test]
98    fn test_single_point_in_linestring() {
99        let ls_a = LineString::from(vec![(1., 1.)]);
100        let ls_b = LineString::from(vec![(0., 2.)]);
101        assert_relative_eq!(
102            (ls_a.clone().into_points())[0].euclidean_distance(&(&ls_b.clone().into_points())[0]),
103            ls_a.frechet_distance(&ls_b)
104        );
105    }
106
107    #[test]
108    fn test_identical_linestrings() {
109        let ls_a = LineString::from(vec![(1., 1.), (2., 1.), (2., 2.)]);
110        let ls_b = LineString::from(vec![(1., 1.), (2., 1.), (2., 2.)]);
111        assert_relative_eq!(0., ls_a.frechet_distance(&ls_b));
112    }
113
114    #[test]
115    fn different_dimensions_linestrings() {
116        let ls_a = LineString::from(vec![(1., 1.)]);
117        let ls_b = LineString::from(vec![(2., 2.), (0., 1.)]);
118        assert_relative_eq!(2f64.sqrt(), ls_a.frechet_distance(&ls_b));
119    }
120
121    #[test]
122    fn test_frechet_1() {
123        let ls_a = LineString::from(vec![(1., 1.), (2., 1.)]);
124        let ls_b = LineString::from(vec![(2., 2.), (2., 3.)]);
125        assert_relative_eq!(2., ls_a.frechet_distance(&ls_b));
126    }
127
128    #[test]
129    fn test_frechet_2() {
130        let ls_a = LineString::from(vec![(1., 1.), (2., 1.), (2., 2.)]);
131        let ls_b = LineString::from(vec![(2., 2.), (0., 1.), (2., 4.)]);
132        assert_relative_eq!(2., ls_a.frechet_distance(&ls_b));
133    }
134}
geo/algorithm/frechet_distance.rs

geo/algorithm/
frechet_distance.rs
