Skip to main content

fprint_mindtct/detect/
line.rs

1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Straight-line pixel trajectories between two points — port of stock NBIS
6//! `mindtct/src/lib/mindtct/line.c` (`line_points`), used to walk the contiguous pixels a contour
7//! scan steps along (the basis for ridge counting and free-path tests).
8//!
9//! The walk is Bresenham-shaped but computed in `f64`: one axis advances by an integer `±1` each
10//! step while the other accumulates a fractional `x_factor` / `y_factor`. After every accumulation
11//! the running coordinate is quantized through [`trunc_dbl_precision`] at `1/16384`
12//! ([`TRUNC_SCALE`]) — this is what makes the trajectory identical on every architecture — and only
13//! then rounded to a pixel via the stock `(int)(r + 0.5)` cast. See `docs/mindtct-algorithm.md`
14//! §Bit-exactness.
15
16use crate::consts::TRUNC_SCALE;
17use crate::num::trunc_dbl_precision;
18
19/// Contiguous pixel coordinates of the line connecting `(x1, y1)` to `(x2, y2)`, endpoints included
20/// — port of stock `line_points` (`line.c` L82).
21///
22/// Returns the trajectory as an ordered `Vec<(x, y)>`; the stock out-parameters `ox_list`/`oy_list`
23/// (parallel arrays) and `onum` (count) collapse into this single structured value, with `onum`
24/// recovered as `.len()`.
25///
26/// # Algorithm (verbatim to `line.c`)
27///
28/// One axis is the *driving* axis (advances by `±1` each iteration); the other is *interpolated*
29/// from an `f64` accumulator. `inx`/`iny` select which axis drives (`inx = |dx| > |dy|`,
30/// `iny = |dy| > |dx|`; both `0` on the exact diagonal, where the walk steps `(±1, ±1)`), and
31/// `intx = 1 - iny` / `inty = 1 - inx` gate the integer vs. interpolated contribution to each new
32/// pixel. Per step (`L198`–`L213`):
33///
34/// 1. `rx += x_factor; ry += y_factor` (`L198`–`L199`).
35/// 2. `rx`, `ry` are [`trunc_dbl_precision`]-quantized at [`TRUNC_SCALE`] (`L203`–`L204`), stripping
36///    sub-`1/16384` noise so the following round is reproducible.
37/// 3. `ix = intx·(ix + x_incr) + iny·(int)(rx + 0.5)` and the mirror for `iy` (`L208`–`L209`). The
38///    `(int)(r + 0.5)` cast is a truncate-toward-zero of `r + 0.5` — *not* `sround`; it carries no
39///    negative-side `-0.5`, matching the stock exactly (image coordinates are non-negative).
40///
41/// The loop runs until `(ix, iy) == (x2, y2)`.
42///
43/// # Errors
44///
45/// `Err(-412)` if the point count would exceed the stock capacity bound
46/// `max(|x2-x1| + 2, |y2-y1| + 2)` — the `line.c` L191 "coord list overflow" guard, preserved
47/// verbatim. It is mathematically unreachable for the CASE 1/2/3 walks (each yields at most
48/// `max(|dx|, |dy|) + 1` points), but is kept to mirror stock bit-for-bit. The stock `malloc`
49/// failures (`-410`/`-411`, `L100`/`L106`) have no analogue here — `Vec` allocation is infallible in
50/// this context — and are elided.
51// PORT: stock `line_points` returns `int` (0 / negative). Here `Ok(list)` replaces the three out
52// parameters and `Err(code)` replaces the negative returns.
53pub(crate) fn line_points(x1: i32, y1: i32, x2: i32, y2: i32) -> Result<Vec<(i32, i32)>, i32> {
54    // PORT L95: maximum number of points needed to hold the segment (== stock malloc capacity).
55    let asize = (i32::abs(x2 - x1) + 2).max(i32::abs(y2 - y1) + 2);
56
57    // PORT L111–L112: delta x and y.
58    let dx = x2 - x1;
59    let dy = y2 - y1;
60
61    // PORT L115–L123: per-axis step direction (`+1` for a non-negative delta, else `-1`).
62    let x_incr = if dx >= 0 { 1 } else { -1 };
63    let y_incr = if dy >= 0 { 1 } else { -1 };
64
65    // PORT L126–L127: |DX| and |DY|.
66    let adx = i32::abs(dx);
67    let ady = i32::abs(dy);
68
69    // PORT L130–L139: axis orientation. `inx` set when X dominates, `iny` when Y dominates; both 0
70    // on the exact diagonal (|DX| == |DY|).
71    let inx = i32::from(adx > ady);
72    let iny = i32::from(ady > adx);
73
74    // PORT L160–L161: gates selecting the integer vs. interpolated contribution per axis.
75    let intx = 1 - iny;
76    let inty = 1 - inx;
77
78    // PORT L167: x_factor = (inx·x_incr) + (iny · DX / max(1, |DY|)).
79    let x_factor =
80        f64::from(inx * x_incr) + f64::from(iny) * (f64::from(dx) / f64::from(ady.max(1)));
81    // PORT L173: y_factor = (iny·y_incr) + (inx · DY / max(1, |DX|)).
82    let y_factor =
83        f64::from(iny * y_incr) + f64::from(inx) * (f64::from(dy) / f64::from(adx.max(1)));
84
85    // PORT L176–L180: integer and floating-point running coordinates seeded at the first point.
86    let mut ix = x1;
87    let mut iy = y1;
88    let mut rx = f64::from(x1);
89    let mut ry = f64::from(y1);
90
91    // PORT L98/L183–L187: allocate to `asize` and assign the first point.
92    let mut list: Vec<(i32, i32)> = Vec::with_capacity(asize.max(0) as usize);
93    list.push((x1, y1));
94
95    // PORT L189: walk until the integer coordinate reaches the second endpoint.
96    while ix != x2 || iy != y2 {
97        // PORT L191–L196: capacity guard (see the doc `Errors` note).
98        if list.len() as i32 >= asize {
99            return Err(-412);
100        }
101
102        // PORT L198–L199: accumulate the fractional step.
103        rx += x_factor;
104        ry += y_factor;
105
106        // PORT L203–L204: quantize so the round below is architecture-independent.
107        rx = trunc_dbl_precision(rx, TRUNC_SCALE);
108        ry = trunc_dbl_precision(ry, TRUNC_SCALE);
109
110        // PORT L208–L209: new pixel — driving axis by `±1`, interpolated axis by `(int)(r + 0.5)`.
111        ix = intx * (ix + x_incr) + iny * ((rx + 0.5) as i32);
112        iy = inty * (iy + y_incr) + inx * ((ry + 0.5) as i32);
113
114        // PORT L212–L213: append the point.
115        list.push((ix, iy));
116    }
117
118    // PORT L217–L222: structured return (out params + count collapse into `list`).
119    Ok(list)
120}
121
122#[cfg(test)]
123mod tests {
124    use super::*;
125
126    #[test]
127    fn single_point_when_endpoints_coincide() {
128        // Loop never runs: only the seed point is emitted.
129        assert_eq!(line_points(4, 7, 4, 7), Ok(vec![(4, 7)]));
130    }
131
132    #[test]
133    fn horizontal_line_steps_by_one_in_x() {
134        assert_eq!(
135            line_points(0, 2, 3, 2),
136            Ok(vec![(0, 2), (1, 2), (2, 2), (3, 2)])
137        );
138    }
139
140    #[test]
141    fn vertical_line_steps_by_one_in_y() {
142        assert_eq!(
143            line_points(5, 0, 5, 3),
144            Ok(vec![(5, 0), (5, 1), (5, 2), (5, 3)])
145        );
146    }
147
148    #[test]
149    fn exact_diagonal_steps_by_one_in_both() {
150        // |DX| == |DY|: CASE 3, both axes driven by their increments.
151        assert_eq!(
152            line_points(0, 0, 3, 3),
153            Ok(vec![(0, 0), (1, 1), (2, 2), (3, 3)])
154        );
155    }
156
157    #[test]
158    fn reversed_diagonal_walks_backwards() {
159        assert_eq!(
160            line_points(3, 3, 0, 0),
161            Ok(vec![(3, 3), (2, 2), (1, 1), (0, 0)])
162        );
163    }
164
165    #[test]
166    fn x_dominant_interpolates_y() {
167        // |DX| > |DY|: X drives by +1, Y interpolated via `(int)(ry + 0.5)`.
168        // Hand-traced against line.c: y_factor = 0.5.
169        assert_eq!(
170            line_points(0, 0, 4, 2),
171            Ok(vec![(0, 0), (1, 1), (2, 1), (3, 2), (4, 2)])
172        );
173    }
174
175    #[test]
176    fn endpoints_are_always_the_first_and_last_points() {
177        for &(x1, y1, x2, y2) in &[(2, 3, 9, 5), (9, 5, 2, 3), (-1, -2, 4, 7), (7, 1, 1, 8)] {
178            let pts = line_points(x1, y1, x2, y2).expect("no overflow for these segments");
179            assert_eq!(pts.first(), Some(&(x1, y1)));
180            assert_eq!(pts.last(), Some(&(x2, y2)));
181        }
182    }
183}