checkerboard_calibrate/chessboard/
quad.rs

1// Copyright (C) The Strand-Braid Authors
2// SPDX-License-Identifier: MIT OR Apache-2.0
3
4//! Quad extraction — the part of OpenCV's `generateQuads` that turns a contour
5//! into a candidate chessboard square.
6//!
7//! For each contour, `approxPolyDP` is run with increasing accuracy until the
8//! polygon has four vertices; the result is kept if it is convex and large
9//! enough. The geometry helpers ([`contour_area`], [`is_contour_convex`]) match
10//! OpenCV's `contourArea` and `isContourConvex` exactly for integer contours.
11
12use super::approx::approx_poly_dp;
13use super::contour::Contour;
14
15/// A candidate quadrilateral: four ordered corner pixels `(x, y)`.
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
17pub struct Quad {
18    pub corners: [(i32, i32); 4],
19}
20
21/// Polygon area via the shoelace formula, matching OpenCV `contourArea`
22/// (absolute value, integer-exact for integer input).
23pub fn contour_area(pts: &[(i32, i32)]) -> f64 {
24    let n = pts.len();
25    if n < 3 {
26        return 0.0;
27    }
28    let mut acc = 0i64;
29    let mut prev = pts[n - 1];
30    for &p in pts {
31        acc += prev.0 as i64 * p.1 as i64 - p.0 as i64 * prev.1 as i64;
32        prev = p;
33    }
34    (acc as f64).abs() * 0.5
35}
36
37/// Whether a polygon is convex, matching OpenCV `isContourConvex`.
38///
39/// Like OpenCV, a consecutive collinear triple (cross product exactly zero) is
40/// treated as non-convex: the orientation flag is set to both signs at once,
41/// which forces a `false` result.
42pub fn is_contour_convex(pts: &[(i32, i32)]) -> bool {
43    let n = pts.len();
44    if n < 3 {
45        return false;
46    }
47    let mut prev = pts[n - 2];
48    let mut cur = pts[n - 1];
49    let mut dx0 = (cur.0 - prev.0) as i64;
50    let mut dy0 = (cur.1 - prev.1) as i64;
51    let mut orientation = 0u8;
52
53    for &p in pts {
54        prev = cur;
55        cur = p;
56        let dx = (cur.0 - prev.0) as i64;
57        let dy = (cur.1 - prev.1) as i64;
58        let cross = dx0 * dy - dx * dy0;
59        orientation |= match cross.cmp(&0) {
60            std::cmp::Ordering::Greater => 1,
61            std::cmp::Ordering::Less => 2,
62            std::cmp::Ordering::Equal => 3,
63        };
64        if orientation == 3 {
65            return false;
66        }
67        dx0 = dx;
68        dy0 = dy;
69    }
70    true
71}
72
73/// Extract candidate quads from contours, mirroring OpenCV's per-contour logic
74/// in `generateQuads`: approximate with `approxPolyDP` at accuracy levels 1..=7
75/// until four vertices remain, then keep convex quads with area `>= min_area`.
76pub fn find_quads(contours: &[Contour], min_area: f64) -> Vec<Quad> {
77    let mut quads = Vec::new();
78    for contour in contours {
79        let mut approx = Vec::new();
80        for level in 1..=7 {
81            approx = approx_poly_dp(&contour.points, level as f64, true);
82            if approx.len() == 4 {
83                break;
84            }
85        }
86        if approx.len() != 4 {
87            continue;
88        }
89        if !is_contour_convex(&approx) {
90            continue;
91        }
92        if contour_area(&approx) < min_area {
93            continue;
94        }
95        quads.push(Quad {
96            corners: [approx[0], approx[1], approx[2], approx[3]],
97        });
98    }
99    quads
100}
101
102#[cfg(test)]
103mod tests {
104    use super::super::contour::find_contours;
105    use super::*;
106
107    fn img(rows: &[&str]) -> (Vec<u8>, usize, usize) {
108        let h = rows.len();
109        let w = rows[0].len();
110        let mut data = vec![0u8; w * h];
111        for (r, row) in rows.iter().enumerate() {
112            for (c, ch) in row.chars().enumerate() {
113                data[r * w + c] = if ch == '#' { 255 } else { 0 };
114            }
115        }
116        (data, w, h)
117    }
118
119    #[test]
120    fn area_of_unit_and_large_squares() {
121        // 10x10 axis-aligned square (corners inclusive 0..=10) -> area 100.
122        let sq = [(0, 0), (10, 0), (10, 10), (0, 10)];
123        approx::assert_abs_diff_eq!(contour_area(&sq), 100.0, epsilon = 1e-9);
124        // A triangle with base 4, height 3 -> area 6.
125        let tri = [(0, 0), (4, 0), (0, 3)];
126        approx::assert_abs_diff_eq!(contour_area(&tri), 6.0, epsilon = 1e-9);
127    }
128
129    #[test]
130    fn convexity() {
131        let square = [(0, 0), (10, 0), (10, 10), (0, 10)];
132        assert!(is_contour_convex(&square));
133        // An arrowhead / concave quad.
134        let concave = [(0, 0), (10, 0), (5, 2), (10, 10)];
135        assert!(!is_contour_convex(&concave));
136    }
137
138    #[test]
139    fn finds_two_square_quads() {
140        let (data, w, h) = img(&[
141            "..........",
142            ".###..###.",
143            ".###..###.",
144            ".###..###.",
145            "..........",
146        ]);
147        let contours = find_contours(&data, w, h);
148        let quads = find_quads(&contours, 1.0);
149        assert_eq!(quads.len(), 2, "expected two square quads, got {quads:?}");
150        // Each quad's corners should be the 3x3 block corners.
151        for q in &quads {
152            let set: std::collections::BTreeSet<_> = q.corners.iter().copied().collect();
153            assert_eq!(set.len(), 4, "degenerate quad {q:?}");
154            assert!(is_contour_convex(&q.corners));
155            approx::assert_abs_diff_eq!(contour_area(&q.corners), 4.0, epsilon = 1e-9);
156        }
157    }
158}
checkerboard_calibrate/chessboard/quad.rs

checkerboard_calibrate/chessboard/
quad.rs
