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}