geo/algorithm/
line_interpolate_point.rs

1use crate::coords_iter::CoordsIter;
2// This algorithm will be deprecated in the future, replaced by a unified implementation
3// rather than being Euclidean specific. Until the alternative is available, lets allow deprecations
4// so as not to change the method signature for existing users.
5#[allow(deprecated)]
6use crate::{CoordFloat, EuclideanLength, Line, LineString, Point};
7use std::ops::AddAssign;
8
9#[deprecated(
10    since = "0.30.0",
11    note = "use `line_string.point_at_ratio_from_start(&Euclidean, fraction)` instead"
12)]
13/// Returns an option of the point that lies a given fraction along the line.
14///
15/// If the given fraction is
16///  * less than zero (including negative infinity): returns a `Some`
17///    of the starting point
18///  * greater than one (including infinity): returns a `Some` of the ending point
19///
20///  If either the fraction is NaN, or any coordinates of the line are not
21///  finite, returns `None`.
22///
23/// # Examples
24///
25/// ```
26/// use geo::{LineString, point};
27/// use geo::LineInterpolatePoint;
28///
29/// let linestring: LineString = vec![
30///     [-1.0, 0.0],
31///     [0.0, 0.0],
32///     [0.0, 1.0]
33/// ].into();
34///
35/// assert_eq!(linestring.line_interpolate_point(-1.0), Some(point!(x: -1.0, y: 0.0)));
36/// assert_eq!(linestring.line_interpolate_point(0.25), Some(point!(x: -0.5, y: 0.0)));
37/// assert_eq!(linestring.line_interpolate_point(0.5), Some(point!(x: 0.0, y: 0.0)));
38/// assert_eq!(linestring.line_interpolate_point(0.75), Some(point!(x: 0.0, y: 0.5)));
39/// assert_eq!(linestring.line_interpolate_point(2.0), Some(point!(x: 0.0, y: 1.0)));
40/// ```
41pub trait LineInterpolatePoint<F: CoordFloat> {
42    type Output;
43
44    fn line_interpolate_point(&self, fraction: F) -> Self::Output;
45}
46
47#[allow(deprecated)]
48impl<T> LineInterpolatePoint<T> for Line<T>
49where
50    T: CoordFloat,
51{
52    type Output = Option<Point<T>>;
53
54    fn line_interpolate_point(&self, fraction: T) -> Self::Output {
55        if (fraction >= T::zero()) && (fraction <= T::one()) {
56            // fraction between 0 and 1, return a point between start and end
57            let diff = self.end - self.start;
58            let r = self.start + diff * (fraction);
59            if r.x.is_finite() && r.y.is_finite() {
60                Some(r.into())
61            } else {
62                None
63            }
64        } else if fraction < T::zero() {
65            // negative fractions are replaced with zero
66            self.line_interpolate_point(T::zero())
67        } else if fraction > T::one() {
68            // fractions above one are replaced with one
69            self.line_interpolate_point(T::one())
70        } else {
71            // fraction is nan
72            debug_assert!(fraction.is_nan());
73            None
74        }
75    }
76}
77
78#[allow(deprecated)]
79impl<T> LineInterpolatePoint<T> for LineString<T>
80where
81    T: CoordFloat + AddAssign + std::fmt::Debug,
82    Line<T>: EuclideanLength<T>,
83    LineString<T>: EuclideanLength<T>,
84{
85    type Output = Option<Point<T>>;
86
87    fn line_interpolate_point(&self, fraction: T) -> Self::Output {
88        if (fraction >= T::zero()) && (fraction <= T::one()) {
89            // find the point along the linestring which is fraction along it
90            let total_length = self.euclidean_length();
91            let fractional_length = total_length * fraction;
92            let mut cum_length = T::zero();
93            for segment in self.lines() {
94                let length = segment.euclidean_length();
95                if cum_length + length >= fractional_length {
96                    let segment_fraction = (fractional_length - cum_length) / length;
97                    return segment.line_interpolate_point(segment_fraction);
98                }
99                cum_length += length;
100            }
101            // either cum_length + length is never larger than fractional_length, i.e.
102            // fractional_length is nan, or the linestring has no lines to loop through
103            debug_assert!(fractional_length.is_nan() || (self.coords_count() == 0));
104            None
105        } else if fraction < T::zero() {
106            // negative fractions replaced with zero
107            self.line_interpolate_point(T::zero())
108        } else if fraction > T::one() {
109            // fractions above one replaced with one
110            self.line_interpolate_point(T::one())
111        } else {
112            // fraction is nan
113            debug_assert!(fraction.is_nan());
114            None
115        }
116    }
117}
118
119#[cfg(test)]
120mod test {
121    #![allow(deprecated)]
122
123    use super::*;
124    use crate::{coord, point};
125    use crate::{ClosestPoint, LineLocatePoint};
126    use num_traits::Float;
127
128    #[test]
129    fn test_line_interpolate_point_line() {
130        let line = Line::new(coord! { x: -1.0, y: 0.0 }, coord! { x: 1.0, y: 0.0 });
131        // some finite examples
132        assert_eq!(
133            line.line_interpolate_point(-1.0),
134            Some(point!(x: -1.0, y: 0.0))
135        );
136        assert_eq!(
137            line.line_interpolate_point(0.5),
138            Some(point!(x: 0.0, y: 0.0))
139        );
140        assert_eq!(
141            line.line_interpolate_point(0.75),
142            Some(point!(x: 0.5, y: 0.0))
143        );
144        assert_eq!(
145            line.line_interpolate_point(0.0),
146            Some(point!(x: -1.0, y: 0.0))
147        );
148        assert_eq!(
149            line.line_interpolate_point(1.0),
150            Some(point!(x: 1.0, y: 0.0))
151        );
152        assert_eq!(
153            line.line_interpolate_point(2.0),
154            Some(point!(x: 1.0, y: 0.0))
155        );
156
157        // fraction is nan or inf
158        assert_eq!(line.line_interpolate_point(Float::nan()), None);
159        assert_eq!(
160            line.line_interpolate_point(Float::infinity()),
161            Some(line.end_point())
162        );
163        assert_eq!(
164            line.line_interpolate_point(Float::neg_infinity()),
165            Some(line.start_point())
166        );
167
168        let line = Line::new(coord! { x: 0.0, y: 0.0 }, coord! { x: 1.0, y: 1.0 });
169        assert_eq!(
170            line.line_interpolate_point(0.5),
171            Some(point!(x: 0.5, y: 0.5))
172        );
173
174        // line contains nans or infs
175        let line = Line::new(
176            coord! {
177                x: Float::nan(),
178                y: 0.0,
179            },
180            coord! { x: 1.0, y: 1.0 },
181        );
182        assert_eq!(line.line_interpolate_point(0.5), None);
183
184        let line = Line::new(
185            coord! {
186                x: Float::infinity(),
187                y: 0.0,
188            },
189            coord! { x: 1.0, y: 1.0 },
190        );
191        assert_eq!(line.line_interpolate_point(0.5), None);
192
193        let line = Line::new(
194            coord! { x: 0.0, y: 0.0 },
195            coord! {
196                x: 1.0,
197                y: Float::infinity(),
198            },
199        );
200        assert_eq!(line.line_interpolate_point(0.5), None);
201
202        let line = Line::new(
203            coord! {
204                x: Float::neg_infinity(),
205                y: 0.0,
206            },
207            coord! { x: 1.0, y: 1.0 },
208        );
209        assert_eq!(line.line_interpolate_point(0.5), None);
210
211        let line = Line::new(
212            coord! { x: 0.0, y: 0.0 },
213            coord! {
214                x: 1.0,
215                y: Float::neg_infinity(),
216            },
217        );
218        assert_eq!(line.line_interpolate_point(0.5), None);
219    }
220
221    #[test]
222    fn test_line_interpolate_point_linestring() {
223        // some finite examples
224        let linestring: LineString = vec![[-1.0, 0.0], [0.0, 0.0], [1.0, 0.0]].into();
225        assert_eq!(
226            linestring.line_interpolate_point(0.0),
227            Some(point!(x: -1.0, y: 0.0))
228        );
229        assert_eq!(
230            linestring.line_interpolate_point(0.5),
231            Some(point!(x: 0.0, y: 0.0))
232        );
233        assert_eq!(
234            linestring.line_interpolate_point(1.0),
235            Some(point!(x: 1.0, y: 0.0))
236        );
237        assert_eq!(
238            linestring.line_interpolate_point(1.0),
239            linestring.line_interpolate_point(2.0)
240        );
241        assert_eq!(
242            linestring.line_interpolate_point(0.0),
243            linestring.line_interpolate_point(-2.0)
244        );
245
246        // fraction is nan or inf
247        assert_eq!(
248            linestring.line_interpolate_point(Float::infinity()),
249            linestring.points().last()
250        );
251        assert_eq!(
252            linestring.line_interpolate_point(Float::neg_infinity()),
253            linestring.points().next()
254        );
255        assert_eq!(linestring.line_interpolate_point(Float::nan()), None);
256
257        let linestring: LineString = vec![[-1.0, 0.0], [0.0, 0.0], [0.0, 1.0]].into();
258        assert_eq!(
259            linestring.line_interpolate_point(0.5),
260            Some(point!(x: 0.0, y: 0.0))
261        );
262        assert_eq!(
263            linestring.line_interpolate_point(1.5),
264            Some(point!(x: 0.0, y: 1.0))
265        );
266
267        // linestrings with nans/infs
268        let linestring: LineString = vec![[-1.0, 0.0], [0.0, Float::nan()], [0.0, 1.0]].into();
269        assert_eq!(linestring.line_interpolate_point(0.5), None);
270        assert_eq!(linestring.line_interpolate_point(1.5), None);
271        assert_eq!(linestring.line_interpolate_point(-1.0), None);
272
273        let linestring: LineString = vec![[-1.0, 0.0], [0.0, Float::infinity()], [0.0, 1.0]].into();
274        assert_eq!(linestring.line_interpolate_point(0.5), None);
275        assert_eq!(linestring.line_interpolate_point(1.5), None);
276        assert_eq!(linestring.line_interpolate_point(-1.0), None);
277
278        let linestring: LineString =
279            vec![[-1.0, 0.0], [0.0, Float::neg_infinity()], [0.0, 1.0]].into();
280        assert_eq!(linestring.line_interpolate_point(0.5), None);
281        assert_eq!(linestring.line_interpolate_point(1.5), None);
282        assert_eq!(linestring.line_interpolate_point(-1.0), None);
283
284        // Empty line
285        let coords: Vec<Point> = Vec::new();
286        let linestring: LineString = coords.into();
287        assert_eq!(linestring.line_interpolate_point(0.5), None);
288    }
289
290    #[test]
291    fn test_matches_closest_point() {
292        // line_locate_point should return the fraction to the closest point,
293        // so interpolating the line with that fraction should yield the closest point
294        let linestring: LineString = vec![[-1.0, 0.0], [0.5, 1.0], [1.0, 2.0]].into();
295        let pt = point!(x: 0.7, y: 0.7);
296        let frac = linestring
297            .line_locate_point(&pt)
298            .expect("Should result in fraction between 0 and 1");
299        let interpolated_point = linestring
300            .line_interpolate_point(frac)
301            .expect("Shouldn't return None");
302        let closest_point = linestring.closest_point(&pt);
303        match closest_point {
304            crate::Closest::SinglePoint(p) => assert_eq!(interpolated_point, p),
305            _ => panic!("The closest point should be a SinglePoint"), // example chosen to not be an intersection
306        };
307    }
308}