geometry_algorithm/
discrete_hausdorff.rs

1//! `discrete_hausdorff_distance(&l1, &l2)` — sup-sup distance over
2//! vertex sets.
3//!
4//! Mirrors `boost::geometry::discrete_hausdorff_distance` from
5//! `boost/geometry/algorithms/discrete_hausdorff_distance.hpp`. The
6//! Boost overload is *directed* — `max_{p ∈ A} min_{q ∈ B} dist(p, q)`,
7//! walking the first geometry's vertices only — and the Rust port
8//! matches; the symmetric Hausdorff distance is `max(d(A, B), d(B, A))`
9//! and is the caller's to compose. `O(m × n)` time, `O(1)` space.
10
11use alloc::vec::Vec;
12
13use geometry_cs::CoordinateSystem;
14use geometry_strategy::distance::DefaultDistance;
15use geometry_strategy::{DefaultDistanceStrategy, DistanceStrategy};
16use geometry_trait::{Geometry, Linestring, Point};
17
18/// Shorthand for the coordinate-system family of a point type.
19type Family<P> = <<P as Point>::Cs as CoordinateSystem>::Family;
20
21/// The scalar output type of the default distance strategy between the
22/// point types of two linestrings.
23type DefaultDistOut<L1, L2> = <DefaultDistanceStrategy<
24    <L1 as Geometry>::Point,
25    <L2 as Geometry>::Point,
26> as DistanceStrategy<<L1 as Geometry>::Point, <L2 as Geometry>::Point>>::Out;
27
28/// Directed discrete Hausdorff distance from `l1` to `l2`, using the
29/// default distance strategy for their coordinate systems.
30///
31/// Mirrors `boost::geometry::discrete_hausdorff_distance(l1, l2)` from
32/// `boost/geometry/algorithms/discrete_hausdorff_distance.hpp`.
33///
34/// # Panics
35///
36/// Panics on an empty linestring — Boost treats empty input as an
37/// error; the Rust port panics with a clear message.
38#[inline]
39#[must_use]
40pub fn discrete_hausdorff_distance<L1, L2>(l1: &L1, l2: &L2) -> DefaultDistOut<L1, L2>
41where
42    L1: Linestring,
43    L2: Linestring,
44    Family<L1::Point>: DefaultDistance<Family<L2::Point>>,
45    DefaultDistanceStrategy<L1::Point, L2::Point>: DistanceStrategy<L1::Point, L2::Point> + Default,
46{
47    let s = <DefaultDistanceStrategy<L1::Point, L2::Point>>::default();
48    discrete_hausdorff_distance_with(l1, l2, s)
49}
50
51/// Directed discrete Hausdorff distance from `l1` to `l2` using an
52/// explicit distance strategy `dist`.
53///
54/// Mirrors the strategy-taking `boost::geometry::discrete_hausdorff_distance`
55/// overload from
56/// `boost/geometry/algorithms/discrete_hausdorff_distance.hpp`: the
57/// supremum over `l1`'s vertices of the distance to the nearest vertex
58/// of `l2`.
59///
60/// # Panics
61///
62/// Panics if either linestring is empty.
63#[must_use]
64#[allow(
65    clippy::needless_pass_by_value,
66    reason = "Distance strategies are zero-sized/Copy; taking by value matches `distance_with`."
67)]
68pub fn discrete_hausdorff_distance_with<L1, L2, S>(l1: &L1, l2: &L2, dist: S) -> S::Out
69where
70    L1: Linestring,
71    L2: Linestring,
72    S: DistanceStrategy<L1::Point, L2::Point>,
73    S::Out: PartialOrd + Copy,
74{
75    let seq1: Vec<&L1::Point> = l1.points().collect();
76    let seq2: Vec<&L2::Point> = l2.points().collect();
77    assert!(
78        !seq1.is_empty() && !seq2.is_empty(),
79        "empty linestring in discrete_hausdorff"
80    );
81
82    // directed(A, B): outer over `seq1` (L1 points), inner over `seq2`.
83    directed_sup(&seq1, &seq2, |p, q| dist.distance(p, q))
84}
85
86/// Directed supremum `max_{p ∈ a} min_{q ∈ b} f(p, q)`.
87fn directed_sup<PA, PB, O, F>(a: &[&PA], b: &[&PB], mut f: F) -> O
88where
89    O: PartialOrd + Copy,
90    F: FnMut(&PA, &PB) -> O,
91{
92    let mut sup: Option<O> = None;
93    for p in a {
94        let mut inf: Option<O> = None;
95        for q in b {
96            let d = f(p, q);
97            inf = Some(match inf {
98                None => d,
99                Some(cur) => {
100                    if d < cur {
101                        d
102                    } else {
103                        cur
104                    }
105                }
106            });
107        }
108        let inf = inf.expect("non-empty inner sequence");
109        sup = Some(match sup {
110            None => inf,
111            Some(cur) => {
112                if inf > cur {
113                    inf
114                } else {
115                    cur
116                }
117            }
118        });
119    }
120    sup.expect("non-empty outer sequence")
121}
122
123#[cfg(test)]
124#[allow(
125    clippy::float_cmp,
126    reason = "Hausdorff reference values compared with an epsilon."
127)]
128mod tests {
129    //! Reference values from
130    //! `boost/geometry/test/algorithms/similarity/discrete_hausdorff_distance.cpp`.
131
132    use super::discrete_hausdorff_distance;
133    use geometry_cs::Cartesian;
134    use geometry_model::{Linestring, Point2D, linestring};
135
136    type Pt = Point2D<f64, Cartesian>;
137
138    #[test]
139    fn identical_linestrings_distance_zero() {
140        let ls: Linestring<Pt> = linestring![(0., 0.), (1., 0.), (2., 0.)];
141        assert!(discrete_hausdorff_distance(&ls, &ls) < 1e-12);
142    }
143
144    /// Subset case: dropping the last vertex — the Hausdorff distance is
145    /// the distance from the dropped vertex `(2,0)` to its nearest kept
146    /// neighbour `(1,0)`, i.e. 1.
147    #[test]
148    fn subset_drops_last_vertex() {
149        let a: Linestring<Pt> = linestring![(0., 0.), (1., 0.), (2., 0.)];
150        let b: Linestring<Pt> = linestring![(0., 0.), (1., 0.)];
151        assert!((discrete_hausdorff_distance(&a, &b) - 1.0).abs() < 1e-9);
152    }
153
154    /// Parallel tracks 1 unit apart with aligned endpoints → 1.
155    #[test]
156    fn parallel_lines() {
157        let a: Linestring<Pt> = linestring![(0., 0.), (5., 0.)];
158        let b: Linestring<Pt> = linestring![(0., 1.), (5., 1.)];
159        assert!((discrete_hausdorff_distance(&a, &b) - 1.0).abs() < 1e-9);
160    }
161
162    /// The distance is directed, as Boost's is: the longer line's far
163    /// vertex is one unit from the shorter line, while every vertex of the
164    /// shorter line lies on the longer one.
165    #[test]
166    fn directed_distance_depends_on_argument_order() {
167        let a: Linestring<Pt> = linestring![(0., 0.), (1., 0.), (2., 0.)];
168        let b: Linestring<Pt> = linestring![(0., 0.), (1., 0.)];
169        assert_eq!(discrete_hausdorff_distance(&a, &b), 1.0);
170        assert_eq!(discrete_hausdorff_distance(&b, &a), 0.0);
171    }
172
173    /// Boost's overload is directed: every vertex of the straight line
174    /// coincides with a vertex of the bent one (0), while the bent line's
175    /// apex is √34 from the nearest vertex of the straight one.
176    #[test]
177    fn matches_boost_directed_value() {
178        let a: Linestring<Pt> = linestring![(0.0, 0.0), (10.0, 0.0)];
179        let b: Linestring<Pt> = linestring![(0.0, 0.0), (5.0, 3.0), (10.0, 0.0)];
180        assert!(discrete_hausdorff_distance(&a, &b).abs() < 1e-12);
181        assert!((discrete_hausdorff_distance(&b, &a) - 34.0_f64.sqrt()).abs() < 1e-12);
182    }
183}
geometry_algorithm/discrete_hausdorff.rs

geometry_algorithm/
discrete_hausdorff.rs
