geo/algorithm/
hausdorff_distance.rs

1use crate::CoordsIter;
2use crate::GeoFloat;
3use crate::algorithm::{Distance, Euclidean};
4use geo_types::{Coord, Point};
5use num_traits::Bounded;
6
7/// Determine the distance between two geometries using the [Hausdorff distance formula].
8///
9/// Hausdorff distance is used to compare two point sets. It measures the maximum euclidean
10/// distance of a point in one set to the nearest point in another set. Hausdorff distance
11/// is often used to measure the amount of mismatch between two sets.
12///
13/// [Hausdorff distance formula]: https://en.wikipedia.org/wiki/Hausdorff_distance
14pub trait HausdorffDistance<T>
15where
16    T: GeoFloat,
17{
18    fn hausdorff_distance<Rhs>(&self, rhs: &Rhs) -> T
19    where
20        Rhs: CoordsIter<Scalar = T>;
21}
22
23impl<T, G> HausdorffDistance<T> for G
24where
25    T: GeoFloat,
26    G: CoordsIter<Scalar = T>,
27{
28    fn hausdorff_distance<Rhs>(&self, rhs: &Rhs) -> T
29    where
30        Rhs: CoordsIter<Scalar = T>,
31    {
32        // calculate from A -> B
33        let hd1 = self
34            .coords_iter()
35            .map(|c| {
36                rhs.coords_iter()
37                    .map(|c2| Euclidean.distance(c, c2))
38                    .fold(<T as Bounded>::max_value(), |accum, val| accum.min(val))
39            })
40            .fold(<T as Bounded>::min_value(), |accum, val| accum.max(val));
41
42        // Calculate from B -> A
43        let hd2 = rhs
44            .coords_iter()
45            .map(|c| {
46                self.coords_iter()
47                    .map(|c2| Euclidean.distance(c, c2))
48                    .fold(<T as Bounded>::max_value(), |accum, val| accum.min(val))
49            })
50            .fold(<T as Bounded>::min_value(), |accum, val| accum.max(val));
51
52        // The max of the two
53        hd1.max(hd2)
54    }
55}
56
57// ┌───────────────────────────┐
58// │ Implementations for Coord │
59// └───────────────────────────┘
60
61impl<T> HausdorffDistance<T> for Coord<T>
62where
63    T: GeoFloat,
64{
65    fn hausdorff_distance<Rhs>(&self, rhs: &Rhs) -> T
66    where
67        Rhs: CoordsIter<Scalar = T>,
68    {
69        Point::from(*self).hausdorff_distance(rhs)
70    }
71}
72
73#[cfg(test)]
74mod test {
75    use crate::HausdorffDistance;
76    use crate::{MultiPoint, MultiPolygon, line_string, polygon};
77
78    #[test]
79    fn hd_mpnt_mpnt() {
80        let p1: MultiPoint<_> = vec![(0., 0.), (1., 2.)].into();
81        let p2: MultiPoint<_> = vec![(2., 3.), (1., 2.)].into();
82        assert_relative_eq!(p1.hausdorff_distance(&p2), 2.236068, epsilon = 1.0e-6);
83    }
84
85    #[test]
86    fn hd_mpnt_poly() {
87        let p1: MultiPoint<_> = vec![(0., 0.), (1., 2.)].into();
88        let poly = polygon![
89        (x: 1., y: -3.1), (x: 3.7, y: 2.7),
90        (x: 0.9, y: 7.6), (x: -4.8, y: 6.7),
91        (x: -7.5, y: 0.9), (x: -4.7, y: -4.),
92        (x: 1., y: -3.1)
93        ];
94
95        assert_relative_eq!(p1.hausdorff_distance(&poly), 7.553807, epsilon = 1.0e-6)
96    }
97
98    #[test]
99    fn hd_mpnt_lns() {
100        let p1: MultiPoint<_> = vec![(0., 0.), (1., 2.)].into();
101        let lns = line_string![
102        (x: 1., y: -3.1), (x: 3.7, y: 2.7),
103        (x: 0.9, y: 7.6), (x: -4.8, y: 6.7),
104        (x: -7.5, y: 0.9), (x: -4.7, y: -4.),
105        (x: 1., y: -3.1)
106        ];
107
108        assert_relative_eq!(p1.hausdorff_distance(&lns), 7.553807, epsilon = 1.0e-6)
109    }
110
111    #[test]
112    fn hd_mpnt_mply() {
113        let p1: MultiPoint<_> = vec![(0., 0.), (1., 2.)].into();
114        let multi_polygon = MultiPolygon::new(vec![
115            polygon![
116              (x: 0.0f32, y: 0.0),
117              (x: 2.0, y: 0.0),
118              (x: 2.0, y: 1.0),
119              (x: 0.0, y: 1.0),
120            ],
121            polygon![
122              (x: 1.0, y: 1.0),
123              (x: -2.0, y: 1.0),
124              (x: -2.0, y: -1.0),
125              (x: 1.0, y: -1.0),
126            ],
127        ]);
128
129        assert_relative_eq!(
130            p1.hausdorff_distance(&multi_polygon),
131            2.236068,
132            epsilon = 1.0e-6
133        )
134    }
135}
geo/algorithm/hausdorff_distance.rs

geo/algorithm/
hausdorff_distance.rs
