Merge georust#1041

1041: Add Hausdorff Distance trait r=michaelkirk a=JosiahParry - [x] I agree to follow the project's [code of conduct](https://github.com/georust/geo/blob/main/CODE_OF_CONDUCT.md). - [x] I added an entry to `CHANGES.md` if knowledge of this change could be valuable to users. --- This PR adds a new trait `HausdorffDistance` which is implemented for all geometries. This is my first Rust library PR so I'll need some guidance getting this through the finish line! ### Outstanding questions for maintainers: - This PR is lacking tests. Should there be a test for each combo of geometry? - `CHANGES.md` does not have a development version listed, how should it be modified? - what amount of documentation is needed / suggested? Co-authored-by: Josiah Parry <josiah.parry@gmail.com>
thehappycheese · Jul 31, 2023 · eeb2b8e · eeb2b8e
2 parents d87fc54 + 17d4822
commit eeb2b8e
Show file tree

Hide file tree

Showing 4 changed files with 145 additions and 0 deletions.
diff --git a/geo/CHANGES.md b/geo/CHANGES.md
@@ -1,5 +1,9 @@
 # Changes
 
+## Development version
+
+* Add `HausdorffDistance` algorithm trait to calculate the Hausdorff distance between any two geometries. <https://github.com/georust/geo/pull/1041>
+
 ## 0.26.0
 
 * Implement "Closest Point" from a `Point` on a `Geometry` using spherical geometry. <https://github.com/georust/geo/pull/958>

diff --git a/geo/src/algorithm/hausdorff_distance.rs b/geo/src/algorithm/hausdorff_distance.rs
@@ -0,0 +1,136 @@
+use crate::algorithm::EuclideanDistance;
+use crate::CoordsIter;
+use crate::GeoFloat;
+use geo_types::{Coord, Point};
+use num_traits::Bounded;
+
+/// Determine the distance between two geometries using the [Hausdorff distance formula].
+///
+/// Hausdorff distance is used to compare two point sets. It measures the maximum euclidean
+/// distance of a point in one set to the nearest point in another set. Hausdorff distance
+/// is often used to measure the amount of mismatch between two sets.
+///
+/// [Hausdorff distance formula]: https://en.wikipedia.org/wiki/Hausdorff_distance
+
+pub trait HausdorffDistance<T>
+where
+    T: GeoFloat,
+{
+    fn hausdorff_distance<Rhs>(&self, rhs: &Rhs) -> T
+    where
+        Rhs: for<'a> CoordsIter<'a, Scalar = T>;
+}
+
+impl<T, G> HausdorffDistance<T> for G
+where
+    T: GeoFloat,
+    G: for<'a> CoordsIter<'a, Scalar = T>,
+{
+    fn hausdorff_distance<Rhs>(&self, rhs: &Rhs) -> T
+    where
+        Rhs: for<'a> CoordsIter<'a, Scalar = T>,
+    {
+        // calculate from A -> B
+        let hd1 = self
+            .coords_iter()
+            .map(|c| {
+                rhs.coords_iter()
+                    .map(|c2| c.euclidean_distance(&c2))
+                    .fold(<T as Bounded>::max_value(), |accum, val| accum.min(val))
+            })
+            .fold(<T as Bounded>::min_value(), |accum, val| accum.max(val));
+
+        // Calculate from B -> A
+        let hd2 = rhs
+            .coords_iter()
+            .map(|c| {
+                self.coords_iter()
+                    .map(|c2| c.euclidean_distance(&c2))
+                    .fold(<T as Bounded>::max_value(), |accum, val| accum.min(val))
+            })
+            .fold(<T as Bounded>::min_value(), |accum, val| accum.max(val));
+
+        // The max of the two
+        hd1.max(hd2)
+    }
+}
+
+// ┌───────────────────────────┐
+// │ Implementations for Coord │
+// └───────────────────────────┘
+
+impl<T> HausdorffDistance<T> for Coord<T>
+where
+    T: GeoFloat,
+{
+    fn hausdorff_distance<Rhs>(&self, rhs: &Rhs) -> T
+    where
+        Rhs: for<'a> CoordsIter<'a, Scalar = T>,
+    {
+        Point::from(*self).hausdorff_distance(rhs)
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use crate::HausdorffDistance;
+    use crate::{line_string, polygon, MultiPoint, MultiPolygon};
+
+    #[test]
+    fn hd_mpnt_mpnt() {
+        let p1: MultiPoint<_> = vec![(0., 0.), (1., 2.)].into();
+        let p2: MultiPoint<_> = vec![(2., 3.), (1., 2.)].into();
+        assert_relative_eq!(p1.hausdorff_distance(&p2), 2.236068, epsilon = 1.0e-6);
+    }
+
+    #[test]
+    fn hd_mpnt_poly() {
+        let p1: MultiPoint<_> = vec![(0., 0.), (1., 2.)].into();
+        let poly = polygon![
+        (x: 1., y: -3.1), (x: 3.7, y: 2.7),
+        (x: 0.9, y: 7.6), (x: -4.8, y: 6.7),
+        (x: -7.5, y: 0.9), (x: -4.7, y: -4.),
+        (x: 1., y: -3.1)
+        ];
+
+        assert_relative_eq!(p1.hausdorff_distance(&poly), 7.553807, epsilon = 1.0e-6)
+    }
+
+    #[test]
+    fn hd_mpnt_lns() {
+        let p1: MultiPoint<_> = vec![(0., 0.), (1., 2.)].into();
+        let lns = line_string![
+        (x: 1., y: -3.1), (x: 3.7, y: 2.7),
+        (x: 0.9, y: 7.6), (x: -4.8, y: 6.7),
+        (x: -7.5, y: 0.9), (x: -4.7, y: -4.),
+        (x: 1., y: -3.1)
+        ];
+
+        assert_relative_eq!(p1.hausdorff_distance(&lns), 7.553807, epsilon = 1.0e-6)
+    }
+
+    #[test]
+    fn hd_mpnt_mply() {
+        let p1: MultiPoint<_> = vec![(0., 0.), (1., 2.)].into();
+        let multi_polygon = MultiPolygon::new(vec![
+            polygon![
+              (x: 0.0f32, y: 0.0),
+              (x: 2.0, y: 0.0),
+              (x: 2.0, y: 1.0),
+              (x: 0.0, y: 1.0),
+            ],
+            polygon![
+              (x: 1.0, y: 1.0),
+              (x: -2.0, y: 1.0),
+              (x: -2.0, y: -1.0),
+              (x: 1.0, y: -1.0),
+            ],
+        ]);
+
+        assert_relative_eq!(
+            p1.hausdorff_distance(&multi_polygon),
+            2.236068,
+            epsilon = 1.0e-6
+        )
+    }
+}
diff --git a/geo/src/algorithm/mod.rs b/geo/src/algorithm/mod.rs
@@ -120,6 +120,10 @@ pub use geodesic_intermediate::GeodesicIntermediate;
 pub mod geodesic_length;
 pub use geodesic_length::GeodesicLength;
 
+/// Calculate the Hausdorff distance between two geometries.
+pub mod hausdorff_distance;
+pub use hausdorff_distance::HausdorffDistance;
+
 /// Calculate the bearing to another `Point`, in degrees.
 pub mod haversine_bearing;
 pub use haversine_bearing::HaversineBearing;

diff --git a/geo/src/lib.rs b/geo/src/lib.rs
@@ -45,6 +45,7 @@
 //!
 //! - **[`EuclideanDistance`](EuclideanDistance)**: Calculate the minimum euclidean distance between geometries
 //! - **[`GeodesicDistance`](GeodesicDistance)**: Calculate the minimum geodesic distance between geometries using the algorithm presented in _Algorithms for geodesics_ by Charles Karney (2013)
+//! - **[`HausdorffDistance`](HausdorffDistance)**: Calculate "the maximum of the distances from a point in any of the sets to the nearest point in the other set." (Rote, 1991)
 //! - **[`HaversineDistance`](HaversineDistance)**: Calculate the minimum geodesic distance between geometries using the haversine formula
 //! - **[`VincentyDistance`](VincentyDistance)**: Calculate the minimum geodesic distance between geometries using Vincenty’s formula
 //!