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}