fprint_mindtct/detect/chaincod.rs
1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! 8-connected chain-code of a traced contour and its directional turn analysis — faithful port of
6//! stock NBIS `mindtct/src/lib/mindtct/chaincod.c` (`chain_code_loop`, `is_chain_clockwise`).
7//!
8//! A contour is an ordered list of pixel coordinates whose successive points are 8-adjacent.
9//! [`chain_code_loop`] encodes each step (including the wrap from the last point back to the first)
10//! as one of eight direction codes; [`is_chain_clockwise`] folds the successive direction changes
11//! into a signed turn total to decide the loop's winding.
12
13// PORT: stock `NBR8_DIM` (`lfs.h` L500) — the chain-code lookup matrix is `NBR8_DIM`×`NBR8_DIM`.
14const NBR8_DIM: i32 = 3;
15
16/// PORT: stock `chaincodes_nbr8` (`globals.c` L250) — the 8-connected chain-code lookup matrix,
17/// row-major `NBR8_DIM`×`NBR8_DIM`. Indexed by `(dy + 1) * NBR8_DIM + (dx + 1)` for a step whose
18/// per-axis delta `dx`/`dy` lies in `-1..=1`, it maps that neighbor offset to its direction code:
19///
20/// ```text
21/// dx=-1 dx=0 dx=1
22/// dy=-1: 3 2 1
23/// dy= 0: 4 -1 0
24/// dy= 1: 5 6 7
25/// ```
26///
27/// The center cell (`dx == dy == 0`, no movement) holds the sentinel `-1`; a well-formed contour
28/// never produces a zero-length step, so it is never selected.
29const CHAINCODES_NBR8: [i32; (NBR8_DIM * NBR8_DIM) as usize] = [3, 2, 1, 4, -1, 0, 5, 6, 7];
30
31// PORT: stock `TRUE`/`FALSE` (`lfs.h` L673, L676). `is_chain_clockwise` returns these — or the
32// caller-supplied `default_ret`, which is itself an application-specific `int` — so the return type
33// stays `i32` rather than `bool` to preserve that three-way contract verbatim.
34const TRUE: i32 = 1;
35const FALSE: i32 = 0;
36
37/// Convert a feature's contour points into an 8-connected chain-code vector — stock
38/// `chain_code_loop` (`chaincod.c` L85).
39///
40/// Each element is the direction taken between two adjacent contour points, with a final code
41/// wrapping the last point back to the first (closing the loop). The returned vector has one code
42/// per contour point (stock `onchain == ncontour`).
43///
44/// `contour_x` and `contour_y` are the parallel coordinate lists; their shared length is the stock
45/// `ncontour` (the caller supplies them in lock-step, exactly as the reference does). If the contour
46/// has three or fewer points it does not form a loop, so an **empty** vector is returned (stock
47/// `onchain = 0` with no allocation) — the port's stand-in for that early exit.
48///
49/// PORT: the stock `-170` `malloc`-failure path is unreachable here — `Vec` allocation aborts rather
50/// than returning an error code — so the return type is the chain itself, not a `Result`.
51///
52/// # Panics
53///
54/// Panics on an out-of-bounds `CHAINCODES_NBR8` index if two successive contour points are not
55/// 8-adjacent (`|dx| > 1` or `|dy| > 1`), where stock C would read past the matrix. Contour tracing
56/// guarantees 8-adjacency, so this cannot occur for a valid contour.
57pub(crate) fn chain_code_loop(contour_x: &[i32], contour_y: &[i32]) -> Vec<i32> {
58 let ncontour = contour_x.len() as i32;
59
60 // If we don't have at least 3 points in the contour, then we don't have a loop, so return an
61 // empty chain (stock sets `onchain = 0` and returns with no allocation).
62 if ncontour <= 3 {
63 return Vec::new();
64 }
65
66 // The chain is the same length as the contour: one code between each pair of adjacent points,
67 // including the last-to-first code that completes the loop.
68 let mut chain = vec![0_i32; ncontour as usize];
69
70 // For each neighboring point, with `i` on the previous neighbor and `j` on the next, derive the
71 // chain-code index from the neighbor deltas. The deltas lie in `-1..=1`, so they are incremented
72 // by one to index the lookup matrix.
73 let mut i = 0_i32;
74 let mut j = 1_i32;
75 while i < ncontour - 1 {
76 let dx = contour_x[j as usize] - contour_x[i as usize];
77 let dy = contour_y[j as usize] - contour_y[i as usize];
78 chain[i as usize] = CHAINCODES_NBR8[((dy + 1) * NBR8_DIM + dx + 1) as usize];
79 i += 1;
80 j += 1;
81 }
82
83 // Now derive the chain code between the last and first points in the contour list. (`i` is left
84 // at `ncontour - 1` by the loop above, exactly as in the reference.)
85 let dx = contour_x[0] - contour_x[i as usize];
86 let dy = contour_y[0] - contour_y[i as usize];
87 chain[i as usize] = CHAINCODES_NBR8[((dy + 1) * NBR8_DIM + dx + 1) as usize];
88
89 chain
90}
91
92/// Decide whether an 8-connected chain-code vector is ordered clockwise — stock
93/// `is_chain_clockwise` (`chaincod.c` L156).
94///
95/// Accumulates the change in direction between each successive pair of codes (including the wrap
96/// from the last code back to the first), reducing each delta to its "inner" distance in `-3..=4`
97/// so a step across the `7 → 0` seam counts as a small turn rather than a large one. Left-hand turns
98/// increment the accumulator, right-hand turns decrement it.
99///
100/// Returns [`TRUE`] (`1`) when the net turn is negative (more right-hand turns → clockwise),
101/// [`FALSE`] (`0`) when it is positive (counter-clockwise), and the caller-supplied `default_ret`
102/// when the net turn is exactly zero (direction indeterminate).
103///
104/// `chain` is the chain-code vector; its length is the stock `nchain`. The caller must pass a
105/// non-empty chain — stock's only caller (`is_loop_clockwise`, `loop.c` L515) guards the empty case
106/// beforehand and returns its own default, so this routine indexes `chain[0]` unconditionally, just
107/// as the reference does.
108pub(crate) fn is_chain_clockwise(chain: &[i32], default_ret: i32) -> i32 {
109 let nchain = chain.len() as i32;
110
111 // Initialize the turn-accumulator to 0.
112 let mut sum = 0_i32;
113
114 // For each neighboring code, compute the difference in direction and accumulate. Each delta is
115 // reduced to its inner distance: a delta `>= 4` is a right-hand turn (subtract 8), a delta
116 // `<= -4` is a left-hand turn (add 8).
117 let mut i = 0_i32;
118 let mut j = 1_i32;
119 while i < nchain - 1 {
120 let mut d = chain[j as usize] - chain[i as usize];
121 if d >= 4 {
122 d -= 8;
123 } else if d <= -4 {
124 d += 8;
125 }
126 sum += d;
127 i += 1;
128 j += 1;
129 }
130
131 // Add the final delta between the last and first codes in the chain. (`i` is left at
132 // `nchain - 1` by the loop above.)
133 let mut d = chain[0] - chain[i as usize];
134 if d >= 4 {
135 d -= 8;
136 } else if d <= -4 {
137 d += 8;
138 }
139 sum += d;
140
141 // A net turn of zero means the direction is indeterminate → return the caller's default.
142 if sum == 0 {
143 default_ret
144 } else if sum > 0 {
145 // More left-hand than right-hand turns → counter-clockwise.
146 FALSE
147 } else {
148 // More right-hand than left-hand turns → clockwise.
149 TRUE
150 }
151}
152
153#[cfg(test)]
154mod tests {
155 use super::*;
156
157 /// A contour of three or fewer points is not a loop, so no chain is produced (stock
158 /// `onchain = 0`).
159 #[test]
160 fn too_few_points_yields_empty_chain() {
161 assert!(chain_code_loop(&[], &[]).is_empty());
162 assert!(chain_code_loop(&[0, 1], &[0, 0]).is_empty());
163 assert!(chain_code_loop(&[0, 1, 2], &[0, 0, 0]).is_empty());
164 }
165
166 // A 2×2 pixel square walked clockwise on screen (image coords, `y` increasing downward):
167 // right along the top, down the right side, left along the bottom, up the left side.
168 const SQUARE_X: [i32; 8] = [0, 1, 2, 2, 2, 1, 0, 0];
169 const SQUARE_Y: [i32; 8] = [0, 0, 0, 1, 2, 2, 2, 1];
170
171 /// Each 8-adjacent step maps to the expected direction code, and the wrap step (last → first)
172 /// closes the loop. Codes: `0`=E, `2`=N(up), `4`=W, `6`=S(down).
173 #[test]
174 fn square_contour_encodes_expected_codes() {
175 let chain = chain_code_loop(&SQUARE_X, &SQUARE_Y);
176 // E,E, S,S, W,W, N,N — the last two include the wrap from (0,1) back to (0,0).
177 assert_eq!(chain, vec![0, 0, 6, 6, 4, 4, 2, 2]);
178 // One code per contour point (stock `onchain == ncontour`).
179 assert_eq!(chain.len(), SQUARE_X.len());
180 }
181
182 /// The screen-clockwise square is reported clockwise (`TRUE`); reversing the point order flips
183 /// it to counter-clockwise (`FALSE`).
184 #[test]
185 fn winding_matches_traversal_order() {
186 let cw = chain_code_loop(&SQUARE_X, &SQUARE_Y);
187 assert_eq!(is_chain_clockwise(&cw, -1), TRUE);
188
189 let mut rx = SQUARE_X;
190 let mut ry = SQUARE_Y;
191 rx.reverse();
192 ry.reverse();
193 let ccw = chain_code_loop(&rx, &ry);
194 assert_eq!(is_chain_clockwise(&ccw, -1), FALSE);
195 }
196
197 /// A chain whose turns cancel to a net zero is indeterminate, so the caller's `default_ret` is
198 /// returned unchanged. `[0,4,0,4]` alternates E/W: each `±4` delta folds to the same sign and
199 /// the four cancel.
200 #[test]
201 fn indeterminate_winding_returns_default() {
202 let sentinel = 42;
203 assert_eq!(is_chain_clockwise(&[0, 4, 0, 4], sentinel), sentinel);
204 }
205
206 /// The inner-distance reduction folds a step across the `7 → 0` seam into a single unit turn
207 /// rather than a seven-unit one, so a chain rotating steadily through all eight directions winds
208 /// consistently (here counter-clockwise, `+8`).
209 #[test]
210 fn seam_crossing_folds_to_inner_distance() {
211 let chain = [0, 1, 2, 3, 4, 5, 6, 7];
212 assert_eq!(is_chain_clockwise(&chain, -1), FALSE);
213 }
214}