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}