axiolid_evaluate/
polyline_length.rs

1//! Exact distance-to-parameter conversion for polylines.
2//!
3//! A polyline is the one refused family whose arc length is a finite
4//! sum rather than an integral: locating a distance is a running sum
5//! until the interval is found, then one linear interpolation. The
6//! only transcendental is the `sqrt` in each segment length, which
7//! `Line` already relies on and reports as `ArcLength3d`, so refusing
8//! the sequence while accepting each element was not defensible on
9//! exactness grounds (kernel#107).
10//!
11//! Three edges have a plausible-looking wrong answer, so each is
12//! pinned deliberately rather than left to fall out of the code:
13//!
14//! - A SEAM is two-valued. At an interior vertex the tangent jumps,
15//!   so this returns the parameter of the OUTGOING segment: a
16//!   distance that lands exactly on a vertex reads the heading the
17//!   curve is about to take, not the one it arrived with.
18//! - A ZERO-LENGTH segment (repeated identical points) has no
19//!   direction. Skipping it would silently change the
20//!   parameterisation, so it is refused instead.
21//! - A CLOSED polyline's wrap segment is real length and is
22//!   included, but distance still may not exceed the total: it is
23//!   clamped by refusal, never wrapped around.
24
25use axiolid_contracts::{GeomError, GeomResult};
26use axiolid_core::{Point3, Scalar};
27use axiolid_curve::Polyline3;
28
29/// Index pairs of the segments of `points`, honouring `closed`.
30fn spans(count: usize, closed: bool) -> Vec<(usize, usize)> {
31    if closed {
32        (0..count).map(|i| (i, (i + 1) % count)).collect()
33    } else {
34        (0..count.saturating_sub(1)).map(|i| (i, i + 1)).collect()
35    }
36}
37
38/// Total 3D length of `polyline`, or an error if any segment is
39/// degenerate or non-finite.
40pub fn polyline_length(polyline: &Polyline3) -> GeomResult<Scalar> {
41    let mut total = 0.0;
42    for (i, j) in spans(polyline.points.len(), polyline.closed) {
43        total += segment_length(polyline.points[i], polyline.points[j])?;
44    }
45    Ok(total)
46}
47
48/// Length of one segment, refusing the degenerate cases by name.
49fn segment_length(a: Point3, b: Point3) -> GeomResult<Scalar> {
50    let length = (b - a).length();
51    if !length.is_finite() {
52        return Err(GeomError::Degenerate(
53            "polyline segment has a non-finite length".to_string(),
54        ));
55    }
56    if length <= 0.0 {
57        return Err(GeomError::Degenerate(
58            "polyline has a zero-length segment, so distance along it is ambiguous".to_string(),
59        ));
60    }
61    Ok(length)
62}
63
64/// Convert a distance along `polyline` to its native parameter.
65///
66/// The parameter runs `[0, segment_count]` with the integer part
67/// selecting the segment, matching `curve::evaluate3`.
68pub fn polyline_parameter(polyline: &Polyline3, distance: Scalar) -> GeomResult<Scalar> {
69    let spans = spans(polyline.points.len(), polyline.closed);
70    if spans.is_empty() {
71        return Err(GeomError::Degenerate(format!(
72            "polyline with {} points has no evaluable segment",
73            polyline.points.len()
74        )));
75    }
76
77    // Every segment is measured up front so a degenerate one is
78    // refused even when the requested distance stops short of it:
79    // the curve is ill-defined as a whole, not just past that point.
80    let mut lengths = Vec::with_capacity(spans.len());
81    for (i, j) in &spans {
82        lengths.push(segment_length(polyline.points[*i], polyline.points[*j])?);
83    }
84    let total: Scalar = lengths.iter().sum();
85
86    if !distance.is_finite() || distance < 0.0 || distance > total {
87        return Err(GeomError::InvalidInput(format!(
88            "distance {distance} is outside the polyline's length [0, {total}]"
89        )));
90    }
91
92    // Running sum until the interval is found. Both `<` and `<=` yield the
93    // same parameter at a vertex (`t` lands exactly on the integer either
94    // way); what actually pins the seam is `polyline_span`'s `floor`, which
95    // sends an integral `t` to the segment STARTING there. `<=` is kept so
96    // the loop resolves a vertex distance without relying on the trailing
97    // fallback below.
98    let mut run = 0.0;
99    for (index, length) in lengths.iter().enumerate() {
100        if distance <= run + length {
101            let local = (distance - run) / length;
102            return Ok(index as Scalar + local);
103        }
104        run += length;
105    }
106
107    // Only reachable when rounding leaves `distance` a hair above
108    // the accumulated sum; the domain end is the exact answer.
109    Ok(spans.len() as Scalar)
110}
axiolid_evaluate/polyline_length.rs

axiolid_evaluate/
polyline_length.rs
