1// Determine whether a path has the shape of an axisa-aligned rectangle.
2
3use crate::math::{point, vector, Box2D, Point, Vector};
4use crate::path::PathEvent;
5
6#[cfg(not(feature = "std"))]
7use num_traits::Float;
8
9#[derive(Copy, Clone, Debug, PartialEq)]
10pub struct ToRectangleOptions {
11 pub tolerance: f32,
12 pub auto_close: bool,
13 /// If true don't consider open sub-paths with no segment.
14 pub ignore_open_empty_sub_paths: bool,
15 /// If true don't consider closed sub-paths with no segment.
16 pub ignore_closed_empty_sub_paths: bool,
17}
18
19impl ToRectangleOptions {
20 /// Default parameters relevant for filling paths.
21 pub fn fill(tolerance: f32) -> Self {
22 ToRectangleOptions {
23 tolerance,
24 auto_close: true,
25 ignore_open_empty_sub_paths: true,
26 ignore_closed_empty_sub_paths: true,
27 }
28 }
29
30 /// Default parameters relevant for stroking paths.
31 ///
32 /// Accepts a subset of the `fill` configuration.
33 pub fn stroke(tolerance: f32) -> Self {
34 ToRectangleOptions {
35 tolerance,
36 auto_close: false,
37 ignore_open_empty_sub_paths: true,
38 ignore_closed_empty_sub_paths: false,
39 }
40 }
41}
42
43/// If the input path represents an axis-aligned rectangle, return it.
44pub fn to_axis_aligned_rectangle<P: IntoIterator<Item = PathEvent>>(
45 path: P,
46 options: &ToRectangleOptions,
47) -> Option<Box2D> {
48 let tolerance = options.tolerance;
49 let mut ctx = ToRectangle {
50 min: point(0.0, 0.0),
51 max: point(0.0, 0.0),
52 current_dir: Dir::None,
53 idx: 0,
54 dirs: [Dir::None; 4],
55 tolerance,
56 };
57
58 for event in path.into_iter() {
59 match event {
60 PathEvent::Begin { at } => {
61 if ctx.idx == 0 {
62 ctx.min = at;
63 ctx.max = at;
64 }
65 }
66 PathEvent::End { first, last, close } => {
67 if ctx.idx == 0 {
68 if !close && options.ignore_open_empty_sub_paths {
69 continue;
70 }
71 if close && options.ignore_closed_empty_sub_paths {
72 continue;
73 }
74 }
75
76 if close || options.auto_close {
77 ctx.edge(last, first)?;
78 }
79
80 ctx.end_sub_path()?;
81 break;
82 }
83 PathEvent::Line { from, to } => {
84 ctx.edge(from, to)?;
85 }
86 PathEvent::Quadratic { from, ctrl, to } => {
87 if ctrl != from {
88 let tol = vector(tolerance, tolerance);
89 let to_axis = (to - from).abs().greater_than(tol);
90 let ctrl_axis = (ctrl - from).abs().greater_than(tol);
91
92 if ctrl_axis != to_axis {
93 return None;
94 }
95
96 if to_axis.x && !is_between(ctrl.x, from.x, to.x) {
97 return None;
98 }
99
100 if to_axis.y && !is_between(ctrl.y, from.y, to.y) {
101 return None;
102 }
103 }
104
105 ctx.edge(from, to);
106 }
107 PathEvent::Cubic {
108 from,
109 ctrl1,
110 ctrl2,
111 to,
112 } => {
113 let tol = vector(tolerance, tolerance);
114 let to_axis = (to - from).abs().greater_than(tol);
115 let mut ctrl1_axis = (ctrl1 - from).abs().greater_than(tol);
116 let mut ctrl2_axis = (ctrl2 - from).abs().greater_than(tol);
117
118 if ctrl1 == from {
119 ctrl1_axis = to_axis;
120 }
121
122 if ctrl2 == from {
123 ctrl2_axis = to_axis;
124 }
125
126 if ctrl1_axis != ctrl2_axis || ctrl1_axis != to_axis {
127 return None;
128 }
129
130 if to_axis.x
131 && !(is_between(ctrl1.x, from.x, to.x) && is_between(ctrl2.x, from.x, to.x))
132 {
133 return None;
134 }
135
136 if to_axis.y
137 && !(is_between(ctrl1.y, from.y, to.y) && is_between(ctrl2.y, from.y, to.y))
138 {
139 return None;
140 }
141
142 ctx.edge(from, to);
143 }
144 }
145 }
146
147 Some(Box2D {
148 min: ctx.min,
149 max: ctx.max,
150 })
151}
152
153struct ToRectangle {
154 min: Point,
155 max: Point,
156 current_dir: Dir,
157 idx: usize,
158 dirs: [Dir; 4],
159 tolerance: f32,
160}
161
162impl ToRectangle {
163 fn edge(&mut self, from: Point, to: Point) -> Option<()> {
164 let edge = to - from;
165 let dir = direction(edge, self.tolerance)?;
166 if dir == Dir::None {
167 return Some(());
168 }
169
170 if dir != self.current_dir {
171 if self.idx >= 4 {
172 return None;
173 }
174
175 if dir == self.current_dir.opposite() {
176 return None;
177 }
178
179 self.dirs[self.idx] = dir;
180 self.idx += 1;
181 self.current_dir = dir;
182 }
183
184 self.min.x = self.min.x.min(to.x);
185 self.min.y = self.min.y.min(to.y);
186 self.max.x = self.max.x.max(to.x);
187 self.max.y = self.max.y.max(to.y);
188
189 Some(())
190 }
191
192 fn end_sub_path(&self) -> Option<()> {
193 if self.idx == 0 {
194 return Some(());
195 }
196
197 if self.idx != 4 {
198 return None;
199 }
200
201 if self.dirs[0].opposite() != self.dirs[2] || self.dirs[1].opposite() != self.dirs[3] {
202 return None;
203 }
204
205 Some(())
206 }
207}
208
209impl Default for ToRectangleOptions {
210 fn default() -> Self {
211 ToRectangleOptions {
212 tolerance: 0.0,
213 auto_close: true,
214 ignore_open_empty_sub_paths: true,
215 ignore_closed_empty_sub_paths: true,
216 }
217 }
218}
219
220fn is_between(x: f32, from: f32, to: f32) -> bool {
221 (from <= x && x <= to) || (to <= x && x <= from)
222}
223
224#[derive(Copy, Clone, Debug, PartialEq, Eq)]
225enum Dir {
226 Left,
227 Right,
228 Up,
229 Down,
230 None,
231}
232
233impl Dir {
234 fn opposite(self) -> Self {
235 match self {
236 Dir::Left => Dir::Right,
237 Dir::Right => Dir::Left,
238 Dir::Up => Dir::Down,
239 Dir::Down => Dir::Up,
240 Dir::None => Dir::None,
241 }
242 }
243}
244
245fn direction(v: Vector, tolerance: f32) -> Option<Dir> {
246 if !v.is_finite() {
247 return None;
248 }
249
250 let x = v.x.abs() > tolerance;
251 let y = v.y.abs() > tolerance;
252
253 if x && y {
254 return None;
255 }
256
257 if !x && !y {
258 return Some(Dir::None);
259 }
260
261 let dir = if x {
262 if v.x > 0.0 {
263 Dir::Right
264 } else {
265 Dir::Left
266 }
267 } else if v.y > 0.0 {
268 Dir::Down
269 } else {
270 Dir::Up
271 };
272
273 Some(dir)
274}
275
276#[test]
277fn test_to_axis_aligned_rectangle() {
278 use crate::geom::euclid::approxeq::ApproxEq;
279 fn approx_eq(a: Box2D, b: Box2D) -> bool {
280 a.min.approx_eq(&b.min) && a.max.approx_eq(&b.max)
281 }
282
283 let fill = ToRectangleOptions::fill(0.00001);
284 let stroke = ToRectangleOptions::stroke(0.00001);
285
286 let mut builder = crate::path::Path::builder();
287 builder.begin(point(0.0, 0.0));
288 builder.line_to(point(10.0, 0.0));
289 builder.line_to(point(10.0, 5.0));
290 builder.line_to(point(0.0, 5.0));
291 builder.end(true);
292 let path = builder.build();
293
294 let r = to_axis_aligned_rectangle(&path, &fill).unwrap();
295 assert!(approx_eq(
296 r,
297 Box2D {
298 min: point(0.0, 0.0),
299 max: point(10.0, 5.0)
300 }
301 ));
302
303 let mut builder = crate::path::Path::builder();
304 builder.begin(point(0.0, 0.0));
305 builder.line_to(point(0.0, 5.0));
306 builder.line_to(point(10.0, 5.0));
307 builder.line_to(point(10.0, 0.0));
308 builder.end(false);
309 let path = builder.build();
310
311 let r = to_axis_aligned_rectangle(&path, &fill).unwrap();
312 assert!(approx_eq(
313 r,
314 Box2D {
315 min: point(0.0, 0.0),
316 max: point(10.0, 5.0)
317 }
318 ));
319 assert!(to_axis_aligned_rectangle(&path, &stroke).is_none());
320
321 let mut builder = crate::path::Path::builder();
322 builder.begin(point(0.0, 0.0));
323 builder.line_to(point(0.0, 2.0));
324 builder.line_to(point(0.0, 5.0));
325 builder.line_to(point(1.0, 5.0));
326 builder.line_to(point(9.0, 5.0));
327 builder.line_to(point(10.0, 5.0));
328 builder.line_to(point(10.0, 0.0));
329 builder.line_to(point(0.0, 0.0));
330 builder.end(true);
331 let path = builder.build();
332
333 let r = to_axis_aligned_rectangle(&path, &fill).unwrap();
334 assert!(approx_eq(
335 r,
336 Box2D {
337 min: point(0.0, 0.0),
338 max: point(10.0, 5.0)
339 }
340 ));
341
342 let mut builder = crate::path::Path::builder();
343 builder.begin(point(0.0, 0.0));
344 builder.line_to(point(0.0, 5.0));
345 builder.line_to(point(10.0, 5.0));
346 builder.end(false);
347 let path = builder.build();
348
349 assert!(to_axis_aligned_rectangle(&path, &fill).is_none());
350
351 let mut builder = crate::path::Path::builder();
352 builder.begin(point(0.0, 0.0));
353 builder.line_to(point(0.0, 5.0));
354 builder.end(false);
355 let path = builder.build();
356
357 assert!(to_axis_aligned_rectangle(&path, &fill).is_none());
358
359 let mut builder = crate::path::Path::builder();
360 builder.begin(point(0.0, 0.0));
361 builder.line_to(point(0.0, 5.0));
362 builder.line_to(point(10.0, 5.0));
363 builder.line_to(point(10.0, 1.0));
364 builder.end(false);
365 let path = builder.build();
366
367 assert!(to_axis_aligned_rectangle(&path, &fill).is_none());
368
369 let mut builder = crate::path::Path::builder();
370 builder.begin(point(0.0, 0.0));
371 builder.line_to(point(0.0, 5.0));
372 builder.line_to(point(5.0, 5.0));
373 builder.line_to(point(10.0, 5.0));
374 builder.line_to(point(10.0, 10.0));
375 builder.line_to(point(0.0, 10.0));
376 builder.end(false);
377 let path = builder.build();
378
379 assert!(to_axis_aligned_rectangle(&path, &fill).is_none());
380
381 let mut builder = crate::path::Path::builder();
382 builder.begin(point(0.0, 0.0));
383 builder.quadratic_bezier_to(point(5.0, 0.0), point(10.0, 0.0));
384 builder.line_to(point(10.0, 5.0));
385 builder.line_to(point(0.0, 5.0));
386 builder.end(true);
387 let path = builder.build();
388
389 let r = to_axis_aligned_rectangle(&path, &fill).unwrap();
390 assert!(approx_eq(
391 r,
392 Box2D {
393 min: point(0.0, 0.0),
394 max: point(10.0, 5.0)
395 }
396 ));
397
398 let mut builder = crate::path::Path::builder();
399 builder.begin(point(0.0, 0.0));
400 builder.quadratic_bezier_to(point(11.0, 0.0), point(10.0, 0.0));
401 builder.line_to(point(10.0, 5.0));
402 builder.line_to(point(0.0, 5.0));
403 builder.end(true);
404 let path = builder.build();
405
406 assert!(to_axis_aligned_rectangle(&path, &fill).is_none());
407
408 let mut builder = crate::path::Path::builder();
409 builder.begin(point(-1.0, 0.0));
410 builder.end(true);
411
412 builder.begin(point(0.0, -1.0));
413 builder.end(false);
414
415 builder.begin(point(0.0, 0.0));
416 builder.line_to(point(10.0, 0.0));
417 builder.line_to(point(10.0, 5.0));
418 builder.line_to(point(0.0, 5.0));
419 builder.end(true);
420
421 builder.begin(point(-1.0, -1.0));
422 builder.end(false);
423
424 builder.begin(point(-1.0, -1.0));
425 builder.end(true);
426
427 let path = builder.build();
428
429 let r = to_axis_aligned_rectangle(&path, &fill).unwrap();
430 assert!(approx_eq(
431 r,
432 Box2D {
433 min: point(0.0, 0.0),
434 max: point(10.0, 5.0)
435 }
436 ));
437
438 let mut builder = crate::path::Path::builder();
439 builder.begin(point(0.0, 0.0));
440 builder.line_to(point(10.0, 0.0));
441 builder.line_to(point(10.0, 5.0));
442 builder.line_to(point(1.0, 5.0));
443 builder.end(false);
444 let path = builder.build();
445
446 assert!(to_axis_aligned_rectangle(&path, &stroke).is_none());
447}
448