lyon_algorithms/
rect.rs

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}
lyon_algorithms/rect.rs

lyon_algorithms/
rect.rs
