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: Point2D = point(x:f32::MAX, y:f32::MAX);
17 let mut max: Point2D = point(x:f32::MIN, y:f32::MIN);
18 for e: Evt 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(x:f32::MAX, y: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: Point2D = point(x:f32::MAX, y:f32::MAX);
68 let mut max: Point2D = point(x:f32::MIN, y:f32::MIN);
69
70 for evt: 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(x:f32::MAX, y: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}
162