geometry_algorithm/
densify.rs

1//! `densify(g, max_distance)` — insert intermediate points so no
2//! segment exceeds `max_distance`.
3//!
4//! Mirrors `boost::geometry::densify(g_in, g_out, max_distance)` from
5//! `boost/geometry/algorithms/densify.hpp`. Boost takes the output
6//! through an out-parameter; the Rust port returns it by value.
7
8use geometry_strategy::{CartesianDensify, DensifyStrategy};
9
10/// Insert evenly-spaced intermediate vertices into `g` so that no
11/// output segment is longer than `max_distance`.
12///
13/// Mirrors `boost::geometry::densify` from
14/// `boost/geometry/algorithms/densify.hpp`. Straight-line
15/// interpolation only splits an edge — it never adds length — so the
16/// total length of the output equals that of the input.
17///
18/// # Panics
19///
20/// Panics if `max_distance` is not strictly positive (zero, negative,
21/// or NaN) — Boost throws `geometry::invalid_input_exception` for
22/// `max_distance <= 0` (`algorithms/densify.hpp`); the Rust port
23/// panics with a clear message.
24#[inline]
25#[must_use]
26pub fn densify<G>(g: &G, max_distance: f64) -> <CartesianDensify as DensifyStrategy<G>>::Output
27where
28    CartesianDensify: DensifyStrategy<G>,
29{
30    assert!(
31        max_distance > 0.0,
32        "densify: max_distance must be positive, got {max_distance} \
33         (Boost throws invalid_input_exception for max_distance <= 0)"
34    );
35    CartesianDensify.densify(g, max_distance)
36}
37
38#[cfg(test)]
39#[allow(
40    clippy::float_cmp,
41    reason = "Densified coordinates are exact literals."
42)]
43mod tests {
44    //! Reference from `boost/geometry/test/algorithms/densify.cpp:42-65`:
45    //! densification splits edges without changing total length, and no
46    //! output segment exceeds `max_distance`.
47
48    use super::densify;
49    use crate::{length, num_points};
50    use geometry_cs::Cartesian;
51    use geometry_model::{Linestring, Point2D, linestring};
52    use geometry_strategy::{DistanceStrategy, Pythagoras};
53
54    type Pt = Point2D<f64, Cartesian>;
55
56    #[test]
57    fn segment_of_length_10_max_2_5_yields_6_points() {
58        // Boost `densify.hpp`: `n = int(10 / 2.5) = 4` intermediate
59        // points → `n + 1 = 5` sub-segments of length 2 (< max 2.5).
60        let ls: Linestring<Pt> = linestring![(0., 0.), (10., 0.)];
61        let out = densify(&ls, 2.5);
62        assert_eq!(num_points(&out), 6);
63        let xs: alloc::vec::Vec<f64> = out.0.iter().map(geometry_trait::Point::get::<0>).collect();
64        assert_eq!(xs, alloc::vec![0.0, 2.0, 4.0, 6.0, 8.0, 10.0]);
65    }
66
67    #[test]
68    fn length_preserved_through_densify() {
69        let ls: Linestring<Pt> = linestring![(0., 0.), (3., 4.), (6., 0.)];
70        let original = length(&ls);
71        let out = densify(&ls, 1.0);
72        assert!((length(&out) - original).abs() < 1e-9);
73    }
74
75    #[test]
76    fn no_output_segment_exceeds_max_distance() {
77        let ls: Linestring<Pt> = linestring![(0., 0.), (10., 0.), (10., 7.)];
78        let out = densify(&ls, 1.0);
79        let pts: alloc::vec::Vec<&Pt> = geometry_trait::Linestring::points(&out).collect();
80        for w in pts.windows(2) {
81            assert!(Pythagoras.distance(w[0], w[1]) <= 1.0 + 1e-9);
82        }
83    }
84
85    #[test]
86    #[should_panic(expected = "max_distance must be positive")]
87    fn zero_max_distance_panics() {
88        let ls: Linestring<Pt> = linestring![(0., 0.), (10., 0.)];
89        let _ = densify(&ls, 0.0);
90    }
91
92    #[test]
93    #[should_panic(expected = "max_distance must be positive")]
94    fn negative_max_distance_panics() {
95        let ls: Linestring<Pt> = linestring![(0., 0.), (10., 0.)];
96        let _ = densify(&ls, -1.0);
97    }
98
99    #[test]
100    #[should_panic(expected = "max_distance must be positive")]
101    fn nan_max_distance_panics() {
102        let ls: Linestring<Pt> = linestring![(0., 0.), (10., 0.)];
103        let _ = densify(&ls, f64::NAN);
104    }
105}
geometry_algorithm/densify.rs

geometry_algorithm/
densify.rs
