1#[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#[derive(Debug, Clone, Copy, PartialEq)]
38pub(crate) enum Ink {
39 Seg { x0: f64, y0: f64, x1: f64, y1: f64 },
41 Rect { l: f64, b: f64, r: f64, t: f64 },
43 Blot { l: f64, b: f64, r: f64, t: f64 },
46 Bitmap { l: f64, b: f64, r: f64, t: f64 },
49}
50
51pub(crate) const MIN_SIDE: f64 = 5.0;
54pub(crate) const MAX_SIDE: f64 = 24.0;
55const 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 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
78type 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
86pub(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 let near = |a: f64, b: f64| (a - b).abs() <= TOL;
100 let mut hs: Vec<(usize, f64, f64, f64)> = Vec::new(); let mut vs: Vec<(usize, f64, f64, f64)> = Vec::new(); 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 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 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 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 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 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 let mut open = four_edges(50.0, 50.0);
242 open.pop();
243 assert!(find(&open, 800.0).is_empty());
244 }
245
246 #[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}