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}