Skip to main content

docling_pdf/
checkbox.rs

1//! Vector checkboxes (#609): the small squares a generator *draws* in front of
2//! a checklist's lines, found in the page's path painting.
3//!
4//! docling knows a checkbox only from the layout model's `checkbox_selected` /
5//! `checkbox_unselected` labels, and Heron gives them to drawn squares
6//! sparingly — on the #609 reporter's ReportLab checklist it labels the four
7//! options one `text` region, which docling then serializes as two garbled
8//! paragraphs (`First option Third option` / `Second option Fourth option`,
9//! its cell assignment alternating between two overlapping text clusters).
10//! The squares themselves are unambiguous in the content stream, so the text
11//! parser records the strokes it walks past ([`Ink`]) and [`find`] turns them
12//! into [`CheckBox`]es; assembly then gives each boxed line its own checkbox
13//! item ([`crate::assemble::split_checkbox_lines`]).
14//!
15//! A square is an outline — a stroked `re`, or four stroked axis-aligned
16//! edges meeting at the corners (ReportLab draws each edge as its own
17//! `m … l S` path) — between [`MIN_SIDE`] and [`MAX_SIDE`] points with sides
18//! within 15 % of each other. Anything else painted inside it (a tick, a
19//! cross, a filled dot) marks it checked. A square filled with colour — a
20//! stroked-and-filled `re`, or one under a fill of its own size — is a chart
21//! legend's swatch, not a checkbox; a white fill (a form's box background)
22//! draws nothing and changes nothing.
23
24/// A checkbox square, top-left page points (the [`TextCell`] frame).
25///
26/// [`TextCell`]: crate::pdfium_backend::TextCell
27#[derive(Debug, Clone, Copy, PartialEq)]
28pub struct CheckBox {
29    pub l: f32,
30    pub t: f32,
31    pub r: f32,
32    pub b: f32,
33    pub checked: bool,
34}
35
36/// One painted piece of a path, y-up page points (the glyphs' frame).
37#[derive(Debug, Clone, Copy, PartialEq)]
38pub(crate) enum Ink {
39    /// A stroked straight segment.
40    Seg { x0: f64, y0: f64, x1: f64, y1: f64 },
41    /// A stroked (or stroked-and-filled) rectangle, axis-aligned on the page.
42    Rect { l: f64, b: f64, r: f64, t: f64 },
43    /// Anything else painted — a fill, a curve: its bounding box, which can
44    /// only ever be a mark inside a square.
45    Blot { l: f64, b: f64, r: f64, t: f64 },
46    /// An image placement (#999): the text parser hands these on as the
47    /// page's bitmaps and drops them before [`find`] sees the inks.
48    Bitmap { l: f64, b: f64, r: f64, t: f64 },
49}
50
51/// Smallest and largest checkbox side, points: below 5 pt a square is a
52/// bullet or a table hairline's corner, above 24 pt a frame or a swatch.
53pub(crate) const MIN_SIDE: f64 = 5.0;
54pub(crate) const MAX_SIDE: f64 = 24.0;
55/// Corner/edge matching slack, points (line caps, rounding).
56const TOL: f64 = 0.75;
57
58impl Ink {
59    fn bbox(&self) -> (f64, f64, f64, f64) {
60        match *self {
61            Ink::Seg { x0, y0, x1, y1 } => (x0.min(x1), y0.min(y1), x0.max(x1), y0.max(y1)),
62            Ink::Rect { l, b, r, t } | Ink::Blot { l, b, r, t } | Ink::Bitmap { l, b, r, t } => {
63                (l, b, r, t)
64            }
65        }
66    }
67
68    /// Whether the text parser should keep this piece at all: only what can
69    /// be a checkbox edge or fit inside one. Keeps a vector-heavy page (a
70    /// chart, a map) from buffering every path it draws.
71    pub(crate) fn worth_keeping(&self) -> bool {
72        let (l, b, r, t) = self.bbox();
73        let reach = MAX_SIDE + TOL;
74        (r - l) <= reach && (t - b) <= reach
75    }
76}
77
78/// A square's `(l, b, r, t)` and the ink indices that draw it.
79type Square = ((f64, f64, f64, f64), Vec<usize>);
80
81fn square_sides(w: f64, h: f64) -> bool {
82    let (lo, hi) = (w.min(h), w.max(h));
83    lo >= MIN_SIDE && hi <= MAX_SIDE && hi - lo <= 0.15 * hi
84}
85
86/// The checkboxes among a page's painted pieces, top-left page points
87/// (`page_h` flips y). Duplicates (a square stroked twice) collapse.
88pub(crate) fn find(inks: &[Ink], page_h: f32) -> Vec<CheckBox> {
89    let mut squares: Vec<Square> = Vec::new();
90    for (i, ink) in inks.iter().enumerate() {
91        if let Ink::Rect { l, b, r, t } = *ink {
92            if square_sides(r - l, t - b) {
93                squares.push(((l, b, r, t), vec![i]));
94            }
95        }
96    }
97    // Four separate edges. Horizontal edges pair up by a shared x span, and
98    // the two verticals must close the sides at both ends.
99    let near = |a: f64, b: f64| (a - b).abs() <= TOL;
100    let mut hs: Vec<(usize, f64, f64, f64)> = Vec::new(); // (ink, y, xl, xr)
101    let mut vs: Vec<(usize, f64, f64, f64)> = Vec::new(); // (ink, x, yb, yt)
102    for (i, ink) in inks.iter().enumerate() {
103        if let Ink::Seg { x0, y0, x1, y1 } = *ink {
104            if near(y0, y1) && (x1 - x0).abs() >= MIN_SIDE - TOL {
105                hs.push((i, (y0 + y1) / 2.0, x0.min(x1), x0.max(x1)));
106            } else if near(x0, x1) && (y1 - y0).abs() >= MIN_SIDE - TOL {
107                vs.push((i, (x0 + x1) / 2.0, y0.min(y1), y0.max(y1)));
108            }
109        }
110    }
111    // A page drawn from thousands of short strokes (hatching, a plotted
112    // curve) is not a checklist; the pairing below is quadratic.
113    if hs.len() <= 4000 && vs.len() <= 4000 {
114        let side = |lo: f64, hi: f64, a: f64, b: f64| near(lo, a) && near(hi, b);
115        for (x, &(hi, ya, xl, xr)) in hs.iter().enumerate() {
116            for &(hj, yb, xl2, xr2) in &hs[x + 1..] {
117                if !(near(xl, xl2) && near(xr, xr2) && square_sides(xr - xl, (ya - yb).abs())) {
118                    continue;
119                }
120                let (bot, top) = (ya.min(yb), ya.max(yb));
121                let left = vs
122                    .iter()
123                    .find(|&&(_, vx, y0, y1)| near(vx, xl) && side(y0, y1, bot, top));
124                let right = vs
125                    .iter()
126                    .find(|&&(_, vx, y0, y1)| near(vx, xr) && side(y0, y1, bot, top));
127                if let (Some(&(lv, ..)), Some(&(rv, ..))) = (left, right) {
128                    squares.push(((xl, bot, xr, top), vec![hi, hj, lv, rv]));
129                }
130            }
131        }
132    }
133    let mut out: Vec<CheckBox> = Vec::new();
134    for (k, &((l, b, r, t), ref own)) in squares.iter().enumerate() {
135        let same =
136            |o: &Square| near(o.0 .0, l) && near(o.0 .1, b) && near(o.0 .2, r) && near(o.0 .3, t);
137        if squares[..k].iter().any(same) {
138            continue;
139        }
140        // The square's own edges (and any re-stroke of them) are not a mark;
141        // a mark is other ink lying within the square, centred well inside.
142        let edges: Vec<usize> = squares
143            .iter()
144            .filter(|o| same(o))
145            .flat_map(|o| o.1.iter().copied())
146            .chain(own.iter().copied())
147            .collect();
148        // A square under a coloured fill of its own size is a chart legend's
149        // swatch (matplotlib strokes and fills each patch), not a checkbox.
150        let swatch = inks.iter().any(|ink| {
151            matches!(ink, Ink::Blot { .. }) && {
152                let (il, ib, ir, it) = ink.bbox();
153                let fit = 1.5;
154                (il - l).abs() <= fit
155                    && (ir - r).abs() <= fit
156                    && (ib - b).abs() <= fit
157                    && (it - t).abs() <= fit
158            }
159        });
160        if swatch {
161            continue;
162        }
163        let inset = 0.2 * (r - l);
164        let checked = inks.iter().enumerate().any(|(i, ink)| {
165            if edges.contains(&i) {
166                return false;
167            }
168            let (il, ib, ir, it) = ink.bbox();
169            let (cx, cy) = ((il + ir) / 2.0, (ib + it) / 2.0);
170            il >= l - TOL
171                && ir <= r + TOL
172                && ib >= b - TOL
173                && it <= t + TOL
174                && cx > l + inset
175                && cx < r - inset
176                && cy > b + inset
177                && cy < t - inset
178        });
179        out.push(CheckBox {
180            l: l as f32,
181            t: page_h - t as f32,
182            r: r as f32,
183            b: page_h - b as f32,
184            checked,
185        });
186    }
187    out
188}
189
190#[cfg(test)]
191mod tests {
192    use super::*;
193
194    fn seg(x0: f64, y0: f64, x1: f64, y1: f64) -> Ink {
195        Ink::Seg { x0, y0, x1, y1 }
196    }
197
198    /// ReportLab's checkbox: four `m … l S` edges of a 12.96 pt square.
199    fn four_edges(x: f64, y: f64) -> Vec<Ink> {
200        let s = 12.96;
201        vec![
202            seg(x, y + s, x + s, y + s),
203            seg(x, y, x + s, y),
204            seg(x, y, x, y + s),
205            seg(x + s, y, x + s, y + s),
206        ]
207    }
208
209    #[test]
210    fn four_stroked_edges_make_one_square() {
211        let boxes = find(&four_edges(119.52, 449.04), 792.0);
212        assert_eq!(boxes.len(), 1);
213        let b = boxes[0];
214        assert!((b.l - 119.52).abs() < 0.01 && (b.r - 132.48).abs() < 0.01);
215        assert!((b.t - (792.0 - 462.0)).abs() < 0.01, "{b:?}");
216        assert!(!b.checked);
217    }
218
219    #[test]
220    fn a_stroked_rect_is_a_square_and_a_tick_inside_checks_it() {
221        let mut inks = vec![Ink::Rect {
222            l: 100.0,
223            b: 100.0,
224            r: 110.0,
225            t: 110.0,
226        }];
227        assert!(!find(&inks, 800.0)[0].checked);
228        inks.push(seg(102.0, 105.0, 104.5, 102.0));
229        inks.push(seg(104.5, 102.0, 108.5, 108.5));
230        assert!(find(&inks, 800.0)[0].checked);
231    }
232
233    #[test]
234    fn frames_bullets_and_open_shapes_are_not_checkboxes() {
235        let rect = |l, b, r, t| Ink::Rect { l, b, r, t };
236        // Too big (a frame), too small (a bullet), not square (a bar).
237        assert!(find(&[rect(0.0, 0.0, 40.0, 40.0)], 800.0).is_empty());
238        assert!(find(&[rect(0.0, 0.0, 3.0, 3.0)], 800.0).is_empty());
239        assert!(find(&[rect(0.0, 0.0, 20.0, 8.0)], 800.0).is_empty());
240        // Three edges only.
241        let mut open = four_edges(50.0, 50.0);
242        open.pop();
243        assert!(find(&open, 800.0).is_empty());
244    }
245
246    /// A legend swatch — the square filled with colour by a separate fill of
247    /// its size — is not a checkbox.
248    #[test]
249    fn a_colour_filled_square_is_a_swatch() {
250        let mut inks = four_edges(10.0, 10.0);
251        inks.push(Ink::Blot {
252            l: 10.0,
253            b: 10.0,
254            r: 22.96,
255            t: 22.96,
256        });
257        assert!(find(&inks, 800.0).is_empty());
258    }
259
260    #[test]
261    fn a_square_stroked_twice_is_one_unchecked_box() {
262        let mut inks = four_edges(10.0, 10.0);
263        inks.extend(four_edges(10.0, 10.0));
264        let boxes = find(&inks, 800.0);
265        assert_eq!(boxes.len(), 1);
266        assert!(!boxes[0].checked);
267    }
268}