1 use core::ops;
2
3 #[cfg(all(feature = "libm-math", not(feature = "std")))]
4 use crate::nostd_float::FloatExt;
5
6 /// A point in 2-dimensional space, with each dimension of type `N`.
7 ///
8 /// Legal operations on points are addition and subtraction by vectors, and
9 /// subtraction between points, to give a vector representing the offset between
10 /// the two points. Combined with the legal operations on vectors, meaningful
11 /// manipulations of vectors and points can be performed.
12 ///
13 /// For example, to interpolate between two points by a factor `t`:
14 ///
15 /// ```
16 /// # use rusttype::*;
17 /// # let t = 0.5; let p0 = point(0.0, 0.0); let p1 = point(0.0, 0.0);
18 /// let interpolated_point = p0 + (p1 - p0) * t;
19 /// ```
20 #[derive(Copy, Clone, Debug, Default, PartialOrd, Ord, PartialEq, Eq, Hash)]
21 pub struct Point<N> {
22 pub x: N,
23 pub y: N,
24 }
25
26 /// A vector in 2-dimensional space, with each dimension of type `N`.
27 ///
28 /// Legal operations on vectors are addition and subtraction by vectors,
29 /// addition by points (to give points), and multiplication and division by
30 /// scalars.
31 #[derive(Copy, Clone, Debug, Default, PartialOrd, Ord, PartialEq, Eq, Hash)]
32 pub struct Vector<N> {
33 pub x: N,
34 pub y: N,
35 }
36
37 /// A convenience function for generating `Point`s.
38 #[inline]
point<N>(x: N, y: N) -> Point<N>39 pub fn point<N>(x: N, y: N) -> Point<N> {
40 Point { x, y }
41 }
42 /// A convenience function for generating `Vector`s.
43 #[inline]
vector<N>(x: N, y: N) -> Vector<N>44 pub fn vector<N>(x: N, y: N) -> Vector<N> {
45 Vector { x, y }
46 }
47
48 impl<N: ops::Sub<Output = N>> ops::Sub for Point<N> {
49 type Output = Vector<N>;
sub(self, rhs: Point<N>) -> Vector<N>50 fn sub(self, rhs: Point<N>) -> Vector<N> {
51 vector(self.x - rhs.x, self.y - rhs.y)
52 }
53 }
54
55 impl<N: ops::Add<Output = N>> ops::Add for Vector<N> {
56 type Output = Vector<N>;
add(self, rhs: Vector<N>) -> Vector<N>57 fn add(self, rhs: Vector<N>) -> Vector<N> {
58 vector(self.x + rhs.x, self.y + rhs.y)
59 }
60 }
61
62 impl<N: ops::Sub<Output = N>> ops::Sub for Vector<N> {
63 type Output = Vector<N>;
sub(self, rhs: Vector<N>) -> Vector<N>64 fn sub(self, rhs: Vector<N>) -> Vector<N> {
65 vector(self.x - rhs.x, self.y - rhs.y)
66 }
67 }
68
69 impl ops::Mul<f32> for Vector<f32> {
70 type Output = Vector<f32>;
mul(self, rhs: f32) -> Vector<f32>71 fn mul(self, rhs: f32) -> Vector<f32> {
72 vector(self.x * rhs, self.y * rhs)
73 }
74 }
75
76 impl ops::Mul<Vector<f32>> for f32 {
77 type Output = Vector<f32>;
mul(self, rhs: Vector<f32>) -> Vector<f32>78 fn mul(self, rhs: Vector<f32>) -> Vector<f32> {
79 vector(self * rhs.x, self * rhs.y)
80 }
81 }
82
83 impl ops::Mul<f64> for Vector<f64> {
84 type Output = Vector<f64>;
mul(self, rhs: f64) -> Vector<f64>85 fn mul(self, rhs: f64) -> Vector<f64> {
86 vector(self.x * rhs, self.y * rhs)
87 }
88 }
89
90 impl ops::Mul<Vector<f64>> for f64 {
91 type Output = Vector<f64>;
mul(self, rhs: Vector<f64>) -> Vector<f64>92 fn mul(self, rhs: Vector<f64>) -> Vector<f64> {
93 vector(self * rhs.x, self * rhs.y)
94 }
95 }
96
97 impl ops::Div<f32> for Vector<f32> {
98 type Output = Vector<f32>;
div(self, rhs: f32) -> Vector<f32>99 fn div(self, rhs: f32) -> Vector<f32> {
100 vector(self.x / rhs, self.y / rhs)
101 }
102 }
103
104 impl ops::Div<Vector<f32>> for f32 {
105 type Output = Vector<f32>;
div(self, rhs: Vector<f32>) -> Vector<f32>106 fn div(self, rhs: Vector<f32>) -> Vector<f32> {
107 vector(self / rhs.x, self / rhs.y)
108 }
109 }
110
111 impl ops::Div<f64> for Vector<f64> {
112 type Output = Vector<f64>;
div(self, rhs: f64) -> Vector<f64>113 fn div(self, rhs: f64) -> Vector<f64> {
114 vector(self.x / rhs, self.y / rhs)
115 }
116 }
117
118 impl ops::Div<Vector<f64>> for f64 {
119 type Output = Vector<f64>;
div(self, rhs: Vector<f64>) -> Vector<f64>120 fn div(self, rhs: Vector<f64>) -> Vector<f64> {
121 vector(self / rhs.x, self / rhs.y)
122 }
123 }
124
125 impl<N: ops::Add<Output = N>> ops::Add<Vector<N>> for Point<N> {
126 type Output = Point<N>;
add(self, rhs: Vector<N>) -> Point<N>127 fn add(self, rhs: Vector<N>) -> Point<N> {
128 point(self.x + rhs.x, self.y + rhs.y)
129 }
130 }
131
132 impl<N: ops::Sub<Output = N>> ops::Sub<Vector<N>> for Point<N> {
133 type Output = Point<N>;
sub(self, rhs: Vector<N>) -> Point<N>134 fn sub(self, rhs: Vector<N>) -> Point<N> {
135 point(self.x - rhs.x, self.y - rhs.y)
136 }
137 }
138
139 impl<N: ops::Add<Output = N>> ops::Add<Point<N>> for Vector<N> {
140 type Output = Point<N>;
add(self, rhs: Point<N>) -> Point<N>141 fn add(self, rhs: Point<N>) -> Point<N> {
142 point(self.x + rhs.x, self.y + rhs.y)
143 }
144 }
145
146 /// A straight line between two points, `p[0]` and `p[1]`
147 #[derive(Copy, Clone, Debug, Default, PartialEq, PartialOrd)]
148 pub struct Line {
149 pub p: [Point<f32>; 2],
150 }
151 /// A quadratic Bezier curve, starting at `p[0]`, ending at `p[2]`, with control
152 /// point `p[1]`.
153 #[derive(Copy, Clone, Debug, Default, PartialEq, PartialOrd)]
154 pub struct Curve {
155 pub p: [Point<f32>; 3],
156 }
157 /// A rectangle, with top-left corner at `min`, and bottom-right corner at
158 /// `max`.
159 #[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Hash, PartialOrd, Ord)]
160 pub struct Rect<N> {
161 pub min: Point<N>,
162 pub max: Point<N>,
163 }
164
165 impl<N: ops::Sub<Output = N> + Copy> Rect<N> {
width(&self) -> N166 pub fn width(&self) -> N {
167 self.max.x - self.min.x
168 }
height(&self) -> N169 pub fn height(&self) -> N {
170 self.max.y - self.min.y
171 }
172 }
173
174 pub trait BoundingBox<N> {
bounding_box(&self) -> Rect<N>175 fn bounding_box(&self) -> Rect<N> {
176 let (min_x, max_x) = self.x_bounds();
177 let (min_y, max_y) = self.y_bounds();
178 Rect {
179 min: point(min_x, min_y),
180 max: point(max_x, max_y),
181 }
182 }
x_bounds(&self) -> (N, N)183 fn x_bounds(&self) -> (N, N);
y_bounds(&self) -> (N, N)184 fn y_bounds(&self) -> (N, N);
185 }
186
187 impl BoundingBox<f32> for Line {
x_bounds(&self) -> (f32, f32)188 fn x_bounds(&self) -> (f32, f32) {
189 let p = &self.p;
190 if p[0].x < p[1].x {
191 (p[0].x, p[1].x)
192 } else {
193 (p[1].x, p[0].x)
194 }
195 }
y_bounds(&self) -> (f32, f32)196 fn y_bounds(&self) -> (f32, f32) {
197 let p = &self.p;
198 if p[0].y < p[1].y {
199 (p[0].y, p[1].y)
200 } else {
201 (p[1].y, p[0].y)
202 }
203 }
204 }
205
206 impl BoundingBox<f32> for Curve {
x_bounds(&self) -> (f32, f32)207 fn x_bounds(&self) -> (f32, f32) {
208 let p = &self.p;
209 if p[0].x <= p[1].x && p[1].x <= p[2].x {
210 (p[0].x, p[2].x)
211 } else if p[0].x >= p[1].x && p[1].x >= p[2].x {
212 (p[2].x, p[0].x)
213 } else {
214 let t = (p[0].x - p[1].x) / (p[0].x - 2.0 * p[1].x + p[2].x);
215 let _1mt = 1.0 - t;
216 let inflection = _1mt * _1mt * p[0].x + 2.0 * _1mt * t * p[1].x + t * t * p[2].x;
217 if p[1].x < p[0].x {
218 (inflection, p[0].x.max(p[2].x))
219 } else {
220 (p[0].x.min(p[2].x), inflection)
221 }
222 }
223 }
224
y_bounds(&self) -> (f32, f32)225 fn y_bounds(&self) -> (f32, f32) {
226 let p = &self.p;
227 if p[0].y <= p[1].y && p[1].y <= p[2].y {
228 (p[0].y, p[2].y)
229 } else if p[0].y >= p[1].y && p[1].y >= p[2].y {
230 (p[2].y, p[0].y)
231 } else {
232 let t = (p[0].y - p[1].y) / (p[0].y - 2.0 * p[1].y + p[2].y);
233 let _1mt = 1.0 - t;
234 let inflection = _1mt * _1mt * p[0].y + 2.0 * _1mt * t * p[1].y + t * t * p[2].y;
235 if p[1].y < p[0].y {
236 (inflection, p[0].y.max(p[2].y))
237 } else {
238 (p[0].y.min(p[2].y), inflection)
239 }
240 }
241 }
242 }
243
244 pub trait Cut: Sized {
cut_to(self, t: f32) -> Self245 fn cut_to(self, t: f32) -> Self;
cut_from(self, t: f32) -> Self246 fn cut_from(self, t: f32) -> Self;
cut_from_to(self, t0: f32, t1: f32) -> Self247 fn cut_from_to(self, t0: f32, t1: f32) -> Self {
248 self.cut_from(t0).cut_to((t1 - t0) / (1.0 - t0))
249 }
250 }
251
252 impl Cut for Curve {
cut_to(self, t: f32) -> Curve253 fn cut_to(self, t: f32) -> Curve {
254 let p = self.p;
255 let a = p[0] + t * (p[1] - p[0]);
256 let b = p[1] + t * (p[2] - p[1]);
257 let c = a + t * (b - a);
258 Curve { p: [p[0], a, c] }
259 }
cut_from(self, t: f32) -> Curve260 fn cut_from(self, t: f32) -> Curve {
261 let p = self.p;
262 let a = p[0] + t * (p[1] - p[0]);
263 let b = p[1] + t * (p[2] - p[1]);
264 let c = a + t * (b - a);
265 Curve { p: [c, b, p[2]] }
266 }
267 }
268
269 impl Cut for Line {
cut_to(self, t: f32) -> Line270 fn cut_to(self, t: f32) -> Line {
271 let p = self.p;
272 Line {
273 p: [p[0], p[0] + t * (p[1] - p[0])],
274 }
275 }
cut_from(self, t: f32) -> Line276 fn cut_from(self, t: f32) -> Line {
277 let p = self.p;
278 Line {
279 p: [p[0] + t * (p[1] - p[0]), p[1]],
280 }
281 }
cut_from_to(self, t0: f32, t1: f32) -> Line282 fn cut_from_to(self, t0: f32, t1: f32) -> Line {
283 let p = self.p;
284 let v = p[1] - p[0];
285 Line {
286 p: [p[0] + t0 * v, p[0] + t1 * v],
287 }
288 }
289 }
290
291 /// The real valued solutions to a real quadratic equation.
292 #[derive(Copy, Clone, Debug)]
293 pub enum RealQuadraticSolution {
294 /// Two zero-crossing solutions
295 Two(f32, f32),
296 /// One zero-crossing solution (equation is a straight line)
297 One(f32),
298 /// One zero-touching solution
299 Touch(f32),
300 /// No solutions
301 None,
302 /// All real numbers are solutions since a == b == c == 0.0
303 All,
304 }
305
306 impl RealQuadraticSolution {
307 /// If there are two solutions, this function ensures that they are in order
308 /// (first < second)
in_order(self) -> RealQuadraticSolution309 pub fn in_order(self) -> RealQuadraticSolution {
310 use self::RealQuadraticSolution::*;
311 match self {
312 Two(x, y) => {
313 if x < y {
314 Two(x, y)
315 } else {
316 Two(y, x)
317 }
318 }
319 other => other,
320 }
321 }
322 }
323
324 /// Solve a real quadratic equation, giving all real solutions, if any.
solve_quadratic_real(a: f32, b: f32, c: f32) -> RealQuadraticSolution325 pub fn solve_quadratic_real(a: f32, b: f32, c: f32) -> RealQuadraticSolution {
326 let discriminant = b * b - 4.0 * a * c;
327 if discriminant > 0.0 {
328 let sqrt_d = discriminant.sqrt();
329 let common = -b + if b >= 0.0 { -sqrt_d } else { sqrt_d };
330 let x1 = 2.0 * c / common;
331 if a == 0.0 {
332 RealQuadraticSolution::One(x1)
333 } else {
334 let x2 = common / (2.0 * a);
335 RealQuadraticSolution::Two(x1, x2)
336 }
337 } else if discriminant < 0.0 {
338 RealQuadraticSolution::None
339 } else if b == 0.0 {
340 if a == 0.0 {
341 if c == 0.0 {
342 RealQuadraticSolution::All
343 } else {
344 RealQuadraticSolution::None
345 }
346 } else {
347 RealQuadraticSolution::Touch(0.0)
348 }
349 } else {
350 RealQuadraticSolution::Touch(2.0 * c / -b)
351 }
352 }
353
354 #[test]
quadratic_test()355 fn quadratic_test() {
356 solve_quadratic_real(-0.000_000_1, -2.0, 10.0);
357 }
358