Skip to main content

fprint_mindtct/detect/
contour.rs

1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Ridge/valley contour tracing around a candidate minutia point — faithful port of stock NBIS
6//! `mindtct/src/lib/mindtct/contour.c`.
7//!
8//! A minutia "feature" is a run of interior pixels of one color (ridge = black = `1`, valley =
9//! white = `0`); each interior *contour* pixel is paired with an adjacent *edge* pixel of the
10//! opposite color that sits just outside the feature. [`trace_contour`] walks that interior edge one
11//! 8-connected step at a time — [`next_contour_pixel`] scans the eight neighbors of the current
12//! feature pixel, clockwise or counter-clockwise, for the next feature/edge pair, skipping "exposed"
13//! corner pixels — collecting parallel lists of contour and edge coordinates. The higher-level
14//! [`get_centered_contour`]/[`get_high_curvature_contour`] extract a fixed-length contour centered on
15//! the feature point by tracing one half clockwise and the other counter-clockwise and concatenating
16//! them, and [`min_contour_theta`] finds the point of highest curvature along such a contour.
17//!
18//! The 8-neighbor scan order, the clockwise/counter-clockwise rotation, and the corner-exposure rule
19//! are reproduced verbatim from the reference so a traced contour is identical pixel-for-pixel.
20
21// `too_many_arguments`: the routines carrying a per-function `#[allow]` below are verbatim
22// transcriptions of a stock `contour.c` function whose interface is fixed by the reference — the
23// binary image (`bdata`, `iw`, `ih`) plus two or three coordinate pairs (a feature point, its edge
24// pixel, and sometimes a loop/search target). Bundling those into an ad-hoc struct would obscure the
25// one-to-one correspondence with the C; the reference-side arity is the justification, applied at
26// each function that needs it rather than to the whole file.
27
28use crate::consts::TRUNC_SCALE;
29use crate::num::{sround, trunc_dbl_precision};
30
31// PORT: stock `nbr8_dx`/`nbr8_dy` (`globals.c` L245–L246) — per-axis offsets of the eight neighbors
32// of a pixel, indexed 0..8 clockwise starting due north:
33//
34// ```text
35//   7 0 1        NW N NE
36//   6 . 2   ==    W . E
37//   5 4 3        SW S SE
38// ```
39const NBR8_DX: [i32; 8] = [0, 1, 1, 1, 0, -1, -1, -1];
40const NBR8_DY: [i32; 8] = [-1, -1, 0, 1, 1, 1, 0, -1];
41
42// PORT: stock cardinal neighbor indices into `nbr8_dx`/`nbr8_dy` (`lfs.h` L667–L670). These name the
43// four non-diagonal positions that [`start_scan_nbr`] can return.
44const NORTH: i32 = 0;
45const EAST: i32 = 2;
46const SOUTH: i32 = 4;
47const WEST: i32 = 6;
48
49// PORT: stock `INVALID_DIR` (`lfs.h` L320) — returned by [`start_scan_nbr`] for an input that is
50// neither N/S/E/W aligned. The reference notes this is unreachable for the aligned pairs the tracer
51// feeds it ("Should never reach here. Added to remove compiler warning.").
52const INVALID_DIR: i32 = -1;
53
54// PORT: stock `MIN_SLOPE_DELTA` (`lfs.h` L701) — below this per-axis delta a line is treated as
55// having zero slope in [`angle2line`], avoiding a degenerate `atan2(0, 0)`.
56const MIN_SLOPE_DELTA: f64 = 0.5;
57
58/// Direction in which the eight neighbors of a feature pixel are scanned for the next contour pixel —
59/// port of the stock `scan_clock` flag (`SCAN_CLOCKWISE == 0` / `SCAN_COUNTER_CLOCKWISE == 1`,
60/// `lfs.h` L496–L497). Modeled as an enum since it is only ever one of the two directions.
61#[derive(Clone, Copy, Debug, PartialEq, Eq)]
62pub(crate) enum ScanDir {
63    /// Advance the neighbor index one position clockwise (`SCAN_CLOCKWISE`).
64    Clockwise,
65    /// Advance the neighbor index one position counter-clockwise (`SCAN_COUNTER_CLOCKWISE`).
66    CounterClockwise,
67}
68
69/// A traced feature contour — the port's analogue of stock's four parallel coordinate lists
70/// (`contour_x`, `contour_y`, `contour_ex`, `contour_ey`) plus their shared count `ncontour`.
71///
72/// The first two vectors are the 8-connected *contour points* interior to the feature (guaranteed
73/// adjacent and the feature's color); the second two are the corresponding *edge points* just
74/// outside the feature (opposite color, not guaranteed 8-connected). All four are kept in lock-step,
75/// so their shared length ([`len`](Self::len)) is the stock `ncontour`. Exposing `x`/`y` as slices
76/// lets them feed [`min_contour_theta`] and the chain-code routines directly.
77///
78/// PORT: stock `allocate_contour`/`free_contour` (`contour.c` L105/L179) collapse into `Vec`
79/// ownership; the `-180..=-183` malloc-failure paths are unreachable here (allocation aborts rather
80/// than returning an error code) and are elided.
81#[derive(Clone, Debug, Default, PartialEq, Eq)]
82pub(crate) struct Contour {
83    /// X coordinates of the interior contour points (stock `contour_x`).
84    pub x: Vec<i32>,
85    /// Y coordinates of the interior contour points (stock `contour_y`).
86    pub y: Vec<i32>,
87    /// X coordinates of the corresponding exterior edge points (stock `contour_ex`).
88    pub ex: Vec<i32>,
89    /// Y coordinates of the corresponding exterior edge points (stock `contour_ey`).
90    pub ey: Vec<i32>,
91}
92
93impl Contour {
94    /// An empty contour with room for `n` points reserved in each list.
95    fn with_capacity(n: usize) -> Self {
96        Contour {
97            x: Vec::with_capacity(n),
98            y: Vec::with_capacity(n),
99            ex: Vec::with_capacity(n),
100            ey: Vec::with_capacity(n),
101        }
102    }
103
104    /// Number of contour points (stock `ncontour`); all four coordinate lists share this length.
105    pub fn len(&self) -> usize {
106        self.x.len()
107    }
108
109    /// Append one contour/edge point pair to the parallel lists.
110    fn push(&mut self, x: i32, y: i32, ex: i32, ey: i32) {
111        self.x.push(x);
112        self.y.push(y);
113        self.ex.push(ex);
114        self.ey.push(ey);
115    }
116
117    /// Append `src`'s points in **reverse** order (last point first).
118    ///
119    /// A clockwise half-contour is collected outward from the feature point, so reversing it makes
120    /// its far end the start of the concatenated contour — the stock `for(i, j=n-1; ...; j--)` copy.
121    fn extend_rev(&mut self, src: &Contour) {
122        let mut j = src.len();
123        while j > 0 {
124            j -= 1;
125            self.push(src.x[j], src.y[j], src.ex[j], src.ey[j]);
126        }
127    }
128
129    /// Append `src`'s points in **forward** order — the stock `for(i, j=n+1; ...; j++)` copy.
130    fn extend_fwd(&mut self, src: &Contour) {
131        let mut i = 0;
132        while i < src.len() {
133            self.push(src.x[i], src.y[i], src.ex[i], src.ey[i]);
134            i += 1;
135        }
136    }
137}
138
139/// Outcome of [`trace_contour`] — the stock `int` return with its allocated buffers folded in.
140#[derive(Clone, Debug, PartialEq, Eq)]
141pub(crate) enum TraceResult {
142    /// The trace completed normally (stock return `0`): a contour of up to `max_len` points, possibly
143    /// cut short where no further contour pixel was found.
144    Traced(Contour),
145    /// The trace walked back around to the loop-trigger point (stock `LOOP_FOUND`); the contour holds
146    /// the points collected up to — but not including — that point.
147    Loop(Contour),
148    /// The trace was impossible because the feature and edge pixels were not opposite colors (stock
149    /// `IGNORE`); no contour is produced.
150    Ignore,
151}
152
153/// Outcome of [`get_centered_contour`] — stock returns `0`/`LOOP_FOUND`/`IGNORE`/`INCOMPLETE`.
154#[derive(Clone, Debug, PartialEq, Eq)]
155pub(crate) enum CenteredContour {
156    /// A complete, centered contour of `2 * half_contour + 1` points (stock return `0`).
157    Ok(Contour),
158    /// A loop was detected while tracing either half (stock `LOOP_FOUND`); no contour is returned.
159    Loop,
160    /// A half-trace was impossible due to the starting conditions (stock `IGNORE`).
161    Ignore,
162    /// A half-contour could not reach the requested length (stock `INCOMPLETE`).
163    Incomplete,
164}
165
166/// Outcome of [`get_high_curvature_contour`] — stock returns `0` (with an empty *or* full contour)
167/// or `LOOP_FOUND` (with a contour).
168#[derive(Clone, Debug, PartialEq, Eq)]
169pub(crate) enum HighCurvatureContour {
170    /// The trace could not extract a full-length contour (stock return `0` with `oncontour == 0`);
171    /// nothing is returned.
172    Empty,
173    /// A complete contour of `2 * half_contour + 1` points (stock return `0` with a contour).
174    Ok(Contour),
175    /// The contour forms a complete loop (stock `LOOP_FOUND`); the loop's contour is returned for
176    /// further processing.
177    Loop(Contour),
178}
179
180/// Compute the angle (radians) of the line from `(fx, fy)` to `(tx, ty)` — port of stock
181/// `angle2line` (`util.c` L519).
182///
183/// PORT: `angle2line` lives in stock `util.c`, not `contour.c`; it is defined here as a file-private
184/// helper because [`min_contour_theta`] is its only port-side consumer so far. Relocate to a shared
185/// `util` module when that file is ported. The slope is measured as `dy = fy - ty`, `dx = tx - fx`
186/// (note the asymmetry, verbatim from the reference); when both deltas fall below [`MIN_SLOPE_DELTA`]
187/// the angle is defined as `0.0`.
188fn angle2line(fx: i32, fy: i32, tx: i32, ty: i32) -> f64 {
189    // PORT L524–L525: slope components (the reference's mixed subtraction order is intentional).
190    let dy = f64::from(fy - ty);
191    let dx = f64::from(tx - fx);
192    // PORT L527–L532: sufficiently flat → 0.0, else the arctangent of the slope.
193    if dx.abs() < MIN_SLOPE_DELTA && dy.abs() < MIN_SLOPE_DELTA {
194        0.0
195    } else {
196        dy.atan2(dx)
197    }
198}
199
200/// Convert the line connecting two points to an integer direction on the full circle — port of stock
201/// `line2direction` (`util.c` L552).
202///
203/// The point coordinates are swapped and their order reversed (as in the reference) so that direction
204/// `0` is vertical and positive directions run clockwise. The angle from [`angle2line`] is made
205/// positive, converted from radians to an integer direction on `0..=2*ndirs` (`full_ndirs` units per
206/// circle), quantized through [`trunc_dbl_precision`]/[`sround`] for architecture-independent
207/// rounding, and reduced onto the range `0..2*ndirs`.
208///
209/// PORT: `line2direction` lives in stock `util.c`; it is defined here as a `pub(crate)` helper (beside
210/// [`angle2line`], its only dependency) because the detection stage
211/// ([`adjust_high_curvature_minutia_v2`](super::adjust_high_curvature_minutia_v2) and
212/// [`process_loop_v2`](super::loops::process_loop_v2)) is its only consumer. Relocate to a shared
213/// `util` module when that file is ported. `fmod` becomes `rem_euclid` (the argument is always
214/// positive here, so the two agree); the trailing `%` likewise stays non-negative.
215pub(crate) fn line2direction(fx: i32, fy: i32, tx: i32, ty: i32, ndirs: i32) -> i32 {
216    // PORT L557: static `pi2 = 2*PI`.
217    let pi2 = std::f64::consts::PI * 2.0;
218
219    // PORT L563: coordinates swapped and points reversed so 0 is vertical, positive is clockwise.
220    let mut theta = angle2line(ty, tx, fy, fx);
221
222    // PORT L566–L567: make the angle positive and fold onto `[0, 2*PI)`.
223    theta += pi2;
224    theta = theta.rem_euclid(pi2);
225
226    // PORT L572–L576: radians → integer-direction units on the full circle.
227    let full_ndirs = ndirs << 1;
228    let pi_factor = f64::from(full_ndirs) / pi2;
229    theta *= pi_factor;
230
231    // PORT L579–L581: quantize precision, then round to the nearest integer direction.
232    theta = trunc_dbl_precision(theta, TRUNC_SCALE);
233    let idir = sround(theta);
234
235    // PORT L583: reduce onto `[0..2*ndirs]` (always non-negative here).
236    idir.rem_euclid(full_ndirs)
237}
238
239/// Position of the second pixel relative to the first for an N/S/E/W-aligned pair — port of stock
240/// `start_scan_nbr` (`contour.c` L1020).
241///
242/// Returns the [`NORTH`]/[`SOUTH`]/[`EAST`]/[`WEST`] neighbor index of `(x_next, y_next)` as seen
243/// from `(x_prev, y_prev)`, or [`INVALID_DIR`] for a non-aligned (e.g. diagonal) pair. This does not
244/// account for diagonal positions — the tracer guarantees the edge pixel is cardinally adjacent to
245/// the feature pixel (see [`fix_edge_pixel_pair`]).
246fn start_scan_nbr(x_prev: i32, y_prev: i32, x_next: i32, y_next: i32) -> i32 {
247    // PORT L1023–L1030: cardinal-direction dispatch.
248    if x_prev == x_next && y_next > y_prev {
249        SOUTH
250    } else if x_prev == x_next && y_next < y_prev {
251        NORTH
252    } else if x_next > x_prev && y_prev == y_next {
253        EAST
254    } else if x_next < x_prev && y_prev == y_next {
255        WEST
256    } else {
257        // PORT L1032–L1034: unreachable for aligned inputs; present to mirror the reference.
258        INVALID_DIR
259    }
260}
261
262/// Advance an 8-connected neighbor index one position in the given scan direction — port of stock
263/// `next_scan_nbr` (`contour.c` L1049).
264///
265/// Clockwise adds one modulo 8; counter-clockwise adds seven modulo 8 (a wrapping decrement).
266fn next_scan_nbr(nbr_i: i32, scan: ScanDir) -> i32 {
267    // PORT L1053–L1063: `+1 % 8` clockwise, `+7 % 8` counter-clockwise.
268    match scan {
269        ScanDir::Clockwise => (nbr_i + 1) % 8,
270        ScanDir::CounterClockwise => (nbr_i + 7) % 8,
271    }
272}
273
274/// Locate the next pixel on a feature's interior contour — port of stock `next_contour_pixel`
275/// (`contour.c` L876).
276///
277/// Scans the eight neighbors of the current feature pixel `(cur_x_loc, cur_y_loc)` in the `scan`
278/// direction, starting from the current edge pixel's position, looking for the first adjacent pair
279/// whose leading pixel has the feature's color and whose trailing (previous) pixel has the edge's
280/// color. That pair becomes the next contour point (returned) and edge point. An "exposed" corner —
281/// a diagonal neighbor whose own next neighbor is *not* the feature color — is skipped so the walk
282/// stays on the 8-connected interior edge.
283///
284/// Returns `Some((next_x_loc, next_y_loc, next_x_edge, next_y_edge))` on success (stock `TRUE`), or
285/// `None` (stock `FALSE`) when a neighbor falls outside the image or no valid pair exists among the
286/// eight neighbors (an isolated pixel).
287#[expect(clippy::too_many_arguments)]
288fn next_contour_pixel(
289    cur_x_loc: i32,
290    cur_y_loc: i32,
291    cur_x_edge: i32,
292    cur_y_edge: i32,
293    scan: ScanDir,
294    bdata: &[u8],
295    iw: i32,
296    ih: i32,
297) -> Option<(i32, i32, i32, i32)> {
298    // PORT L890–L892: the feature pixel's value and its edge pixel's value.
299    let feature_pix = bdata[(cur_y_loc * iw + cur_x_loc) as usize];
300    let edge_pix = bdata[(cur_y_edge * iw + cur_x_edge) as usize];
301
302    // PORT L901: neighbor index of the edge pixel relative to the feature pixel — the scan seed.
303    let mut nbr_i = start_scan_nbr(cur_x_loc, cur_y_loc, cur_x_edge, cur_y_edge);
304
305    // PORT L904–L906: seed the "current" scan neighbor at the feature's edge pixel.
306    let mut cur_nbr_x = cur_x_edge;
307    let mut cur_nbr_y = cur_y_edge;
308    let mut cur_nbr_pix = edge_pix;
309
310    // PORT L909: scan the (up to) eight neighbors of the feature pixel.
311    let mut i = 0;
312    while i < 8 {
313        // PORT L912–L914: the just-scanned neighbor becomes the "previous" one.
314        let prev_nbr_x = cur_nbr_x;
315        let prev_nbr_y = cur_nbr_y;
316        let prev_nbr_pix = cur_nbr_pix;
317
318        // PORT L917: step the neighbor index clockwise / counter-clockwise.
319        nbr_i = next_scan_nbr(nbr_i, scan);
320
321        // PORT L922–L923: the new neighbor's coordinates, around the feature point.
322        cur_nbr_x = cur_x_loc + NBR8_DX[nbr_i as usize];
323        cur_nbr_y = cur_y_loc + NBR8_DY[nbr_i as usize];
324
325        // PORT L926–L929: a neighbor outside the image ends the trace (failure).
326        if cur_nbr_x < 0 || cur_nbr_x >= iw || cur_nbr_y < 0 || cur_nbr_y >= ih {
327            return None;
328        }
329
330        // PORT L932: the new neighbor's pixel value.
331        cur_nbr_pix = bdata[(cur_nbr_y * iw + cur_nbr_x) as usize];
332
333        // PORT L938: a feature-colored pixel preceded by an edge-colored one is a candidate.
334        if cur_nbr_pix == feature_pix && prev_nbr_pix == edge_pix {
335            // PORT L943: corners sit at the odd neighbor indices; test them for exposure.
336            if nbr_i % 2 != 0 {
337                // PORT L945–L947: look ahead one more neighbor.
338                let ni = next_scan_nbr(nbr_i, scan);
339                let nx = cur_x_loc + NBR8_DX[ni as usize];
340                let ny = cur_y_loc + NBR8_DY[ni as usize];
341                // PORT L949–L952: look-ahead neighbor out of bounds ends the trace (failure).
342                if nx < 0 || nx >= iw || ny < 0 || ny >= ih {
343                    return None;
344                }
345                let npix = bdata[(ny * iw + nx) as usize];
346
347                // PORT L957: the corner is NOT exposed → accept it as the next contour point.
348                if npix == feature_pix {
349                    return Some((cur_nbr_x, cur_nbr_y, prev_nbr_x, prev_nbr_y));
350                }
351                // PORT L966–L978: exposed corner → skip it by adopting the look-ahead neighbor and
352                // advancing both the neighbor index and the scan count an extra step.
353                cur_nbr_x = nx;
354                cur_nbr_y = ny;
355                cur_nbr_pix = npix;
356                nbr_i = ni;
357                i += 1;
358            }
359            // PORT L980–L989: non-corner neighbor → accept it as the next contour point.
360            else {
361                return Some((cur_nbr_x, cur_nbr_y, prev_nbr_x, prev_nbr_y));
362            }
363        }
364
365        i += 1;
366    }
367
368    // PORT L998: no valid pair among the eight neighbors (an isolated pixel) → failure.
369    None
370}
371
372/// Trace a feature's interior contour up to `max_len` points in one direction — port of stock
373/// `trace_contour` (`contour.c` L653).
374///
375/// Starts at feature point `(x_loc, y_loc)` with adjacent edge pixel `(x_edge, y_edge)` and walks the
376/// contour in the `scan` direction, one [`next_contour_pixel`] step at a time. If the walk reaches
377/// the loop-trigger point `(x_loop, y_loop)`, it stops and reports a [`TraceResult::Loop`] — passing
378/// that point independently lets successive half-traces from a common start detect a loop spanning
379/// both. `bdata` is the binary image (`0 == white/valley`, `1 == black/ridge`), `iw`×`ih` pixels.
380#[expect(clippy::too_many_arguments)]
381pub(crate) fn trace_contour(
382    max_len: i32,
383    x_loop: i32,
384    y_loop: i32,
385    x_loc: i32,
386    y_loc: i32,
387    x_edge: i32,
388    y_edge: i32,
389    scan: ScanDir,
390    bdata: &[u8],
391    iw: i32,
392    ih: i32,
393) -> TraceResult {
394    // PORT L669–L672: the feature and edge pixels must be opposite colors, else the trace can't work.
395    if bdata[(y_loc * iw + x_loc) as usize] == bdata[(y_edge * iw + x_edge) as usize] {
396        return TraceResult::Ignore;
397    }
398
399    // PORT L675/L682: allocate the contour buffers and zero the point counter (implicit in `Vec`).
400    let mut contour = Contour::with_capacity(max_len.max(0) as usize);
401
402    // PORT L685–L688: seed the "current" feature/edge pair at the starting point.
403    let mut cur_x_loc = x_loc;
404    let mut cur_y_loc = y_loc;
405    let mut cur_x_edge = x_edge;
406    let mut cur_y_edge = y_edge;
407
408    // PORT L691: collect up to `max_len` contour points.
409    let mut i = 0;
410    while i < max_len {
411        // PORT L693–L697: find the next contour pixel.
412        if let Some((next_x_loc, next_y_loc, next_x_edge, next_y_edge)) = next_contour_pixel(
413            cur_x_loc, cur_y_loc, cur_x_edge, cur_y_edge, scan, bdata, iw, ih,
414        ) {
415            // PORT L701–L710: reached the loop-trigger point → return the contour so far as a loop.
416            if next_x_loc == x_loop && next_y_loc == y_loop {
417                return TraceResult::Loop(contour);
418            }
419
420            // PORT L714–L719: store the new contour point.
421            contour.push(next_x_loc, next_y_loc, next_x_edge, next_y_edge);
422
423            // PORT L722–L725: advance the current pair.
424            cur_x_loc = next_x_loc;
425            cur_y_loc = next_y_loc;
426            cur_x_edge = next_x_edge;
427            cur_y_edge = next_y_edge;
428        } else {
429            // PORT L728–L738: no further contour pixel → stop short, returning what was found.
430            return TraceResult::Traced(contour);
431        }
432
433        i += 1;
434    }
435
436    // PORT L745–L752: collected the full `max_len` points.
437    TraceResult::Traced(contour)
438}
439
440/// Walk a feature's contour looking for a specific point — port of stock `search_contour`
441/// (`contour.c` L787).
442///
443/// Steps up to `search_len` points along the contour from `(x_loc, y_loc)`/`(x_edge, y_edge)` in the
444/// `scan` direction, returning `true` (stock `FOUND`) the moment the traced contour point equals
445/// `(x_search, y_search)`, or `false` (stock `NOT_FOUND`) if the point is not met within
446/// `search_len` steps or the trace terminates early.
447#[expect(clippy::too_many_arguments)]
448pub(crate) fn search_contour(
449    x_search: i32,
450    y_search: i32,
451    search_len: i32,
452    x_loc: i32,
453    y_loc: i32,
454    x_edge: i32,
455    y_edge: i32,
456    scan: ScanDir,
457    bdata: &[u8],
458    iw: i32,
459    ih: i32,
460) -> bool {
461    // PORT L801–L804: seed the current feature/edge pair.
462    let mut cur_x_loc = x_loc;
463    let mut cur_y_loc = y_loc;
464    let mut cur_x_edge = x_edge;
465    let mut cur_y_edge = y_edge;
466
467    // PORT L807: walk up to `search_len` contour points.
468    let mut i = 0;
469    while i < search_len {
470        // PORT L809–L813: find the next contour pixel.
471        if let Some((next_x_loc, next_y_loc, next_x_edge, next_y_edge)) = next_contour_pixel(
472            cur_x_loc, cur_y_loc, cur_x_edge, cur_y_edge, scan, bdata, iw, ih,
473        ) {
474            // PORT L816–L819: found the searched-for point.
475            if next_x_loc == x_search && next_y_loc == y_search {
476                return true;
477            }
478
479            // PORT L821–L825: advance the current pair.
480            cur_x_loc = next_x_loc;
481            cur_y_loc = next_y_loc;
482            cur_x_edge = next_x_edge;
483            cur_y_edge = next_y_edge;
484        } else {
485            // PORT L828–L831: trace ended early → not found.
486            return false;
487        }
488
489        i += 1;
490    }
491
492    // PORT L836: exhausted the search length without finding the point.
493    false
494}
495
496/// Extract a fixed-length contour centered on a feature point — port of stock `get_centered_contour`
497/// (`contour.c` L457).
498///
499/// Traces one half clockwise and the other counter-clockwise (each up to `half_contour` points),
500/// using the far end of the first half as the second half's loop-trigger. On success both halves are
501/// concatenated — first half reversed (far end first), then the feature point, then the second half
502/// forward — into a contour of `2 * half_contour + 1` points ([`CenteredContour::Ok`]). Any loop,
503/// impossible trace, or short half yields the corresponding non-`Ok` variant with no contour.
504#[expect(clippy::too_many_arguments)]
505pub(crate) fn get_centered_contour(
506    half_contour: i32,
507    x_loc: i32,
508    y_loc: i32,
509    x_edge: i32,
510    y_edge: i32,
511    bdata: &[u8],
512    iw: i32,
513    ih: i32,
514) -> CenteredContour {
515    // PORT L478–L480: first half contour, traced clockwise from the feature point.
516    let half1 = match trace_contour(
517        half_contour,
518        x_loc,
519        y_loc,
520        x_loc,
521        y_loc,
522        x_edge,
523        y_edge,
524        ScanDir::Clockwise,
525        bdata,
526        iw,
527        ih,
528    ) {
529        // PORT L489–L491: trace impossible.
530        TraceResult::Ignore => return CenteredContour::Ignore,
531        // PORT L494–L499: first half looped → discard and report.
532        TraceResult::Loop(_) => return CenteredContour::Loop,
533        TraceResult::Traced(c) => c,
534    };
535
536    // PORT L502–L507: first half must reach the requested length.
537    if (half1.len() as i32) < half_contour {
538        return CenteredContour::Incomplete;
539    }
540
541    // PORT L513–L516: second half, traced counter-clockwise; the first half's far end is the
542    // loop-trigger so a loop spanning both halves is detected.
543    let last = half1.len() - 1;
544    let half2 = match trace_contour(
545        half_contour,
546        half1.x[last],
547        half1.y[last],
548        x_loc,
549        y_loc,
550        x_edge,
551        y_edge,
552        ScanDir::CounterClockwise,
553        bdata,
554        iw,
555        ih,
556    ) {
557        // PORT L525–L530: second trace impossible.
558        TraceResult::Ignore => return CenteredContour::Ignore,
559        // PORT L533–L539: second half looped → discard and report.
560        TraceResult::Loop(_) => return CenteredContour::Loop,
561        TraceResult::Traced(c) => c,
562    };
563
564    // PORT L542–L548: second half must reach the requested length.
565    if (half2.len() as i32) < half_contour {
566        return CenteredContour::Incomplete;
567    }
568
569    // PORT L555/L573–L598: concatenate — first half reversed, feature point, second half forward.
570    let max_contour = (half_contour << 1) + 1;
571    let mut contour = Contour::with_capacity(max_contour.max(0) as usize);
572    contour.extend_rev(&half1);
573    contour.push(x_loc, y_loc, x_edge, y_edge);
574    contour.extend_fwd(&half2);
575
576    // PORT L603–L611: return the centered contour.
577    CenteredContour::Ok(contour)
578}
579
580/// Extract a fixed-length contour of a high-curvature feature edge — port of stock
581/// `get_high_curvature_contour` (`contour.c` L228).
582///
583/// Like [`get_centered_contour`] but tolerant of loops: if the first half forms a loop the loop's
584/// contour (feature point followed by the first half reversed) is returned as
585/// [`HighCurvatureContour::Loop`]; if the second half loops the two halves are still concatenated and
586/// returned as a loop. A full non-loop trace yields [`HighCurvatureContour::Ok`]; a trace that cannot
587/// reach full length yields [`HighCurvatureContour::Empty`] (no contour).
588#[expect(clippy::too_many_arguments)]
589pub(crate) fn get_high_curvature_contour(
590    half_contour: i32,
591    x_loc: i32,
592    y_loc: i32,
593    x_edge: i32,
594    y_edge: i32,
595    bdata: &[u8],
596    iw: i32,
597    ih: i32,
598) -> HighCurvatureContour {
599    // PORT L243: maximum full contour length (two halves + the feature point).
600    let max_contour = (half_contour << 1) + 1;
601
602    // PORT L249–L251: first half contour, traced clockwise from the feature point.
603    let half1 = match trace_contour(
604        half_contour,
605        x_loc,
606        y_loc,
607        x_loc,
608        y_loc,
609        x_edge,
610        y_edge,
611        ScanDir::Clockwise,
612        bdata,
613        iw,
614        ih,
615    ) {
616        // PORT L254–L256: trace impossible → empty result.
617        TraceResult::Ignore => return HighCurvatureContour::Empty,
618        // PORT L259–L301: first half looped → return the feature point then the half reversed.
619        TraceResult::Loop(loop_half) => {
620            let mut contour = Contour::with_capacity(loop_half.len() + 1);
621            contour.push(x_loc, y_loc, x_edge, y_edge);
622            contour.extend_rev(&loop_half);
623            return HighCurvatureContour::Loop(contour);
624        }
625        TraceResult::Traced(c) => c,
626    };
627
628    // PORT L310–L315: first half not complete → empty result.
629    if (half1.len() as i32) < half_contour {
630        return HighCurvatureContour::Empty;
631    }
632
633    // PORT L321–L324: second half, traced counter-clockwise, with the first half's far end as the
634    // loop-trigger. `looped` records whether it closed a loop (stock's `ret == LOOP_FOUND`).
635    let last = half1.len() - 1;
636    let (half2, looped) = match trace_contour(
637        half_contour,
638        half1.x[last],
639        half1.y[last],
640        x_loc,
641        y_loc,
642        x_edge,
643        y_edge,
644        ScanDir::CounterClockwise,
645        bdata,
646        iw,
647        ih,
648    ) {
649        // PORT L327–L332: second trace impossible → empty result.
650        TraceResult::Ignore => return HighCurvatureContour::Empty,
651        TraceResult::Loop(c) => (c, true),
652        TraceResult::Traced(c) => (c, false),
653    };
654
655    // PORT L344–L350: a non-loop second half that is too short → empty result.
656    if !looped && (half2.len() as i32) < half_contour {
657        return HighCurvatureContour::Empty;
658    }
659
660    // PORT L359/L377–L402: concatenate — first half reversed, feature point, second half forward.
661    let mut contour = Contour::with_capacity(max_contour.max(0) as usize);
662    contour.extend_rev(&half1);
663    contour.push(x_loc, y_loc, x_edge, y_edge);
664    contour.extend_fwd(&half2);
665
666    // PORT L414–L416: a looping second half returns a loop, otherwise a complete contour.
667    if looped {
668        HighCurvatureContour::Loop(contour)
669    } else {
670        HighCurvatureContour::Ok(contour)
671    }
672}
673
674/// Locate the point of highest curvature (minimum interior angle) along a contour — port of stock
675/// `min_contour_theta` (`contour.c` L1097).
676///
677/// At each interior point a left and right segment extend `angle_edge` points either side; the angle
678/// between the center→left and center→right lines is measured (via [`angle2line`]), reduced to its
679/// inner value `min(dθ, 2π − dθ)`, and quantized through [`trunc_dbl_precision`] at [`TRUNC_SCALE`]
680/// so the comparison is architecture-independent. The smallest such angle and its center index are
681/// returned; a perfectly flat contour (no strict minimum) reports the contour's midpoint.
682///
683/// Returns `None` (stock `IGNORE`) when the contour is shorter than `2 * angle_edge + 1` points, else
684/// `Some((min_i, min_theta))`.
685pub(crate) fn min_contour_theta(
686    angle_edge: i32,
687    contour_x: &[i32],
688    contour_y: &[i32],
689) -> Option<(i32, f64)> {
690    let ncontour = contour_x.len() as i32;
691
692    // PORT L1107–L1109: too short to analyze → ignore.
693    if ncontour < (angle_edge << 1) + 1 {
694        return None;
695    }
696
697    // PORT L1112–L1116: running minimum seeded at π (quantized for reproducibility).
698    let mut min_theta = trunc_dbl_precision(std::f64::consts::PI, TRUNC_SCALE);
699    // PORT L1117: no minimum found yet.
700    let mut min_i: i32 = -1;
701
702    // PORT L1119–L1123: left / center / right sample indices, `angle_edge` apart.
703    let mut pleft = 0;
704    let mut pcenter = angle_edge;
705    let mut pright = pcenter + angle_edge;
706
707    // PORT L1126: slide the triple along the contour until the right point runs off the end.
708    while pright < ncontour {
709        // PORT L1128–L1132: angles from the center point to the left and right sample points.
710        let theta1 = angle2line(
711            contour_x[pcenter as usize],
712            contour_y[pcenter as usize],
713            contour_x[pleft as usize],
714            contour_y[pleft as usize],
715        );
716        let theta2 = angle2line(
717            contour_x[pcenter as usize],
718            contour_y[pcenter as usize],
719            contour_x[pright as usize],
720            contour_y[pright as usize],
721        );
722
723        // PORT L1136–L1140: inner angle between them, quantized.
724        let mut dtheta = (theta2 - theta1).abs();
725        dtheta = dtheta.min(std::f64::consts::PI * 2.0 - dtheta);
726        dtheta = trunc_dbl_precision(dtheta, TRUNC_SCALE);
727
728        // PORT L1143–L1146: track the running minimum.
729        if dtheta < min_theta {
730            min_i = pcenter;
731            min_theta = dtheta;
732        }
733
734        // PORT L1149–L1151: advance all three sample points.
735        pleft += 1;
736        pcenter += 1;
737        pright += 1;
738    }
739
740    // PORT L1156–L1164: a flat contour (no strict minimum) reports its midpoint.
741    if min_i == -1 {
742        Some((ncontour >> 1, min_theta))
743    } else {
744        Some((min_i, min_theta))
745    }
746}
747
748/// Bounding box of a contour's interior points — port of stock `contour_limits` (`contour.c` L1185).
749///
750/// Returns `(xmin, ymin, xmax, ymax)`. As in the reference (which calls `minv`/`maxv`), the contour
751/// is assumed non-empty.
752///
753/// # Panics
754///
755/// Panics on an empty contour, matching the stock precondition ("The list is assumed to be NOT
756/// empty").
757pub(crate) fn contour_limits(contour_x: &[i32], contour_y: &[i32]) -> (i32, i32, i32, i32) {
758    // PORT L1189–L1195: per-axis minima and maxima (stock `minv`/`maxv`).
759    let xmin = *contour_x.iter().min().expect("contour is non-empty");
760    let ymin = *contour_y.iter().min().expect("contour is non-empty");
761    let xmax = *contour_x.iter().max().expect("contour is non-empty");
762    let ymax = *contour_y.iter().max().expect("contour is non-empty");
763    (xmin, ymin, xmax, ymax)
764}
765
766/// Adjust a diagonal feature/edge pixel pair to a cardinal one — port of stock `fix_edge_pixel_pair`
767/// (`contour.c` L1222).
768///
769/// The contour tracer requires the edge pixel to sit N/S/E/W of the feature pixel. If the supplied
770/// pair are diagonal neighbors, one of the two intervening pixels (both retaining the required
771/// colors) is chosen so the resulting pair is cardinally adjacent: the edge pixel is shifted onto
772/// whichever intervening pixel is *not* the feature's color, or — if both are — the feature pixel
773/// itself is shifted onto the diagonal (an exposed corner). Non-diagonal pairs are returned
774/// unchanged. Returns the adjusted `(feat_x, feat_y, edge_x, edge_y)`.
775///
776// PORT: stock takes `ih` but never reads it (only `iw` indexes `bdata`), so it is dropped here. The
777// four in/out pointer parameters become one returned tuple. As in the reference, the `p1`/`p2`
778// look-ups are not bounds-checked — callers supply an interior feature pixel whose diagonal
779// intervening pixels lie within the image.
780pub(crate) fn fix_edge_pixel_pair(
781    feat_x: i32,
782    feat_y: i32,
783    edge_x: i32,
784    edge_y: i32,
785    bdata: &[u8],
786    iw: i32,
787) -> (i32, i32, i32, i32) {
788    // PORT L1230: the feature pixel's color — the value the retained pixels must match.
789    let feature_pix = bdata[(feat_y * iw + feat_x) as usize];
790
791    // PORT L1233–L1236: current (feature) and previous (edge) points.
792    let cx = feat_x;
793    let mut cy = feat_y;
794    let mut px = edge_x;
795    let mut py = edge_y;
796
797    // PORT L1239–L1240: deltas from feature to edge.
798    let dx = px - cx;
799    let dy = py - cy;
800
801    // PORT L1249: only diagonal neighbors need fixing.
802    if dx.abs() == 1 && dy.abs() == 1 {
803        // PORT L1272–L1273: if the pixel where x changes (p1 = px-dx, py) is NOT the feature color,
804        // move the edge x-coord onto it.
805        if bdata[(py * iw + (px - dx)) as usize] != feature_pix {
806            px -= dx;
807        }
808        // PORT L1276–L1278: else if the pixel where y changes (p2 = px, py-dy) is NOT the feature
809        // color, move the edge y-coord onto it.
810        else if bdata[((py - dy) * iw + px) as usize] != feature_pix {
811            py -= dy;
812        }
813        // PORT L1279–L1284: else the feature pixel is exposed on a corner — shift it onto the
814        // diagonal (which carries the feature color).
815        else {
816            cy += dy;
817        }
818    }
819
820    // PORT L1287–L1290 (and the unchanged non-diagonal case): the resulting pair.
821    (cx, cy, px, py)
822}
823
824#[cfg(test)]
825mod tests {
826    use super::*;
827
828    /// A 5×5 image whose bottom three rows (`y >= 2`) are ridge (`1`) and top two rows are valley
829    /// (`0`) — a straight horizontal feature edge along `y == 2`.
830    fn half_plane() -> (Vec<u8>, i32, i32) {
831        let iw = 5;
832        let ih = 5;
833        let mut b = vec![0u8; (iw * ih) as usize];
834        for y in 2..ih {
835            for x in 0..iw {
836                b[(y * iw + x) as usize] = 1;
837            }
838        }
839        (b, iw, ih)
840    }
841
842    /// A 5×5 image with a solid 3×3 ridge block at `x,y ∈ [1,3]`, valley elsewhere — a closed
843    /// feature whose interior edge is an eight-pixel loop.
844    fn block_3x3() -> (Vec<u8>, i32, i32) {
845        let iw = 5;
846        let ih = 5;
847        let mut b = vec![0u8; (iw * ih) as usize];
848        for y in 1..=3 {
849            for x in 1..=3 {
850                b[(y * iw + x) as usize] = 1;
851            }
852        }
853        (b, iw, ih)
854    }
855
856    #[test]
857    fn scan_nbr_cardinal_directions() {
858        // Second pixel due S / N / E / W of the first.
859        assert_eq!(start_scan_nbr(2, 2, 2, 3), SOUTH);
860        assert_eq!(start_scan_nbr(2, 2, 2, 1), NORTH);
861        assert_eq!(start_scan_nbr(2, 2, 3, 2), EAST);
862        assert_eq!(start_scan_nbr(2, 2, 1, 2), WEST);
863        // A diagonal pair is not aligned.
864        assert_eq!(start_scan_nbr(2, 2, 3, 3), INVALID_DIR);
865    }
866
867    #[test]
868    fn next_scan_nbr_wraps_both_ways() {
869        assert_eq!(next_scan_nbr(0, ScanDir::Clockwise), 1);
870        assert_eq!(next_scan_nbr(7, ScanDir::Clockwise), 0);
871        assert_eq!(next_scan_nbr(0, ScanDir::CounterClockwise), 7);
872        assert_eq!(next_scan_nbr(7, ScanDir::CounterClockwise), 6);
873    }
874
875    #[test]
876    fn next_contour_pixel_walks_along_a_straight_edge() {
877        let (b, iw, ih) = half_plane();
878        // Feature (2,2) with edge due north (2,1): clockwise steps east, counter-clockwise west.
879        assert_eq!(
880            next_contour_pixel(2, 2, 2, 1, ScanDir::Clockwise, &b, iw, ih),
881            Some((3, 2, 3, 1))
882        );
883        assert_eq!(
884            next_contour_pixel(2, 2, 2, 1, ScanDir::CounterClockwise, &b, iw, ih),
885            Some((1, 2, 1, 1))
886        );
887    }
888
889    #[test]
890    fn next_contour_pixel_none_for_isolated_pixel() {
891        let iw = 5;
892        let ih = 5;
893        let mut b = vec![0u8; (iw * ih) as usize];
894        b[(2 * iw + 2) as usize] = 1; // a single ridge pixel surrounded by valley
895        assert_eq!(
896            next_contour_pixel(2, 2, 2, 1, ScanDir::Clockwise, &b, iw, ih),
897            None
898        );
899    }
900
901    #[test]
902    fn trace_contour_ignores_same_colored_pair() {
903        let (b, iw, ih) = half_plane();
904        // Both (2,2) and (2,3) are ridge → not opposite → IGNORE.
905        assert_eq!(
906            trace_contour(4, 2, 2, 2, 2, 2, 3, ScanDir::Clockwise, &b, iw, ih),
907            TraceResult::Ignore
908        );
909    }
910
911    #[test]
912    fn trace_contour_stops_short_at_image_edge() {
913        let (b, iw, ih) = half_plane();
914        // Walk east along the edge; it runs off the right side after two points.
915        let res = trace_contour(4, 2, 2, 2, 2, 2, 1, ScanDir::Clockwise, &b, iw, ih);
916        let TraceResult::Traced(c) = res else {
917            panic!("expected a short traced contour, got {res:?}");
918        };
919        assert_eq!(c.x, vec![3, 4]);
920        assert_eq!(c.y, vec![2, 2]);
921        assert_eq!(c.ex, vec![3, 4]);
922        assert_eq!(c.ey, vec![1, 1]);
923    }
924
925    #[test]
926    fn trace_contour_detects_a_loop_around_a_block() {
927        let (b, iw, ih) = block_3x3();
928        // Start at the block's top-left interior pixel (1,1) with its north edge (1,0); the trace
929        // walks clockwise around the eight-pixel interior edge back to (1,1).
930        let res = trace_contour(20, 1, 1, 1, 1, 1, 0, ScanDir::Clockwise, &b, iw, ih);
931        let TraceResult::Loop(c) = res else {
932            panic!("expected a loop, got {res:?}");
933        };
934        // Seven points collected before stepping back onto the start point.
935        assert_eq!(c.x, vec![2, 3, 3, 3, 2, 1, 1]);
936        assert_eq!(c.y, vec![1, 1, 2, 3, 3, 3, 2]);
937    }
938
939    #[test]
940    fn search_contour_finds_and_misses() {
941        let (b, iw, ih) = block_3x3();
942        // (3,1) is two clockwise steps from the start and IS on the contour.
943        assert!(search_contour(
944            3,
945            1,
946            8,
947            1,
948            1,
949            1,
950            0,
951            ScanDir::Clockwise,
952            &b,
953            iw,
954            ih
955        ));
956        // (4,4) is off the feature entirely and is never met.
957        assert!(!search_contour(
958            4,
959            4,
960            8,
961            1,
962            1,
963            1,
964            0,
965            ScanDir::Clockwise,
966            &b,
967            iw,
968            ih
969        ));
970    }
971
972    #[test]
973    fn angle2line_flat_and_axis_aligned() {
974        // Coincident points → both deltas below MIN_SLOPE_DELTA → 0.0.
975        assert_eq!(angle2line(3, 3, 3, 3), 0.0);
976        // Horizontal to the right: dy = 0, dx = +1 → atan2(0, 1) == 0.
977        assert_eq!(angle2line(0, 0, 1, 0), 0.0);
978        // Straight up in image coords (to smaller y): dy = fy-ty = 0-(-1)? use (0,0)->(0,1):
979        // dy = 0-1 = -1, dx = 0 → atan2(-1, 0) == -π/2.
980        assert!((angle2line(0, 0, 0, 1) + std::f64::consts::FRAC_PI_2).abs() < 1e-12);
981    }
982
983    #[test]
984    fn min_contour_theta_ignores_short_contours() {
985        // ncontour (2) < 2*angle_edge+1 (3) → IGNORE.
986        assert_eq!(min_contour_theta(1, &[0, 1], &[0, 0]), None);
987    }
988
989    #[test]
990    fn min_contour_theta_flat_reports_midpoint() {
991        // A collinear contour has a constant angle of π everywhere → no strict minimum → midpoint.
992        let x = [0, 1, 2, 3, 4];
993        let y = [0, 0, 0, 0, 0];
994        let expected_theta = trunc_dbl_precision(std::f64::consts::PI, TRUNC_SCALE);
995        assert_eq!(min_contour_theta(1, &x, &y), Some((2, expected_theta)));
996    }
997
998    #[test]
999    fn min_contour_theta_finds_right_angle() {
1000        // A 90-degree turn at index 1: left (0,0), center (1,0), right (1,1) → inner angle π/2.
1001        let x = [0, 1, 1];
1002        let y = [0, 0, 1];
1003        let expected_theta = trunc_dbl_precision(std::f64::consts::FRAC_PI_2, TRUNC_SCALE);
1004        assert_eq!(min_contour_theta(1, &x, &y), Some((1, expected_theta)));
1005    }
1006
1007    #[test]
1008    fn contour_limits_bounds_the_points() {
1009        let x = [3, 1, 4, 1, 5];
1010        let y = [2, 7, 1, 8, 2];
1011        assert_eq!(contour_limits(&x, &y), (1, 1, 5, 8));
1012    }
1013
1014    #[test]
1015    fn fix_edge_pixel_pair_leaves_cardinal_pairs_untouched() {
1016        let (b, iw, _) = half_plane();
1017        // Edge already due north of the feature → unchanged.
1018        assert_eq!(fix_edge_pixel_pair(2, 2, 2, 1, &b, iw), (2, 2, 2, 1));
1019    }
1020
1021    #[test]
1022    fn fix_edge_pixel_pair_shifts_edge_off_the_diagonal() {
1023        // Lone ridge pixel at (2,2); the diagonal edge (3,1) is valley. p1 = (px-dx, py) = (2,1) is
1024        // valley (≠ feature) → the edge x-coord moves onto it, giving a due-north pair.
1025        let iw = 5;
1026        let ih = 5;
1027        let mut b = vec![0u8; (iw * ih) as usize];
1028        b[(2 * iw + 2) as usize] = 1;
1029        assert_eq!(fix_edge_pixel_pair(2, 2, 3, 1, &b, iw), (2, 2, 2, 1));
1030        let _ = ih;
1031    }
1032
1033    #[test]
1034    fn fix_edge_pixel_pair_shifts_feature_on_exposed_corner() {
1035        // Feature (2,2)=1 with a diagonal edge at (3,1). Both intervening pixels p1=(2,1) and
1036        // p2=(3,2) are ridge (== feature), so the feature pixel itself shifts by dy onto the
1037        // diagonal: cy += dy = 2 + (-1) = 1.
1038        let iw = 5;
1039        let ih = 5;
1040        let mut b = vec![0u8; (iw * ih) as usize];
1041        for &(x, y) in &[(2, 2), (2, 1), (3, 2)] {
1042            b[(y * iw + x) as usize] = 1;
1043        }
1044        let _ = ih;
1045        assert_eq!(fix_edge_pixel_pair(2, 2, 3, 1, &b, iw), (2, 1, 3, 1));
1046    }
1047
1048    #[test]
1049    fn get_centered_contour_concatenates_two_halves() {
1050        // On the straight edge a centered contour of half_contour=1 needs one point either side of
1051        // the feature. Feature (2,2)/edge (2,1): clockwise half → (3,2), ccw half → (1,2).
1052        let (b, iw, ih) = half_plane();
1053        let res = get_centered_contour(1, 2, 2, 2, 1, &b, iw, ih);
1054        let CenteredContour::Ok(c) = res else {
1055            panic!("expected a centered contour, got {res:?}");
1056        };
1057        // Reversed first half (single point), feature point, forward second half.
1058        assert_eq!(c.x, vec![3, 2, 1]);
1059        assert_eq!(c.y, vec![2, 2, 2]);
1060        assert_eq!(c.len(), 3);
1061    }
1062
1063    #[test]
1064    fn get_centered_contour_incomplete_when_edge_too_close() {
1065        // half_contour=3 cannot fit either side before the 5-wide image edge → INCOMPLETE.
1066        let (b, iw, ih) = half_plane();
1067        assert_eq!(
1068            get_centered_contour(3, 2, 2, 2, 1, &b, iw, ih),
1069            CenteredContour::Incomplete
1070        );
1071    }
1072
1073    #[test]
1074    fn get_centered_contour_ignores_same_colored_pair() {
1075        let (b, iw, ih) = half_plane();
1076        assert_eq!(
1077            get_centered_contour(1, 2, 2, 2, 3, &b, iw, ih),
1078            CenteredContour::Ignore
1079        );
1080    }
1081}