Skip to main content

fprint_mindtct/
ridges.rs

1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Neighbor ridge counting (`count_minutiae_ridges`): for each minutia, count the ridges crossing to
6//! its nearest neighbours, populating the ridge-count structure.
7//!
8//! Faithful port of stock NBIS `mindtct/src/lib/mindtct/ridges.c` (the neighbor/ridge stage), plus the
9//! two `minutia.c` list operations it opens with — `sort_minutiae_x_y` (`minutia.c` L680) and
10//! `rm_dup_minutiae` (`minutia.c` L745). Those two are what fix the **order and count** of the final
11//! minutiae list (and therefore the `.xyt` output); the ridge counts themselves are structured data
12//! consumed downstream, not part of the `x/y/theta/q` record.
13//!
14//! Stage outline ([`count_minutiae_ridges`]):
15//! 1. [`sort_minutiae_x_y`] — column-oriented sort (rank `x*iw + y`).
16//! 2. [`rm_dup_minutiae`] — drop minutiae sharing exact pixel coordinates.
17//! 3. For each minutia, [`find_neighbors`] (up to `max_nbrs` closest), [`sort_neighbors`] (vertical
18//!    origin, clockwise), and [`ridge_count`] to each — filling the minutia's
19//!    [`nbrs`](DetMinutia::nbrs) / [`ridge_counts`](DetMinutia::ridge_counts).
20//!
21//! The `util.c` helpers this stage relies on (`squared_distance`, `find_incr_position_dbl`,
22//! `angle2line`) live in the shared [`crate::util`] module. See `docs/mindtct-algorithm.md`
23//! §Bit-exactness.
24
25use crate::detect::contour::{fix_edge_pixel_pair, trace_contour, ScanDir, TraceResult};
26use crate::detect::line::line_points;
27use crate::detect::DetMinutia;
28use crate::num::{bubble_sort_double_inc_2, sort_indices_int_inc};
29use crate::params::LfsParms;
30use crate::util::{angle2line, find_incr_position_dbl, squared_distance};
31
32/// Sort the minutiae left-to-right then top-to-bottom (column-oriented) — port of stock
33/// `sort_minutiae_x_y` (`minutia.c` L680).
34///
35/// The sort key is the 1-D offset `x*iw + y`, so X is the primary key and Y breaks ties; the stable
36/// [`sort_indices_int_inc`] preserves input order among equal keys, matching the reference's stable
37/// bubble sort. PORT: stock passes `ih` but never reads it, so it is dropped here (as in
38/// `remove::sort_minutiae_y_x`).
39fn sort_minutiae_x_y(minutiae: &mut Vec<DetMinutia>, iw: i32) {
40    // PORT L694–L699: 1-D column-oriented offsets, then their sorted permutation.
41    let mut ranks: Vec<i32> = minutiae.iter().map(|m| (m.x * iw) + m.y).collect();
42    let order = sort_indices_int_inc(&mut ranks);
43
44    // PORT L713–L720: rebuild the list in sorted order.
45    let newlist: Vec<DetMinutia> = order
46        .into_iter()
47        .map(|o| minutiae[o as usize].clone())
48        .collect();
49    *minutiae = newlist;
50}
51
52/// Remove minutiae sharing exact pixel coordinates with an adjacent list entry — port of stock
53/// `rm_dup_minutiae` (`minutia.c` L745).
54///
55/// Walks the (already sorted) list back-to-front so removals never disturb not-yet-visited indices;
56/// when `list[i]` and `list[i-1]` share `(x, y)`, the earlier one (`i-1`) is dropped. PORT: the stock
57/// `remove_minutia` in-place slide is a `Vec::remove`.
58fn rm_dup_minutiae(minutiae: &mut Vec<DetMinutia>) {
59    // PORT L753: nothing to compare against for an empty (or single) list.
60    if minutiae.is_empty() {
61        return;
62    }
63    // PORT L753–L764: work backward, removing the 2nd of each coincident pair.
64    let mut i = minutiae.len() - 1;
65    while i > 0 {
66        if minutiae[i].x == minutiae[i - 1].x && minutiae[i].y == minutiae[i - 1].y {
67            // PORT L760: drop `list[i-1]`; the former `list[i]` slides into its place.
68            minutiae.remove(i - 1);
69        }
70        i -= 1;
71    }
72}
73
74/// Insert a neighbor at `pos`, shifting the tail down and off the fixed-length lists — port of stock
75/// `insert_neighbor` (`ridges.c` L416).
76///
77/// `nbr_list` / `nbr_sqr_dists` are the `max_nbrs`-length working buffers; `nnbrs` is the current fill
78/// count. When the lists are not yet full the tail shifts down and `nnbrs` grows; when full the last
79/// entry is bumped off. PORT: the stock `-480`/`-481` range guards are provably unreachable here — the
80/// only caller derives `pos` from [`find_incr_position_dbl`] over `0..nnbrs`, and only inserts while
81/// `nnbrs < max_nbrs` or the new distance beats the last stored one — so they are elided (as the crate
82/// elides other unreachable stock error returns).
83fn insert_neighbor(
84    pos: usize,
85    nbr_index: i32,
86    nbr_dist2: f64,
87    nbr_list: &mut [i32],
88    nbr_sqr_dists: &mut [f64],
89    nnbrs: &mut usize,
90    max_nbrs: usize,
91) {
92    // PORT L432–L450: start index for the down-shift; grow the count only when there is room.
93    let mut i: isize = if *nnbrs < max_nbrs {
94        let start = *nnbrs as isize - 1;
95        *nnbrs += 1;
96        start
97    } else {
98        // *nnbrs == max_nbrs: bump the last neighbor off (ignore it) to make room.
99        *nnbrs as isize - 2
100    };
101
102    // PORT L452–L458: shift everything from `i` down one slot until reaching `pos`.
103    while i >= pos as isize {
104        nbr_list[(i + 1) as usize] = nbr_list[i as usize];
105        nbr_sqr_dists[(i + 1) as usize] = nbr_sqr_dists[i as usize];
106        i -= 1;
107    }
108
109    // PORT L462–L463: drop the new neighbor into the freed slot.
110    nbr_list[pos] = nbr_index;
111    nbr_sqr_dists[pos] = nbr_dist2;
112}
113
114/// Consider `second` as a nearest neighbor of `first`, inserting it in distance order if close enough —
115/// port of stock `update_nbr_dists` (`ridges.c` L341).
116///
117/// PORT: the stock `-470` illegal-position guard is unreachable (see [`insert_neighbor`]) and elided.
118fn update_nbr_dists(
119    nbr_list: &mut [i32],
120    nbr_sqr_dists: &mut [f64],
121    nnbrs: &mut usize,
122    max_nbrs: usize,
123    first: usize,
124    second: usize,
125    minutiae: &[DetMinutia],
126) {
127    // PORT L350: position of the maximum (last) stored neighbor.
128    let last_nbr = max_nbrs - 1;
129
130    // PORT L356–L358: squared distance between the minutia pair.
131    let dist2 = squared_distance(
132        minutiae[first].x,
133        minutiae[first].y,
134        minutiae[second].x,
135        minutiae[second].y,
136    );
137
138    // PORT L363–L364: room left, or closer than the farthest stored neighbor?
139    if *nnbrs < max_nbrs || dist2 < nbr_sqr_dists[last_nbr] {
140        // PORT L367: insertion point preserving increasing distance order.
141        let pos = find_incr_position_dbl(dist2, &nbr_sqr_dists[..*nnbrs]);
142        // PORT L377–L379: insert at `pos`.
143        insert_neighbor(
144            pos,
145            second as i32,
146            dist2,
147            nbr_list,
148            nbr_sqr_dists,
149            nnbrs,
150            max_nbrs,
151        );
152    }
153    // PORT L387: otherwise not close enough — ignore.
154}
155
156/// Locate up to `max_nbrs` closest neighbors of `first`, searched forward through the sorted list —
157/// port of stock `find_neighbors` (`ridges.c` L227).
158///
159/// Because the list is sorted on `x*iw + y`, neighbors are drawn from the same pixel column below the
160/// primary and then complete columns to its right; the X-distance is a monotone lower bound on the
161/// true distance, so once the lists are full and the X-distance exceeds the farthest stored neighbor,
162/// the search stops. Returns the neighbor indices ordered by increasing squared distance (length is
163/// the stock `nnbrs`, empty when none qualify).
164///
165/// PORT: the two out-parameters (`onbr_list`, `onnbrs`) collapse into the returned `Vec`; the
166/// fixed-length `nbr_list` / `nbr_sqr_dists` working buffers become `max_nbrs`-length vectors truncated
167/// to `nnbrs` on return.
168fn find_neighbors(max_nbrs: i32, first: usize, minutiae: &[DetMinutia]) -> Vec<i32> {
169    // PORT L236–L250: fixed-length working buffers (indices + their squared distances).
170    let max_nbrs = max_nbrs.max(0) as usize;
171    let mut nbr_list = vec![0i32; max_nbrs];
172    let mut nbr_sqr_dists = vec![0.0f64; max_nbrs];
173
174    // PORT L253–L257: no stored neighbors yet; scan from just past the primary.
175    let mut nnbrs: usize = 0;
176    let last_nbr = max_nbrs - 1;
177    let mut second = first + 1;
178
179    // PORT L265–L294: walk the sorted suffix while neighbors may still qualify.
180    while second < minutiae.len() {
181        // PORT L271–L272: squared X-distance — a lower bound on the true squared distance.
182        let xdist = f64::from(minutiae[second].x - minutiae[first].x);
183        let xdist2 = xdist * xdist;
184
185        // PORT L276–L277: lists not full, OR this column is closer than the farthest stored neighbor.
186        if nnbrs < max_nbrs || xdist2 < nbr_sqr_dists[last_nbr] {
187            // PORT L279–L280: append or insert the candidate.
188            update_nbr_dists(
189                &mut nbr_list,
190                &mut nbr_sqr_dists,
191                &mut nnbrs,
192                max_nbrs,
193                first,
194                second,
195                minutiae,
196            );
197        } else {
198            // PORT L288–L290: full and this (and every farther) column is too far → stop.
199            break;
200        }
201
202        // PORT L293: next secondary minutia.
203        second += 1;
204    }
205
206    // PORT L299–L309: return only the neighbors actually stored.
207    nbr_list.truncate(nnbrs);
208    nbr_list
209}
210
211/// Sort a minutia's neighbors by their bearing from it — vertical origin, clockwise — port of stock
212/// `sort_neighbors` (`ridges.c` L488).
213///
214/// The bearing to each neighbor is [`angle2line`] with coordinates swapped and point order reversed
215/// (so direction `0` is vertical and positive runs clockwise), made non-negative and folded onto
216/// `[0, 2*PI)`. The stable [`bubble_sort_double_inc_2`] then reorders `nbr_list` by ascending bearing.
217///
218/// PORT: the by-reference sort of the stock in/out `nbr_list` becomes taking and returning it by value;
219/// `fmod(theta, 2*PI)` is `rem_euclid` (the argument is always non-negative here, so they agree).
220fn sort_neighbors(mut nbr_list: Vec<i32>, first: usize, minutiae: &[DetMinutia]) -> Vec<i32> {
221    // PORT L493: `pi2 = 2*PI`.
222    let pi2 = std::f64::consts::PI * 2.0;
223
224    // PORT L503–L517: bearing of the line joining the primary to each neighbor.
225    let mut join_thetas: Vec<f64> = nbr_list
226        .iter()
227        .map(|&nb| {
228            let nb = nb as usize;
229            // PORT L508–L511: coords swapped / points reversed for the vertical-clockwise convention.
230            let mut theta = angle2line(
231                minutiae[nb].y,
232                minutiae[nb].x,
233                minutiae[first].y,
234                minutiae[first].x,
235            );
236            // PORT L514–L515: make positive and fold onto `[0, 2*PI)`.
237            theta += pi2;
238            theta.rem_euclid(pi2)
239        })
240        .collect();
241
242    // PORT L520: stable sort the neighbor indices into ascending-bearing order.
243    bubble_sort_double_inc_2(&mut join_thetas, &mut nbr_list);
244
245    nbr_list
246}
247
248/// Search forward along a pixel trajectory for the `pix1`→`pix2` transition — port of stock
249/// `find_transition` (`ridges.c` L709).
250///
251/// Starting at index `*iptr`, tests each adjacent pixel pair `(i, i+1)`; on the first pair equal to
252/// `(pix1, pix2)` it sets `*iptr` to the second pixel's index and returns `true`. Otherwise it sets
253/// `*iptr` to `num` (past the end) and returns `false`.
254///
255/// PORT: stock passes `ih` but only ever indexes with `iw`, so `ih` is dropped. `pts` replaces the
256/// parallel `xlist`/`ylist` (x = `.0`, y = `.1`).
257fn find_transition(
258    iptr: &mut usize,
259    pix1: u8,
260    pix2: u8,
261    pts: &[(i32, i32)],
262    num: usize,
263    bdata: &[u8],
264    iw: i32,
265) -> bool {
266    // PORT L716–L718: current index and its successor.
267    let mut i = *iptr;
268    let mut j = i + 1;
269
270    // PORT L721: stop one short of the trajectory end.
271    while i < num - 1 {
272        // PORT L723–L724: desired transition found?
273        let pi = bdata[(pts[i].1 * iw + pts[i].0) as usize];
274        let pj = bdata[(pts[j].1 * iw + pts[j].0) as usize];
275        if pi == pix1 && pj == pix2 {
276            // PORT L727: point at the second pixel of the transition.
277            *iptr = j;
278            return true;
279        }
280        // PORT L734–L735: advance to the next pixel pair.
281        i += 1;
282        j += 1;
283    }
284
285    // PORT L741–L742: exhausted the trajectory without a match.
286    *iptr = num;
287    false
288}
289
290/// Decide whether a ridge start/end transition is a genuine ridge crossing — port of stock
291/// `validate_ridge_crossing` (`ridges.c` L770).
292///
293/// Traces the ridge contour outward from the ridge-end edge pixel, both clockwise and
294/// counter-clockwise, up to `max_ridge_steps` steps, watching for the ridge-start point. If either
295/// trace loops back to the start (or is impossible to seed), the pair is walking on and off the side of
296/// one ridge, not crossing — invalid. A crossing is valid only when **both** traces complete without
297/// looping.
298///
299/// PORT: stock's `IGNORE` / `LOOP_FOUND` / `0` `int` returns map onto [`TraceResult`]
300/// `Ignore` / `Loop` / `Traced`; "not IGNORE and not LOOP_FOUND" is exactly `matches!(_, Traced)`. The
301/// unused `num` parameter and the never-taken `< 0` system-error path are dropped, and the traced
302/// contours (which stock immediately frees) are simply discarded.
303fn validate_ridge_crossing(
304    ridge_start: usize,
305    ridge_end: usize,
306    pts: &[(i32, i32)],
307    bdata: &[u8],
308    iw: i32,
309    ih: i32,
310    max_ridge_steps: i32,
311) -> bool {
312    // PORT L780–L783: feature pixel at the ridge end, edge pixel one step before it.
313    // PORT L786–L787: nudge a diagonally adjacent pair onto a cardinal one before tracing.
314    let (feat_x, feat_y, edge_x, edge_y) = fix_edge_pixel_pair(
315        pts[ridge_end].0,
316        pts[ridge_end].1,
317        pts[ridge_end - 1].0,
318        pts[ridge_end - 1].1,
319        bdata,
320        iw,
321    );
322
323    // PORT L800: the ridge-start point is the loop-trigger the traces watch for.
324    let x_loop = pts[ridge_start - 1].0;
325    let y_loop = pts[ridge_start - 1].1;
326
327    // PORT L797–L802: trace clockwise; a completed (non-looping) trace lets us try the other way.
328    let clockwise = trace_contour(
329        max_ridge_steps,
330        x_loop,
331        y_loop,
332        feat_x,
333        feat_y,
334        edge_x,
335        edge_y,
336        ScanDir::Clockwise,
337        bdata,
338        iw,
339        ih,
340    );
341    // PORT L818–L819: not IGNORE and not LOOP_FOUND → keep validating.
342    if matches!(clockwise, TraceResult::Traced(_)) {
343        // PORT L823–L828: now trace counter-clockwise.
344        let counter = trace_contour(
345            max_ridge_steps,
346            x_loop,
347            y_loop,
348            feat_x,
349            feat_y,
350            edge_x,
351            edge_y,
352            ScanDir::CounterClockwise,
353            bdata,
354            iw,
355            ih,
356        );
357        // PORT L841–L845: both traces completed without looping → a valid crossing.
358        if matches!(counter, TraceResult::Traced(_)) {
359            return true;
360        }
361    }
362
363    // PORT L850–L851: failed to validate.
364    false
365}
366
367/// Count the ridges crossed along the straight trajectory from minutia `first` to `second` — port of
368/// stock `ridge_count` (`ridges.c` L547).
369///
370/// Walks the [`line_points`] trajectory, skips to the first pixel of opposite color, then repeatedly
371/// finds a `0`→`1` (ridge start) followed by a `1`→`0` (ridge end) transition, counting each pair that
372/// [`validate_ridge_crossing`] accepts as a genuine crossing.
373///
374/// # Errors
375///
376/// Propagates the [`line_points`] overflow error (`-412`), unreachable for these trajectories but kept
377/// for a faithful transcription. The stock `< 0` validation system-error path has no port analogue.
378fn ridge_count(
379    first: usize,
380    second: i32,
381    minutiae: &[DetMinutia],
382    bdata: &[u8],
383    iw: i32,
384    ih: i32,
385    lfsparms: &LfsParms,
386) -> Result<i32, i32> {
387    let second = second as usize;
388    let m1 = &minutiae[first];
389    let m2 = &minutiae[second];
390
391    // PORT L560–L564: identical coordinates → zero ridges between them.
392    if m1.x == m2.x && m1.y == m2.y {
393        return Ok(0);
394    }
395
396    // PORT L566–L571: contiguous pixel trajectory between the two points.
397    let pts = line_points(m1.x, m1.y, m2.x, m2.y)?;
398    let num = pts.len();
399
400    // PORT L573–L579: no trajectory points → nothing to count (defensive, unreachable).
401    if num == 0 {
402        return Ok(0);
403    }
404
405    // PORT L581–L593: skip forward to the first pixel opposite the starting pixel's color.
406    let prevpix = bdata[(pts[0].1 * iw + pts[0].0) as usize];
407    let mut i = 1usize;
408    let mut found = false;
409    while i < num {
410        let curpix = bdata[(pts[i].1 * iw + pts[i].0) as usize];
411        if curpix != prevpix {
412            found = true;
413            break;
414        }
415        i += 1;
416    }
417
418    // PORT L595–L600: never changed color → no ridges to count.
419    if !found {
420        return Ok(0);
421    }
422
423    // PORT L603: ready to count.
424    let mut ridge_count = 0;
425
426    // PORT L608–L674: alternately find ridge-start / ridge-end transitions and validate each.
427    while i < num {
428        // PORT L610–L620: no more 0→1 ridge starts → done.
429        if !find_transition(&mut i, 0, 1, &pts, num, bdata, iw) {
430            return Ok(ridge_count);
431        }
432        let ridge_start = i;
433
434        // PORT L627–L637: no matching 1→0 ridge end → done.
435        if !find_transition(&mut i, 1, 0, &pts, num, bdata, iw) {
436            return Ok(ridge_count);
437        }
438        let ridge_end = i;
439
440        // PORT L651–L670: a validated crossing bumps the count; otherwise seek the next ridge start.
441        if validate_ridge_crossing(
442            ridge_start,
443            ridge_end,
444            &pts,
445            bdata,
446            iw,
447            ih,
448            lfsparms.max_ridge_steps,
449        ) {
450            ridge_count += 1;
451        }
452    }
453
454    // PORT L683: trajectory exhausted.
455    Ok(ridge_count)
456}
457
458/// Fill in one minutia's neighbors and their ridge counts — port of stock `count_minutia_ridges`
459/// (`ridges.c` L144).
460///
461/// Finds `first`'s closest neighbors ([`find_neighbors`]), orders them by bearing ([`sort_neighbors`]),
462/// counts the ridges to each ([`ridge_count`]), and stores both lists on `minutiae[first]`. A minutia
463/// with no neighbors is left with empty lists (stock `num_nbrs == 0`).
464///
465/// # Errors
466///
467/// Propagates [`ridge_count`]'s error.
468fn count_minutia_ridges(
469    first: usize,
470    minutiae: &mut [DetMinutia],
471    bdata: &[u8],
472    iw: i32,
473    ih: i32,
474    lfsparms: &LfsParms,
475) -> Result<(), i32> {
476    // PORT L151–L155: up to `max_nbrs` closest neighbors.
477    let nbr_list = find_neighbors(lfsparms.max_nbrs, first, minutiae);
478
479    // PORT L160–L164: no neighbors → nothing to store.
480    if nbr_list.is_empty() {
481        return Ok(());
482    }
483
484    // PORT L166–L170: order the neighbors by bearing.
485    let nbr_list = sort_neighbors(nbr_list, first, minutiae);
486
487    // PORT L172–L196: ridge count to each neighbor, in sorted order.
488    let mut nbr_nridges = Vec::with_capacity(nbr_list.len());
489    for &nbr in &nbr_list {
490        nbr_nridges.push(ridge_count(first, nbr, minutiae, bdata, iw, ih, lfsparms)?);
491    }
492
493    // PORT L199–L201: assign the neighbor indices and ridge counts to the primary minutia.
494    minutiae[first].nbrs = nbr_list;
495    minutiae[first].ridge_counts = nbr_nridges;
496
497    Ok(())
498}
499
500/// Find neighbors and count intervening ridges for every minutia — port of stock
501/// `count_minutiae_ridges` (`ridges.c` L93).
502///
503/// Sorts the list column-oriented ([`sort_minutiae_x_y`]), drops coincident duplicates
504/// ([`rm_dup_minutiae`]) — the two steps that fix the **order and count** of the final minutiae list —
505/// then, for each minutia but the last, fills its neighbor / ridge-count lists
506/// ([`count_minutia_ridges`]). `bdata` is the binary image (`0 == white/valley`, `1 == black/ridge`),
507/// `iw`×`ih` pixels.
508///
509/// # Errors
510///
511/// Propagates [`count_minutia_ridges`]'s error (`line_points` overflow, unreachable here).
512pub(crate) fn count_minutiae_ridges(
513    minutiae: &mut Vec<DetMinutia>,
514    bdata: &[u8],
515    iw: i32,
516    ih: i32,
517    lfsparms: &LfsParms,
518) -> Result<(), i32> {
519    // PORT L102–L105: column-oriented sort (x then y).
520    sort_minutiae_x_y(minutiae, iw);
521
522    // PORT L107–L110: remove exact-coordinate duplicates.
523    rm_dup_minutiae(minutiae);
524
525    // PORT L112–L120: for each remaining minutia but the last, find neighbors and count ridges.
526    for i in 0..minutiae.len().saturating_sub(1) {
527        count_minutia_ridges(i, minutiae, bdata, iw, ih, lfsparms)?;
528    }
529
530    // PORT L123: done.
531    Ok(())
532}
533
534#[cfg(test)]
535mod tests {
536    use super::*;
537    use crate::detect::{BIFURCATION, RIDGE_ENDING};
538    use crate::params::LFSPARMS_V2;
539
540    // Minimal DetMinutia builder — only the fields the ridge stage reads (coordinates, kind, and the
541    // neighbor lists it fills) matter here.
542    fn mk(x: i32, y: i32) -> DetMinutia {
543        DetMinutia {
544            x,
545            y,
546            ex: x,
547            ey: y,
548            direction: 0,
549            reliability: 0.99,
550            kind: RIDGE_ENDING,
551            appearing: true,
552            feature_id: 0,
553            nbrs: Vec::new(),
554            ridge_counts: Vec::new(),
555        }
556    }
557
558    #[test]
559    fn sort_minutiae_x_y_orders_by_column_then_row() {
560        // Deliberately out of order; iw large so x dominates the rank.
561        let mut ms = vec![mk(2, 5), mk(0, 9), mk(2, 1), mk(0, 3)];
562        sort_minutiae_x_y(&mut ms, 100);
563        let coords: Vec<(i32, i32)> = ms.iter().map(|m| (m.x, m.y)).collect();
564        assert_eq!(coords, vec![(0, 3), (0, 9), (2, 1), (2, 5)]);
565    }
566
567    #[test]
568    fn rm_dup_minutiae_drops_coincident_pairs() {
569        // Sorted, with a coincident pair (1,1)/(1,1) and a triple (4,4).
570        let mut ms = vec![mk(0, 0), mk(1, 1), mk(1, 1), mk(4, 4), mk(4, 4), mk(4, 4)];
571        rm_dup_minutiae(&mut ms);
572        let coords: Vec<(i32, i32)> = ms.iter().map(|m| (m.x, m.y)).collect();
573        assert_eq!(coords, vec![(0, 0), (1, 1), (4, 4)]);
574    }
575
576    #[test]
577    fn find_neighbors_returns_k_nearest_in_distance_order() {
578        // Primary at index 0; suffix candidates, already x_y-sorted.
579        // Distances^2 from (0,0): (1,1)=2, (2,0)=4, (3,3)=18, (4,0)=16, (5,1)=26.
580        let ms = vec![mk(0, 0), mk(1, 1), mk(2, 0), mk(3, 3), mk(4, 0), mk(5, 1)];
581        let nbrs = find_neighbors(5, 0, &ms);
582        // Ascending squared distance: 2, 4, 16, 18, 26 → indices 1, 2, 4, 3, 5.
583        assert_eq!(nbrs, vec![1, 2, 4, 3, 5]);
584    }
585
586    #[test]
587    fn find_neighbors_caps_at_max_nbrs_and_breaks_on_x() {
588        // Only the three closest are kept when max_nbrs = 3.
589        let ms = vec![mk(0, 0), mk(1, 1), mk(2, 0), mk(3, 3), mk(4, 0), mk(5, 1)];
590        let nbrs = find_neighbors(3, 0, &ms);
591        assert_eq!(nbrs, vec![1, 2, 4]);
592    }
593
594    #[test]
595    fn sort_neighbors_orders_vertical_then_clockwise() {
596        // Primary (10,10); A above (10,0), B right (20,10), C below (10,20).
597        let ms = vec![mk(10, 10), mk(10, 0), mk(20, 10), mk(10, 20)];
598        // Feed them out of order; expect vertical origin, clockwise: A(1), B(2), C(3).
599        let sorted = sort_neighbors(vec![3, 2, 1], 0, &ms);
600        assert_eq!(sorted, vec![1, 2, 3]);
601    }
602
603    #[test]
604    fn find_transition_locates_pair_and_reports_end() {
605        // 4-wide, 1-tall image: white white black white → 0 0 1 0.
606        let bdata = [0u8, 0, 1, 0];
607        let pts = [(0, 0), (1, 0), (2, 0), (3, 0)];
608        // 0→1 transition: pair (1,2) → *iptr becomes 2 (the '1').
609        let mut i = 0usize;
610        assert!(find_transition(&mut i, 0, 1, &pts, 4, &bdata, 4));
611        assert_eq!(i, 2);
612        // 1→0 transition from there: pair (2,3) → *iptr becomes 3.
613        assert!(find_transition(&mut i, 1, 0, &pts, 4, &bdata, 4));
614        assert_eq!(i, 3);
615        // No further 0→1 → false, *iptr set past the end.
616        let mut j = 3usize;
617        assert!(!find_transition(&mut j, 0, 1, &pts, 4, &bdata, 4));
618        assert_eq!(j, 4);
619    }
620
621    #[test]
622    fn ridge_count_identical_points_is_zero() {
623        let ms = vec![mk(5, 5), mk(5, 5)];
624        let bdata = vec![0u8; 25];
625        let rc = ridge_count(0, 1, &ms, &bdata, 5, 5, &LFSPARMS_V2).unwrap();
626        assert_eq!(rc, 0);
627    }
628
629    #[test]
630    fn ridge_count_no_transition_is_zero() {
631        // All-white image: no color change along the trajectory.
632        let ms = vec![mk(1, 2), mk(3, 2)];
633        let bdata = vec![0u8; 25];
634        let rc = ridge_count(0, 1, &ms, &bdata, 5, 5, &LFSPARMS_V2).unwrap();
635        assert_eq!(rc, 0);
636    }
637
638    #[test]
639    fn ridge_count_counts_a_validated_crossing() {
640        // 25x25 image, two full-height black ridge columns at x=6 and x=13.
641        // The horizontal trajectory at y=12 skips past column 6 (the first color change) and then
642        // counts the column-13 crossing, which validates (a full-height ridge separates the left and
643        // right white regions, so neither contour trace loops back).
644        let iw = 25i32;
645        let ih = 25i32;
646        let mut bdata = vec![0u8; (iw * ih) as usize];
647        for y in 0..ih {
648            bdata[(y * iw + 6) as usize] = 1;
649            bdata[(y * iw + 13) as usize] = 1;
650        }
651        let ms = vec![mk(2, 12), mk(20, 12)];
652        let rc = ridge_count(0, 1, &ms, &bdata, iw, ih, &LFSPARMS_V2).unwrap();
653        assert_eq!(rc, 1);
654    }
655
656    #[test]
657    fn count_minutiae_ridges_sorts_dedups_and_fills() {
658        // Two coincident minutiae plus others; after sort+dedup the count drops and neighbors fill.
659        let iw = 25i32;
660        let ih = 25i32;
661        let bdata = vec![0u8; (iw * ih) as usize];
662        let mut ms = vec![mk(20, 12), mk(2, 12), mk(2, 12), mk(10, 8), mk(15, 4)];
663        count_minutiae_ridges(&mut ms, &bdata, iw, ih, &LFSPARMS_V2).unwrap();
664        // The coincident (2,12) pair collapses to one; 5 → 4 minutiae, sorted by x then y.
665        let coords: Vec<(i32, i32)> = ms.iter().map(|m| (m.x, m.y)).collect();
666        assert_eq!(coords, vec![(2, 12), (10, 8), (15, 4), (20, 12)]);
667        // Every minutia but the last gets a (possibly empty, but here non-empty) neighbor list, and
668        // the two parallel lists always share a length.
669        for m in &ms {
670            assert_eq!(m.nbrs.len(), m.ridge_counts.len());
671        }
672        assert!(!ms[0].nbrs.is_empty());
673    }
674
675    #[test]
676    fn bifurcation_and_ending_kinds_are_both_usable() {
677        // Sanity: the builder's kind field is independent of the ridge stage's list operations.
678        let mut a = mk(0, 0);
679        a.kind = BIFURCATION;
680        assert_eq!(a.kind, BIFURCATION);
681        assert_eq!(mk(0, 0).kind, RIDGE_ENDING);
682    }
683}