Skip to main content

fprint_mindtct/detect/
shape.rs

1// SPDX-FileCopyrightText: 2026 fprintd (pure-Rust) contributors
2//
3// SPDX-License-Identifier: MIT OR Apache-2.0
4
5//! Per-row shape representation of a closed loop contour — port of stock NBIS
6//! `mindtct/src/lib/mindtct/shape.c` (`alloc_shape`, `shape_from_contour`, `sort_row_on_x`, and the
7//! implicit `free_shape` folded into `Vec` ownership).
8//!
9//! [`fill_loop`](super::loops::fill_loop) needs, for each scanline the loop spans, the loop's contour
10//! points on that row sorted left-to-right so it can fill between them while skipping the gaps that
11//! concavities open up. A [`Shape`] holds one [`Row`] per scanline of the loop's bounding box, each
12//! carrying the distinct x-coordinates of the contour points on that row. See
13//! `docs/mindtct-algorithm.md`.
14
15use crate::num::bubble_sort_int_inc;
16
17use super::contour::contour_limits;
18
19/// One scanline of a [`Shape`] — the port's analogue of the stock `ROW` (`lfs.h`), one field per
20/// member that survives the `Vec` port.
21///
22/// PORT: stock `ROW` carries `y`, `xs`, `alloc`, and `npts`; `alloc`/`npts` collapse into the `Vec`'s
23/// capacity/length, leaving `y` and `xs`.
24#[derive(Clone, Debug, PartialEq, Eq)]
25pub(crate) struct Row {
26    /// Y-coordinate shared by every contour point on this row (stock `y`).
27    pub y: i32,
28    /// X-coordinates of the row's contour points, left-to-right after [`shape_from_contour`] sorts
29    /// them (stock `xs` / `npts`).
30    pub xs: Vec<i32>,
31}
32
33/// A loop contour reorganized by scanline — the port's analogue of the stock `SHAPE` (`lfs.h`).
34///
35/// PORT: stock `SHAPE` carries `ymin`, `ymax`, `nrows`, `alloc`, and `rows`; `nrows`/`alloc` collapse
36/// into the `rows` `Vec`. `free_shape` is `Vec` `Drop`, so it has no port-side routine.
37#[derive(Clone, Debug, PartialEq, Eq)]
38pub(crate) struct Shape {
39    /// One row per scanline of the loop's bounding box, top (`ymin`) to bottom (`ymax`).
40    pub rows: Vec<Row>,
41}
42
43/// Allocate a shape spanning scanlines `ymin..=ymax`, each row initially empty — port of stock
44/// `alloc_shape` (`shape.c` L84).
45///
46/// PORT: the reference pre-sizes each row's `xs` to `xmax - xmin + 1` (the maximum contiguous pixels
47/// possible on a row); here that becomes the `Vec` capacity hint, and the `-250..=-253` malloc-failure
48/// paths are unreachable (allocation aborts) and elided. `xmax` is used only for that hint.
49fn alloc_shape(xmin: i32, ymin: i32, xmax: i32, ymax: i32) -> Shape {
50    // PORT L91–L96: rows span the shape's y-limits; each may hold up to `xmax - xmin + 1` points.
51    let alloc_rows = ymax - ymin + 1;
52    let alloc_pts = (xmax - xmin + 1).max(0) as usize;
53
54    // PORT L127–L166: one empty row per scanline, carrying its y-coordinate.
55    let mut rows = Vec::with_capacity(alloc_rows.max(0) as usize);
56    for i in 0..alloc_rows {
57        rows.push(Row {
58            y: ymin + i,
59            xs: Vec::with_capacity(alloc_pts),
60        });
61    }
62
63    Shape { rows }
64}
65
66/// Reorganize a closed-loop contour into a per-row [`Shape`] — port of stock `shape_from_contour`
67/// (`shape.c` L250).
68///
69/// Bins each contour point onto the row of its y-coordinate (skipping x-coordinates already recorded
70/// for that row, as complex "pinching" contours revisit points), then sorts each row left-to-right on
71/// x. `contour_x`/`contour_y` are the loop's contour points (assumed non-empty by the caller).
72///
73/// # Errors
74///
75/// `Err(-260)` on the stock "row overflow" path — unreachable here (rows are sized to the bounding
76/// box), retained for a faithful transcription.
77pub(crate) fn shape_from_contour(contour_x: &[i32], contour_y: &[i32]) -> Result<Shape, i32> {
78    // PORT L262–L263: bounding box of the contour.
79    let (xmin, ymin, xmax, ymax) = contour_limits(contour_x, contour_y);
80
81    // PORT L266: allocate the empty per-scanline shape.
82    let mut shape = alloc_shape(xmin, ymin, xmax, ymax);
83
84    // PORT L269–L295: bin each contour point onto its row, de-duplicating x-coordinates.
85    for i in 0..contour_x.len() {
86        // PORT L274–L277: rows are indexed relative to the top-most scanline.
87        let row = &mut shape.rows[(contour_y[i] - ymin) as usize];
88        // PORT L282–L294: record the x-coordinate unless the row already holds it.
89        if !row.xs.contains(&contour_x[i]) {
90            // PORT L284–L289: a full row is impossible given the bounding-box sizing.
91            if row.xs.len() >= row.xs.capacity() {
92                return Err(-260);
93            }
94            row.xs.push(contour_x[i]);
95        }
96    }
97
98    // PORT L298–L300: sort each row's points increasing on x.
99    for row in &mut shape.rows {
100        sort_row_on_x(row);
101    }
102
103    // PORT L303–L306: return the shape.
104    Ok(shape)
105}
106
107/// Sort a row's x-coordinates left-to-right — port of stock `sort_row_on_x` (`shape.c` L317).
108///
109/// A stable increasing bubble sort, verbatim from the reference (the point count is small).
110fn sort_row_on_x(row: &mut Row) {
111    // PORT L322: increasing bubble sort of the row's x-coords.
112    bubble_sort_int_inc(&mut row.xs);
113}