geometry_algorithm/
line_locate_point.rs

1//! Locate the closest point as a fraction of Cartesian linestring length.
2
3use alloc::vec::Vec;
4
5use geometry_cs::{CartesianFamily, CoordinateSystem};
6use geometry_model::Segment;
7use geometry_strategy::{
8    CartesianClosestPoints, ClosestPointsStrategy, DistanceStrategy, Pythagoras,
9};
10use geometry_tag::SameAs;
11use geometry_trait::{Linestring, Point, PointMut};
12
13/// Return the fractional arc-length position nearest to `point`.
14///
15/// Returns `None` for an empty linestring and `Some(0.0)` for a single-point or
16/// zero-length linestring. Ties retain the earliest position along the line.
17#[must_use]
18pub fn line_locate_point<L, P>(line: &L, point: &P) -> Option<f64>
19where
20    L: Linestring<Point = P>,
21    P: Point<Scalar = f64> + PointMut + Default + Copy,
22    <P::Cs as CoordinateSystem>::Family: SameAs<CartesianFamily>,
23    CartesianClosestPoints: ClosestPointsStrategy<P, Segment<P>, Out = P>,
24    Pythagoras: DistanceStrategy<P, P, Out = f64>,
25{
26    let points: Vec<P> = line.points().copied().collect();
27    if points.is_empty() {
28        return None;
29    }
30    if points.len() == 1 {
31        return Some(0.0);
32    }
33
34    let total: f64 = points
35        .windows(2)
36        .map(|edge| Pythagoras.distance(&edge[0], &edge[1]))
37        .sum();
38    if total == 0.0 {
39        return Some(0.0);
40    }
41
42    let mut elapsed = 0.0;
43    let mut best_distance = f64::INFINITY;
44    let mut best_position = 0.0;
45    for edge in points.windows(2) {
46        let segment = Segment::new(edge[0], edge[1]);
47        let (_, projected) = CartesianClosestPoints.closest_points(point, &segment);
48        let candidate_distance = Pythagoras.distance(point, &projected);
49        if candidate_distance < best_distance {
50            best_distance = candidate_distance;
51            best_position = elapsed + Pythagoras.distance(&edge[0], &projected);
52        }
53        elapsed += Pythagoras.distance(&edge[0], &edge[1]);
54    }
55    Some((best_position / total).clamp(0.0, 1.0))
56}
57
58#[cfg(test)]
59mod tests {
60    use super::line_locate_point;
61    use geometry_cs::Cartesian;
62    use geometry_model::{Linestring, Point2D};
63
64    type P = Point2D<f64, Cartesian>;
65
66    #[test]
67    fn empty_and_bent_lines_have_defined_results() {
68        assert_eq!(
69            line_locate_point(&Linestring::<P>::new(), &P::new(0.0, 0.0)),
70            None
71        );
72        let line = Linestring::from_vec(vec![P::new(0.0, 0.0), P::new(2.0, 0.0), P::new(2.0, 2.0)]);
73        assert_eq!(line_locate_point(&line, &P::new(2.5, 1.0)), Some(0.75));
74    }
75}
geometry_algorithm/line_locate_point.rs

geometry_algorithm/
line_locate_point.rs
