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#[cfg(test)]
46#[allow(
47    clippy::float_cmp,
48    reason = "Closest-point coordinates are exact for these inputs."
49)]
50mod tests {
51    //! Reference values mirror the point↔segment cases in
52    //! `boost/geometry/test/algorithms/closest_points/pl_l.cpp` and the
53    //! v1 `PointToSegment` distances (`test/strategies/projected_point.cpp`):
54    //! the distance between the returned closest points equals the
55    //! geometry-pair distance.
56
57    use super::closest_points;
58    use geometry_cs::Cartesian;
59    use geometry_model::{Linestring, Point2D, Segment};
60    use geometry_strategy::{DistanceStrategy, Pythagoras};
61    use geometry_trait::Point as _;
62
63    type Pt = Point2D<f64, Cartesian>;
64
65    #[test]
66    fn point_above_segment_drops_perpendicular() {
67        // (0,5) to segment (0,0)-(10,0) → closest pair ((0,5), (0,0)).
68        let p = Pt::new(0., 5.);
69        let s = Segment::new(Pt::new(0., 0.), Pt::new(10., 0.));
70        let (a, b) = closest_points(&p, &s);
71        assert_eq!((a.get::<0>(), a.get::<1>()), (0., 5.));
72        assert_eq!((b.get::<0>(), b.get::<1>()), (0., 0.));
73        assert!((Pythagoras.distance(&a, &b) - 5.0).abs() < 1e-12);
74    }
75
76    #[test]
77    fn point_on_segment_returns_input() {
78        let p = Pt::new(1., 1.);
79        let s = Segment::new(Pt::new(0., 0.), Pt::new(3., 3.));
80        let (a, b) = closest_points(&p, &s);
81        assert!(Pythagoras.distance(&a, &b) < 1e-12);
82    }
83
84    #[test]
85    fn crossing_segments_share_intersection_point() {
86        // Two crossing segments → the intersection point (1,1) on both.
87        let a = Segment::new(Pt::new(0., 0.), Pt::new(2., 2.));
88        let b = Segment::new(Pt::new(0., 2.), Pt::new(2., 0.));
89        let (ca, cb) = closest_points(&a, &b);
90        assert!((ca.get::<0>() - 1.0).abs() < 1e-12 && (ca.get::<1>() - 1.0).abs() < 1e-12);
91        assert!(Pythagoras.distance(&ca, &cb) < 1e-12);
92    }
93
94    #[test]
95    fn parallel_linestrings_closest_pair() {
96        // Two horizontal tracks 3 apart; nearest pair is vertically
97        // aligned, distance 3.
98        let a: Linestring<Pt> =
99            Linestring::from_vec(alloc::vec![Pt::new(0., 0.), Pt::new(10., 0.),]);
100        let b: Linestring<Pt> =
101            Linestring::from_vec(alloc::vec![Pt::new(2., 3.), Pt::new(8., 3.),]);
102        let (ca, cb) = closest_points(&a, &b);
103        assert!((Pythagoras.distance(&ca, &cb) - 3.0).abs() < 1e-9);
104    }
105
106    #[test]
107    #[should_panic(expected = "empty or degenerate linestring in closest_points")]
108    fn degenerate_linestring_panics() {
109        let a: Linestring<Pt> = Linestring::from_vec(alloc::vec![Pt::new(0., 0.)]);
110        let b: Linestring<Pt> =
111            Linestring::from_vec(alloc::vec![Pt::new(0., 0.), Pt::new(1., 0.),]);
112        let _ = closest_points(&a, &b);
113    }
114
115    /// Point × Point: the closest pair is trivially the two inputs.
116    #[test]
117    fn point_point_returns_the_inputs() {
118        let a = Pt::new(1., 2.);
119        let b = Pt::new(4., 6.);
120        let (ca, cb) = closest_points(&a, &b);
121        assert_eq!((ca.get::<0>(), ca.get::<1>()), (1., 2.));
122        assert_eq!((cb.get::<0>(), cb.get::<1>()), (4., 6.));
123        assert!((Pythagoras.distance(&ca, &cb) - 5.0).abs() < 1e-12);
124    }
125
126    /// Point × Point works in 3D too, exercising the `get_dim`/`set_dim`
127    /// (and `copy_point`) third-ordinate arm.
128    #[test]
129    fn point_point_in_three_dimensions() {
130        use geometry_model::Point3D;
131        type P3 = Point3D<f64, Cartesian>;
132        let a = P3::new(0., 0., 0.);
133        let b = P3::new(1., 2., 2.);
134        let (ca, cb) = closest_points(&a, &b);
135        assert_eq!((ca.get::<0>(), ca.get::<1>(), ca.get::<2>()), (0., 0., 0.));
136        assert_eq!((cb.get::<0>(), cb.get::<1>(), cb.get::<2>()), (1., 2., 2.));
137    }
138
139    /// Two parallel, non-crossing segments: the intersection test
140    /// returns `None`, so the closest pair falls out of the four endpoint
141    /// projections. Here the parallel offset is a constant 1 apart.
142    #[test]
143    fn parallel_segments_closest_pair_via_endpoint_projection() {
144        let a = Segment::new(Pt::new(0., 0.), Pt::new(4., 0.));
145        let b = Segment::new(Pt::new(0., 1.), Pt::new(4., 1.));
146        let (ca, cb) = closest_points(&a, &b);
147        assert!((Pythagoras.distance(&ca, &cb) - 1.0).abs() < 1e-12);
148    }
149
150    /// A degenerate (zero-length) segment drives the projection down its
151    /// `denominator <= 0` branch: the closest point is the segment's
152    /// start.
153    #[test]
154    fn degenerate_segment_projects_to_its_point() {
155        let p = Pt::new(3., 4.);
156        // start == end: a zero-length segment at the origin.
157        let s = Segment::new(Pt::new(0., 0.), Pt::new(0., 0.));
158        let (a, b) = closest_points(&p, &s);
159        assert_eq!((a.get::<0>(), a.get::<1>()), (3., 4.));
160        assert_eq!((b.get::<0>(), b.get::<1>()), (0., 0.));
161        assert!((Pythagoras.distance(&a, &b) - 5.0).abs() < 1e-12);
162    }
163
164    /// Linestring × Linestring: two disjoint parallel polylines. The
165    /// windowed double-loop keeps the minimum (the first-iteration seed
166    /// then the running-minimum update).
167    #[test]
168    fn linestring_linestring_closest_over_all_segment_pairs() {
169        use geometry_model::linestring;
170        let a: Linestring<Pt> = linestring![(0., 0.), (4., 0.)];
171        let b: Linestring<Pt> = linestring![(0., 3.), (4., 3.)];
172        let (ca, cb) = closest_points(&a, &b);
173        assert!((Pythagoras.distance(&ca, &cb) - 3.0).abs() < 1e-12);
174    }
175}
geometry_algorithm/closest_points.rs

geometry_algorithm/
closest_points.rs
