lyon_algorithms/
aabb.rs

1//! Bounding rectangle computation for paths.
2
3use crate::geom::{CubicBezierSegment, QuadraticBezierSegment};
4use crate::math::{point, Box2D, Point};
5use crate::path::PathEvent;
6
7/// Computes a conservative axis-aligned rectangle that contains the path.
8///
9/// This bounding rectangle approximation is faster but less precise than
10/// [`bounding_box`](fn.bounding_box.html).
11pub fn fast_bounding_box<Iter, Evt>(path: Iter) -> Box2D
12where
13    Iter: IntoIterator<Item = Evt>,
14    Evt: FastBoundingBox,
15{
16    let mut min = point(f32::MAX, f32::MAX);
17    let mut max = point(f32::MIN, f32::MIN);
18    for e in path {
19        e.min_max(&mut min, &mut max);
20    }
21
22    // Return an empty rectangle by default if there was no event in the path.
23    if min == point(f32::MAX, f32::MAX) {
24        return Box2D::zero();
25    }
26
27    Box2D { min, max }
28}
29
30#[doc(hidden)]
31pub trait FastBoundingBox {
32    fn min_max(&self, min: &mut Point, max: &mut Point);
33}
34
35impl FastBoundingBox for PathEvent {
36    fn min_max(&self, min: &mut Point, max: &mut Point) {
37        match self {
38            PathEvent::Begin { at } => {
39                *min = Point::min(*min, *at);
40                *max = Point::max(*max, *at);
41            }
42            PathEvent::Line { to, .. } => {
43                *min = Point::min(*min, *to);
44                *max = Point::max(*max, *to);
45            }
46            PathEvent::Quadratic { ctrl, to, .. } => {
47                *min = Point::min(*min, Point::min(*ctrl, *to));
48                *max = Point::max(*max, Point::max(*ctrl, *to));
49            }
50            PathEvent::Cubic {
51                ctrl1, ctrl2, to, ..
52            } => {
53                *min = Point::min(*min, Point::min(*ctrl1, Point::min(*ctrl2, *to)));
54                *max = Point::max(*max, Point::max(*ctrl1, Point::max(*ctrl2, *to)));
55            }
56            PathEvent::End { .. } => {}
57        }
58    }
59}
60
61/// Computes the smallest axis-aligned rectangle that contains the path.
62pub fn bounding_box<Iter, Evt>(path: Iter) -> Box2D
63where
64    Iter: IntoIterator<Item = Evt>,
65    Evt: TightBoundingBox,
66{
67    let mut min = point(f32::MAX, f32::MAX);
68    let mut max = point(f32::MIN, f32::MIN);
69
70    for evt in path {
71        evt.min_max(&mut min, &mut max);
72    }
73
74    // Return an empty rectangle by default if there was no event in the path.
75    if min == point(f32::MAX, f32::MAX) {
76        return Box2D::zero();
77    }
78
79    Box2D { min, max }
80}
81
82#[doc(hidden)]
83pub trait TightBoundingBox {
84    fn min_max(&self, min: &mut Point, max: &mut Point);
85}
86
87impl TightBoundingBox for PathEvent {
88    fn min_max(&self, min: &mut Point, max: &mut Point) {
89        match self {
90            PathEvent::Begin { at } => {
91                *min = Point::min(*min, *at);
92                *max = Point::max(*max, *at);
93            }
94            PathEvent::Line { to, .. } => {
95                *min = Point::min(*min, *to);
96                *max = Point::max(*max, *to);
97            }
98            PathEvent::Quadratic { from, ctrl, to } => {
99                let r = QuadraticBezierSegment {
100                    from: *from,
101                    ctrl: *ctrl,
102                    to: *to,
103                }
104                .bounding_box();
105                *min = Point::min(*min, r.min);
106                *max = Point::max(*max, r.max);
107            }
108            PathEvent::Cubic {
109                from,
110                ctrl1,
111                ctrl2,
112                to,
113            } => {
114                let r = CubicBezierSegment {
115                    from: *from,
116                    ctrl1: *ctrl1,
117                    ctrl2: *ctrl2,
118                    to: *to,
119                }
120                .bounding_box();
121                *min = Point::min(*min, r.min);
122                *max = Point::max(*max, r.max);
123            }
124            PathEvent::End { .. } => {}
125        }
126    }
127}
128
129#[test]
130fn simple_bounding_box() {
131    use crate::path::Path;
132
133    let mut builder = Path::builder();
134    builder.begin(point(-10.0, -3.0));
135    builder.line_to(point(0.0, -12.0));
136    builder.quadratic_bezier_to(point(3.0, 4.0), point(5.0, 3.0));
137    builder.end(true);
138    let path = builder.build();
139
140    assert_eq!(
141        fast_bounding_box(&path),
142        Box2D {
143            min: point(-10.0, -12.0),
144            max: point(5.0, 4.0)
145        },
146    );
147
148    let mut builder = Path::builder();
149    builder.begin(point(0.0, 0.0));
150    builder.cubic_bezier_to(point(-1.0, 2.0), point(3.0, -4.0), point(1.0, -1.0));
151    builder.end(false);
152    let path = builder.build();
153
154    assert_eq!(
155        fast_bounding_box(path.iter()),
156        Box2D {
157            min: point(-1.0, -4.0),
158            max: point(3.0, 2.0)
159        },
160    );
161}
lyon_algorithms/aabb.rs

lyon_algorithms/
aabb.rs
