add hausdorff distance trait

georust · bors · Jul 31, 2023 · Jul 26, 2023 · Jul 27, 2023 · Jul 27, 2023
commit 1bd61e594641ea60df5f331875fb4df16d942b2c
diff --git a/geo/src/algorithm/hausdorff_distance.rs b/geo/src/algorithm/hausdorff_distance.rs
@@ -0,0 +1,194 @@
+use crate::GeoFloat;
+use crate::CoordsIter;
+use crate::algorithm::EuclideanDistance;
+use num_traits::Bounded; // used to have T as generic type in folding
+use geo_types::*;
+
+/// Determine the distance between two geometries using the [Hausdorff distance formula].
+///
+/// [haversine formula]: https://en.wikipedia.org/wiki/Hausdorff_distance
+pub trait HausdorffDistance<T, Rhs = Self> {
+    fn hausdorff_distance(&self, rhs: &Rhs) -> T;
+}
+
+// We can take advantage of the coords_iter() method for all geometries
+// to iterate across all combos of coords (infinum). Simplifies the 
+// implementations for all geometries.
+macro_rules! impl_hausdorff_distance_coord_iter {
+    ($from:ident, [$($to:ident),*]) => {
+        $(
+            impl<T> HausdorffDistance<T, $to<T>> for $from<T>
+            where
+                T: GeoFloat 
+            {
+                fn hausdorff_distance(&self, geom: &$to<T>) -> T {
+                    // calculate from A -> B 
+                    let hd1 = self
+                        .coords_iter()
+                        .map(|c| {
+                            geom
+                            .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 = geom
+                        .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)
+                }
+            }
+        )*
+    };
+}
+
+
+impl_hausdorff_distance_coord_iter!{
+    Line, 
+    [
+        Line, Rect, Triangle, Point, MultiPoint, 
+        LineString, MultiLineString, 
+        Polygon, MultiPolygon,
+        Geometry, GeometryCollection
+    ]
+}
+
+
+impl_hausdorff_distance_coord_iter!{
+    Triangle, 
+    [
+        Line, Rect, Triangle, Point, MultiPoint, 
+        LineString, MultiLineString, 
+        Polygon, MultiPolygon,
+        Geometry, GeometryCollection
+    ]
+}
+
+impl_hausdorff_distance_coord_iter!{
+    Rect, 
+    [
+        Line, Rect, Triangle, Point, MultiPoint, 
+        LineString, MultiLineString, 
+        Polygon, MultiPolygon,
+        Geometry, GeometryCollection
+    ]
+}
+
+impl_hausdorff_distance_coord_iter!{
+    Point, [
+        Line, Rect, Triangle, Point, MultiPoint, 
+        LineString, MultiLineString, 
+        Polygon, MultiPolygon,
+        Geometry, GeometryCollection
+    ]
+}
+
+impl_hausdorff_distance_coord_iter!{
+    LineString, [
+        Line, Rect, Triangle, Point, MultiPoint, 
+        LineString, MultiLineString, 
+        Polygon, MultiPolygon,
+        Geometry, GeometryCollection
+    ]
+}
+
+impl_hausdorff_distance_coord_iter!{
+    Polygon, [
+        Line, Rect, Triangle, Point, MultiPoint, 
+        LineString, MultiLineString, 
+        Polygon, MultiPolygon,
+        Geometry, GeometryCollection
+    ]
+}
+
+
+impl_hausdorff_distance_coord_iter!{
+    MultiPoint, [
+        Line, Rect, Triangle, Point, MultiPoint, 
+        LineString, MultiLineString, 
+        Polygon, MultiPolygon,
+        Geometry, GeometryCollection
+    ]
+}
+
+impl_hausdorff_distance_coord_iter!{
+    MultiLineString, [
+        Line, Rect, Triangle, Point, MultiPoint, 
+        LineString, MultiLineString, 
+        Polygon, MultiPolygon,
+        Geometry, GeometryCollection
+    ]
+}
+
+impl_hausdorff_distance_coord_iter!{
+    MultiPolygon, [
+        Line, Rect, Triangle, Point, MultiPoint, 
+        LineString, MultiLineString, 
+        Polygon, MultiPolygon,
+        Geometry, GeometryCollection
+    ]
+}
+
+impl_hausdorff_distance_coord_iter!{
+    GeometryCollection, [
+        Line, Rect, Triangle, Point, MultiPoint, 
+        LineString, MultiLineString, 
+        Polygon, MultiPolygon,
+        Geometry, GeometryCollection
+    ]
+}
+
+impl_hausdorff_distance_coord_iter!{
+    Geometry, [
+        Line, Rect, Triangle, Point, MultiPoint, 
+        LineString, MultiLineString, 
+        Polygon, MultiPolygon,
+        Geometry, GeometryCollection
+    ]
+}
+
+
+// ┌───────────────────────────┐
+// │ Implementations for Coord │
+// └───────────────────────────┘
+
+// since Coord does not have coords_iter() method we have 
+// to make a macro for it specifically
+macro_rules! impl_haussdorf_distance_coord {
+    ($($for:ident),*) => {
+        $(
+            impl<T> HausdorffDistance<T, $for<T>> for Coord<T>
+            where
+                T: GeoFloat 
+            {
+                fn hausdorff_distance(&self, geom: &$for<T>) -> T {
+                    let p = Point::from(*self);
+                    p.hausdorff_distance(geom)
+                }
+            }
+        )*
+    };
+}
+
+// Implement methods for all other geometries
+impl_haussdorf_distance_coord!(
+    Line, Rect, Triangle, 
+    Point, MultiPoint, 
+    LineString, MultiLineString, 
+    Polygon, MultiPolygon,
+    Geometry, GeometryCollection
+);
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
 //!