Skip to main content

fprint_mindtct/
util.rs

1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Shared arithmetic and geometry helpers ported from stock NBIS `mindtct/src/lib/mindtct/util.c`.
6//!
7//! These small routines have a single stock origin (`util.c`) but several consumers across the
8//! pipeline — detection ([`squared_distance`] in `detect/loops.rs`), false-minutia removal
9//! ([`distance`], [`squared_distance`], [`closest_dir_dist`], [`minmaxs`] in `remove.rs`) and
10//! ridge counting ([`squared_distance`], [`angle2line`], [`find_incr_position_dbl`] in `ridges.rs`).
11//! Collecting them here keeps that one origin in one place rather than re-copied per consumer.
12//!
13//! Each is a verbatim transcription: the `f64` arithmetic (subtraction, squaring, `atan2`, `sqrt`)
14//! matches the reference bit-for-bit. See `docs/mindtct-algorithm.md` §Bit-exactness.
15
16/// Stock `INVALID_DIR` (`lfs.h` L320): a direction that could not be determined.
17const INVALID_DIR: i32 = -1;
18
19/// Stock `MIN_SLOPE_DELTA` (`lfs.h` L701): below this per-axis delta a line is treated as having zero
20/// slope in [`angle2line`], avoiding a degenerate `atan2(0, 0)`.
21const MIN_SLOPE_DELTA: f64 = 0.5;
22
23/// Euclidean distance between two integer points — port of stock `distance` (`util.c` L358).
24pub(crate) fn distance(x1: i32, y1: i32, x2: i32, y2: i32) -> f64 {
25    // PORT L363–L369: sqrt of the squared distance.
26    let dx = f64::from(x1 - x2);
27    let dy = f64::from(y1 - y2);
28    ((dx * dx) + (dy * dy)).sqrt()
29}
30
31/// Squared Euclidean distance between two integer points — port of stock `squared_distance`
32/// (`util.c` L388).
33pub(crate) fn squared_distance(x1: i32, y1: i32, x2: i32, y2: i32) -> f64 {
34    // PORT L393–L397: (x1-x2)^2 + (y1-y2)^2, computed in `f64`.
35    let dx = f64::from(x1 - x2);
36    let dy = f64::from(y1 - y2);
37    (dx * dx) + (dy * dy)
38}
39
40/// Inner (wrap-aware) distance between two integer directions — port of stock `closest_dir_dist`
41/// (`util.c` L602).
42///
43/// Returns [`INVALID_DIR`] if either direction is invalid (`< 0`), else the smaller of the direct and
44/// wrap-around distances on a circle of `ndirs` directions.
45pub(crate) fn closest_dir_dist(dir1: i32, dir2: i32, ndirs: i32) -> i32 {
46    // PORT L607–L618: only defined for two valid directions.
47    if dir1 >= 0 && dir2 >= 0 {
48        let d1 = (dir2 - dir1).abs();
49        let d2 = ndirs - d1;
50        d1.min(d2)
51    } else {
52        INVALID_DIR
53    }
54}
55
56/// Compute the angle (radians) of the line from `(fx, fy)` to `(tx, ty)` — port of stock `angle2line`
57/// (`util.c` L519).
58///
59/// The slope is measured as `dy = fy - ty`, `dx = tx - fx` (the reference's asymmetric subtraction
60/// order, verbatim); when both deltas fall below [`MIN_SLOPE_DELTA`] the angle is `0.0`.
61pub(crate) fn angle2line(fx: i32, fy: i32, tx: i32, ty: i32) -> f64 {
62    // PORT L523–L525: slope components (mixed subtraction order is intentional).
63    let dy = f64::from(fy - ty);
64    let dx = f64::from(tx - fx);
65    // PORT L527–L532: sufficiently flat → 0.0, else the arctangent of the slope.
66    if dx.abs() < MIN_SLOPE_DELTA && dy.abs() < MIN_SLOPE_DELTA {
67        0.0
68    } else {
69        dy.atan2(dx)
70    }
71}
72
73/// Insertion point for `val` in an increasing-sorted `list` — port of stock `find_incr_position_dbl`
74/// (`util.c` L485).
75///
76/// Returns the first index whose value exceeds `val` (preserving increasing order), or `list.len()`
77/// when `val` is `>=` every element.
78pub(crate) fn find_incr_position_dbl(val: f64, list: &[f64]) -> usize {
79    // PORT L489–L499: first slot whose value is strictly greater than `val`.
80    for (i, &v) in list.iter().enumerate() {
81        if val < v {
82            return i;
83        }
84    }
85    // PORT L503: never smaller → append at the end.
86    list.len()
87}
88
89/// The three parallel outputs of [`minmaxs`] — value, type (`-1` minima / `+1` maxima) and index of
90/// each relative extremum.
91pub(crate) struct MinMaxs {
92    pub(crate) val: Vec<i32>,
93    pub(crate) kind: Vec<i32>,
94    pub(crate) idx: Vec<i32>,
95}
96
97/// Locate relative minima and maxima in a vector of integers — port of stock `minmaxs` (`util.c`
98/// L158).
99///
100/// Walks the run-length structure of the sequence, recording each turning point at the midpoint of the
101/// level run that precedes it. Fewer than three items yields no extrema.
102pub(crate) fn minmaxs(items: &[i32]) -> MinMaxs {
103    let num = items.len() as i32;
104
105    // PORT L168–L174: fewer than three items → no min/max possible.
106    if num < 3 {
107        return MinMaxs {
108            val: Vec::new(),
109            kind: Vec::new(),
110            idx: Vec::new(),
111        };
112    }
113
114    let mut val = Vec::new();
115    let mut kind = Vec::new();
116    let mut idx = Vec::new();
117
118    // PORT L204–L219: initial state from the first pair; start location at the first item.
119    let mut i: i32 = 0;
120    let diff = items[1] - items[0];
121    let mut state = if diff > 0 {
122        1
123    } else if diff < 0 {
124        -1
125    } else {
126        0
127    };
128    let mut start: i32 = 0;
129    i += 1;
130
131    // PORT L222–L332: fold each successive item pair into the running state.
132    while i < num - 1 {
133        let diff = items[(i + 1) as usize] - items[i as usize];
134        if diff > 0 {
135            // PORT L227–L275: increasing.
136            if state == 1 {
137                start = i;
138            } else if state == -1 {
139                // PORT L234–L248: a minima at the midpoint of the preceding decline.
140                let loc = (start + i) / 2;
141                val.push(items[loc as usize]);
142                kind.push(-1);
143                idx.push(loc);
144                state = 1;
145                start = i;
146            } else {
147                // PORT L251–L274: previously level (only at the list head).
148                if i - start > 1 {
149                    let loc = (start + i) / 2;
150                    val.push(items[loc as usize]);
151                    kind.push(-1);
152                    idx.push(loc);
153                }
154                state = 1;
155                start = i;
156            }
157        } else if diff < 0 {
158            // PORT L278–L326: decreasing.
159            if state == -1 {
160                start = i;
161            } else if state == 1 {
162                // PORT L285–L298: a maxima at the midpoint of the preceding rise.
163                let loc = (start + i) / 2;
164                val.push(items[loc as usize]);
165                kind.push(1);
166                idx.push(loc);
167                state = -1;
168                start = i;
169            } else {
170                // PORT L302–L325: previously level (only at the list head).
171                if i - start > 1 {
172                    let loc = (start + i) / 2;
173                    val.push(items[loc as usize]);
174                    kind.push(1);
175                    idx.push(loc);
176                }
177                state = -1;
178                start = i;
179            }
180        }
181        // PORT L328: level items just advance.
182        i += 1;
183    }
184
185    MinMaxs { val, kind, idx }
186}
187
188#[cfg(test)]
189mod tests {
190    use super::*;
191
192    #[test]
193    fn distance_and_squared_distance_agree() {
194        assert_eq!(squared_distance(0, 0, 3, 4), 25.0);
195        assert_eq!(distance(0, 0, 3, 4), 5.0);
196        assert_eq!(distance(2, 2, 2, 2), 0.0);
197    }
198
199    #[test]
200    fn squared_distance_matches_stock() {
201        assert_eq!(squared_distance(0, 0, 3, 4), 25.0);
202        assert_eq!(squared_distance(1, 1, 1, 1), 0.0);
203        assert_eq!(squared_distance(-2, 0, 1, 0), 9.0);
204    }
205
206    #[test]
207    fn closest_dir_dist_wraps_and_guards() {
208        // 16-direction semicircle: 1 vs 15 is 2 the short way (wrap), not 14.
209        assert_eq!(closest_dir_dist(1, 15, 16), 2);
210        assert_eq!(closest_dir_dist(3, 5, 16), 2);
211        // Either direction invalid → INVALID_DIR.
212        assert_eq!(closest_dir_dist(-1, 5, 16), INVALID_DIR);
213    }
214
215    #[test]
216    fn angle2line_flat_and_axis_aligned() {
217        // Both deltas below MIN_SLOPE_DELTA → defined as 0.0.
218        assert_eq!(angle2line(4, 4, 4, 4), 0.0);
219        // dy = fy-ty = 0, dx = tx-fx = 3 → atan2(0, 3) = 0.
220        assert_eq!(angle2line(0, 0, 3, 0), 0.0);
221        // dy = 0-0, dx = 0-0 for x... use a vertical line: fx=0,fy=0,tx=0,ty=3 → dy=-3,dx=0 → -pi/2.
222        assert!((angle2line(0, 0, 0, 3) - (-std::f64::consts::FRAC_PI_2)).abs() < 1e-12);
223    }
224
225    #[test]
226    fn find_incr_position_dbl_finds_slot() {
227        let list = [1.0, 3.0, 5.0];
228        assert_eq!(find_incr_position_dbl(0.0, &list), 0);
229        assert_eq!(find_incr_position_dbl(2.0, &list), 1);
230        assert_eq!(find_incr_position_dbl(4.0, &list), 2);
231        assert_eq!(find_incr_position_dbl(9.0, &list), 3);
232        // Equal to an element is NOT strictly less → inserts after it.
233        assert_eq!(find_incr_position_dbl(3.0, &list), 2);
234    }
235
236    #[test]
237    fn minmaxs_finds_a_single_minimum() {
238        // A V-shape: descend then ascend → exactly one minima of type -1. The reference resets
239        // `start` on every continued-decrease step, so a strict decline reports the extremum at the
240        // midpoint of the last tracked pair — here index 1 (value 3), not the true trough at index 2.
241        let items = [5, 3, 1, 3, 5];
242        let mm = minmaxs(&items);
243        assert_eq!(mm.idx.len(), 1);
244        assert_eq!(mm.kind[0], -1);
245        assert_eq!(mm.idx[0], 1);
246        assert_eq!(mm.val[0], 3);
247    }
248
249    #[test]
250    fn minmaxs_ignores_short_sequences() {
251        assert_eq!(minmaxs(&[1, 2]).idx.len(), 0);
252    }
253}