Skip to main content

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}