geometry_algorithm/
closest_points.rs

1//! `closest_points(&a, &b) -> (Point, Point)` — nearest-point pair.
2//!
3//! Mirrors `boost::geometry::closest_points(g1, g2, segment_out)` from
4//! `boost/geometry/algorithms/closest_points.hpp`. Boost returns the
5//! closest pair as a `Segment`; the Rust port returns a `(Point, Point)`
6//! tuple — same information, no `Segment::new` boilerplate at the call
7//! site. The first returned point lies on `a`, the second on `b`.
8//!
9//! v1 ships the Cartesian pairs the Boost test fixtures cover:
10//! point↔point, point↔segment, segment↔segment, and
11//! linestring↔linestring. The areal (polygon) pairs depend on overlay
12//! machinery and land in `phase_03`.
13
14use geometry_strategy::{CartesianClosestPoints, ClosestPointsStrategy};
15
16/// Return the pair of nearest points on `(a, b)` — `(pa, pb)` where
17/// `pa` lies on `a`, `pb` on `b`, and `|pa − pb|` is minimal.
18///
19/// Mirrors `boost::geometry::closest_points` from
20/// `boost/geometry/algorithms/closest_points.hpp`. The distance between
21/// the returned points equals the geometry-pair distance
22/// `distance(a, b)`.
23///
24/// # Panics
25///
26/// Panics if a linestring operand has fewer than 2 points — Boost
27/// treats empty input as an error (`empty_input_exception`); the
28/// Rust port panics with a clear message. Point and segment
29/// operands cannot be empty and never panic.
30#[inline]
31#[must_use]
32pub fn closest_points<A, B>(
33    a: &A,
34    b: &B,
35) -> (
36    <CartesianClosestPoints as ClosestPointsStrategy<A, B>>::Out,
37    <CartesianClosestPoints as ClosestPointsStrategy<A, B>>::Out,
38)
39where
40    CartesianClosestPoints: ClosestPointsStrategy<A, B>,
41{
42    CartesianClosestPoints.closest_points(a, b)
43}
44
45/// Return the nearest-point pair using an explicitly supplied strategy.
46#[inline]
47#[must_use]
48#[allow(
49    clippy::needless_pass_by_value,
50    reason = "closest-point strategies are zero-sized or small Copy values, matching other _with entries"
51)]
52pub fn closest_points_with<A, B, S>(a: &A, b: &B, strategy: S) -> (S::Out, S::Out)
53where
54    S: ClosestPointsStrategy<A, B>,
55{
56    strategy.closest_points(a, b)
57}
58
59#[cfg(test)]
60#[allow(
61    clippy::float_cmp,
62    reason = "Closest-point coordinates are exact for these inputs."
63)]
64mod tests {
65    //! Reference values mirror the point↔segment cases in
66    //! `boost/geometry/test/algorithms/closest_points/pl_l.cpp` and the
67    //! v1 `PointToSegment` distances (`test/strategies/projected_point.cpp`):
68    //! the distance between the returned closest points equals the
69    //! geometry-pair distance.
70
71    use super::closest_points;
72    use geometry_cs::Cartesian;
73    use geometry_model::{Linestring, Point2D, Segment};
74    use geometry_strategy::{DistanceStrategy, Pythagoras};
75    use geometry_trait::Point as _;
76
77    type Pt = Point2D<f64, Cartesian>;
78
79    #[test]
80    fn point_above_segment_drops_perpendicular() {
81        // (0,5) to segment (0,0)-(10,0) → closest pair ((0,5), (0,0)).
82        let p = Pt::new(0., 5.);
83        let s = Segment::new(Pt::new(0., 0.), Pt::new(10., 0.));
84        let (a, b) = closest_points(&p, &s);
85        assert_eq!((a.get::<0>(), a.get::<1>()), (0., 5.));
86        assert_eq!((b.get::<0>(), b.get::<1>()), (0., 0.));
87        assert!((Pythagoras.distance(&a, &b) - 5.0).abs() < 1e-12);
88    }
89
90    #[test]
91    fn point_on_segment_returns_input() {
92        let p = Pt::new(1., 1.);
93        let s = Segment::new(Pt::new(0., 0.), Pt::new(3., 3.));
94        let (a, b) = closest_points(&p, &s);
95        assert!(Pythagoras.distance(&a, &b) < 1e-12);
96    }
97
98    #[test]
99    fn crossing_segments_share_intersection_point() {
100        // Two crossing segments → the intersection point (1,1) on both.
101        let a = Segment::new(Pt::new(0., 0.), Pt::new(2., 2.));
102        let b = Segment::new(Pt::new(0., 2.), Pt::new(2., 0.));
103        let (ca, cb) = closest_points(&a, &b);
104        assert!((ca.get::<0>() - 1.0).abs() < 1e-12 && (ca.get::<1>() - 1.0).abs() < 1e-12);
105        assert!(Pythagoras.distance(&ca, &cb) < 1e-12);
106    }
107
108    #[test]
109    fn parallel_linestrings_closest_pair() {
110        // Two horizontal tracks 3 apart; nearest pair is vertically
111        // aligned, distance 3.
112        let a: Linestring<Pt> =
113            Linestring::from_vec(alloc::vec![Pt::new(0., 0.), Pt::new(10., 0.),]);
114        let b: Linestring<Pt> =
115            Linestring::from_vec(alloc::vec![Pt::new(2., 3.), Pt::new(8., 3.),]);
116        let (ca, cb) = closest_points(&a, &b);
117        assert!((Pythagoras.distance(&ca, &cb) - 3.0).abs() < 1e-9);
118    }
119
120    #[test]
121    #[should_panic(expected = "empty or degenerate linestring in closest_points")]
122    fn degenerate_linestring_panics() {
123        let a: Linestring<Pt> = Linestring::from_vec(alloc::vec![Pt::new(0., 0.)]);
124        let b: Linestring<Pt> =
125            Linestring::from_vec(alloc::vec![Pt::new(0., 0.), Pt::new(1., 0.),]);
126        let _ = closest_points(&a, &b);
127    }
128
129    /// Point × Point: the closest pair is trivially the two inputs.
130    #[test]
131    fn point_point_returns_the_inputs() {
132        let a = Pt::new(1., 2.);
133        let b = Pt::new(4., 6.);
134        let (ca, cb) = closest_points(&a, &b);
135        assert_eq!((ca.get::<0>(), ca.get::<1>()), (1., 2.));
136        assert_eq!((cb.get::<0>(), cb.get::<1>()), (4., 6.));
137        assert!((Pythagoras.distance(&ca, &cb) - 5.0).abs() < 1e-12);
138    }
139
140    /// Point × Point works in 3D too, exercising the `get_dim`/`set_dim`
141    /// (and `copy_point`) third-ordinate arm.
142    #[test]
143    fn point_point_in_three_dimensions() {
144        use geometry_model::Point3D;
145        type P3 = Point3D<f64, Cartesian>;
146        let a = P3::new(0., 0., 0.);
147        let b = P3::new(1., 2., 2.);
148        let (ca, cb) = closest_points(&a, &b);
149        assert_eq!((ca.get::<0>(), ca.get::<1>(), ca.get::<2>()), (0., 0., 0.));
150        assert_eq!((cb.get::<0>(), cb.get::<1>(), cb.get::<2>()), (1., 2., 2.));
151    }
152
153    /// Two parallel, non-crossing segments: the intersection test
154    /// returns `None`, so the closest pair falls out of the four endpoint
155    /// projections. Here the parallel offset is a constant 1 apart.
156    #[test]
157    fn parallel_segments_closest_pair_via_endpoint_projection() {
158        let a = Segment::new(Pt::new(0., 0.), Pt::new(4., 0.));
159        let b = Segment::new(Pt::new(0., 1.), Pt::new(4., 1.));
160        let (ca, cb) = closest_points(&a, &b);
161        assert!((Pythagoras.distance(&ca, &cb) - 1.0).abs() < 1e-12);
162    }
163
164    /// A degenerate (zero-length) segment drives the projection down its
165    /// `denominator <= 0` branch: the closest point is the segment's
166    /// start.
167    #[test]
168    fn degenerate_segment_projects_to_its_point() {
169        let p = Pt::new(3., 4.);
170        // start == end: a zero-length segment at the origin.
171        let s = Segment::new(Pt::new(0., 0.), Pt::new(0., 0.));
172        let (a, b) = closest_points(&p, &s);
173        assert_eq!((a.get::<0>(), a.get::<1>()), (3., 4.));
174        assert_eq!((b.get::<0>(), b.get::<1>()), (0., 0.));
175        assert!((Pythagoras.distance(&a, &b) - 5.0).abs() < 1e-12);
176    }
177
178    /// Linestring × Linestring: two disjoint parallel polylines. The
179    /// windowed double-loop keeps the minimum (the first-iteration seed
180    /// then the running-minimum update).
181    #[test]
182    fn linestring_linestring_closest_over_all_segment_pairs() {
183        use geometry_model::linestring;
184        let a: Linestring<Pt> = linestring![(0., 0.), (4., 0.)];
185        let b: Linestring<Pt> = linestring![(0., 3.), (4., 3.)];
186        let (ca, cb) = closest_points(&a, &b);
187        assert!((Pythagoras.distance(&ca, &cb) - 3.0).abs() < 1e-12);
188    }
189}
geometry_algorithm/closest_points.rs

geometry_algorithm/
closest_points.rs
