geometry.rs 9.52 KB
Newer Older
Dylan Ede's avatar
Dylan Ede committed
1
2
3
4
use std::ops;

/// A point in 2-dimensional space, with each dimension of type `N`.
///
Jim Blandy's avatar
Jim Blandy committed
5
6
7
8
/// Legal operations on points are addition and subtraction by vectors, and
/// subtraction between points, to give a vector representing the offset between
/// the two points. Combined with the legal operations on vectors, meaningful
/// manipulations of vectors and points can be performed.
Dylan Ede's avatar
Dylan Ede committed
9
10
11
12
13
14
15
16
///
/// For example, to interpolate between two points by a factor `t`:
///
/// ```
/// # use rusttype::*;
/// # let t = 0.5; let p0 = point(0.0, 0.0); let p1 = point(0.0, 0.0);
/// let interpolated_point = p0 + (p1 - p0) * t;
/// ```
17
#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
Dylan Ede's avatar
Dylan Ede committed
18
19
pub struct Point<N> {
    pub x: N,
Jim Blandy's avatar
Jim Blandy committed
20
    pub y: N,
Dylan Ede's avatar
Dylan Ede committed
21
22
23
24
}

/// A vector in 2-dimensional space, with each dimension of type `N`.
///
Jim Blandy's avatar
Jim Blandy committed
25
26
27
/// Legal operations on vectors are addition and subtraction by vectors,
/// addition by points (to give points), and multiplication and division by
/// scalars.
28
#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
Dylan Ede's avatar
Dylan Ede committed
29
30
pub struct Vector<N> {
    pub x: N,
Jim Blandy's avatar
Jim Blandy committed
31
    pub y: N,
Dylan Ede's avatar
Dylan Ede committed
32
33
}
/// A convenience function for generating `Point`s.
34
#[inline]
Dylan Ede's avatar
Dylan Ede committed
35
pub fn point<N>(x: N, y: N) -> Point<N> {
Jim Blandy's avatar
Jim Blandy committed
36
    Point { x, y }
Dylan Ede's avatar
Dylan Ede committed
37
38
}
/// A convenience function for generating `Vector`s.
39
#[inline]
Dylan Ede's avatar
Dylan Ede committed
40
pub fn vector<N>(x: N, y: N) -> Vector<N> {
Jim Blandy's avatar
Jim Blandy committed
41
    Vector { x, y }
Dylan Ede's avatar
Dylan Ede committed
42
43
}

Jim Blandy's avatar
Jim Blandy committed
44
impl<N: ops::Sub<Output = N>> ops::Sub for Point<N> {
Dylan Ede's avatar
Dylan Ede committed
45
46
47
48
49
50
    type Output = Vector<N>;
    fn sub(self, rhs: Point<N>) -> Vector<N> {
        vector(self.x - rhs.x, self.y - rhs.y)
    }
}

Jim Blandy's avatar
Jim Blandy committed
51
impl<N: ops::Add<Output = N>> ops::Add for Vector<N> {
Dylan Ede's avatar
Dylan Ede committed
52
53
54
55
56
57
    type Output = Vector<N>;
    fn add(self, rhs: Vector<N>) -> Vector<N> {
        vector(self.x + rhs.x, self.y + rhs.y)
    }
}

Jim Blandy's avatar
Jim Blandy committed
58
impl<N: ops::Sub<Output = N>> ops::Sub for Vector<N> {
Dylan Ede's avatar
Dylan Ede committed
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
    type Output = Vector<N>;
    fn sub(self, rhs: Vector<N>) -> Vector<N> {
        vector(self.x - rhs.x, self.y - rhs.y)
    }
}

impl ops::Mul<f32> for Vector<f32> {
    type Output = Vector<f32>;
    fn mul(self, rhs: f32) -> Vector<f32> {
        vector(self.x * rhs, self.y * rhs)
    }
}

impl ops::Mul<Vector<f32>> for f32 {
    type Output = Vector<f32>;
    fn mul(self, rhs: Vector<f32>) -> Vector<f32> {
        vector(self * rhs.x, self * rhs.y)
    }
}

impl ops::Mul<f64> for Vector<f64> {
    type Output = Vector<f64>;
    fn mul(self, rhs: f64) -> Vector<f64> {
        vector(self.x * rhs, self.y * rhs)
    }
}

impl ops::Mul<Vector<f64>> for f64 {
    type Output = Vector<f64>;
    fn mul(self, rhs: Vector<f64>) -> Vector<f64> {
        vector(self * rhs.x, self * rhs.y)
    }
}

93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
impl ops::Div<f32> for Vector<f32> {
    type Output = Vector<f32>;
    fn div(self, rhs: f32) -> Vector<f32> {
        vector(self.x / rhs, self.y / rhs)
    }
}

impl ops::Div<Vector<f32>> for f32 {
    type Output = Vector<f32>;
    fn div(self, rhs: Vector<f32>) -> Vector<f32> {
        vector(self / rhs.x, self / rhs.y)
    }
}

impl ops::Div<f64> for Vector<f64> {
    type Output = Vector<f64>;
    fn div(self, rhs: f64) -> Vector<f64> {
        vector(self.x / rhs, self.y / rhs)
    }
}

impl ops::Div<Vector<f64>> for f64 {
    type Output = Vector<f64>;
    fn div(self, rhs: Vector<f64>) -> Vector<f64> {
        vector(self / rhs.x, self / rhs.y)
    }
}

Jim Blandy's avatar
Jim Blandy committed
121
impl<N: ops::Add<Output = N>> ops::Add<Vector<N>> for Point<N> {
Dylan Ede's avatar
Dylan Ede committed
122
123
124
125
126
127
    type Output = Point<N>;
    fn add(self, rhs: Vector<N>) -> Point<N> {
        point(self.x + rhs.x, self.y + rhs.y)
    }
}

Jim Blandy's avatar
Jim Blandy committed
128
impl<N: ops::Sub<Output = N>> ops::Sub<Vector<N>> for Point<N> {
Dylan Ede's avatar
Dylan Ede committed
129
130
131
132
133
134
    type Output = Point<N>;
    fn sub(self, rhs: Vector<N>) -> Point<N> {
        point(self.x - rhs.x, self.y - rhs.y)
    }
}

Jim Blandy's avatar
Jim Blandy committed
135
impl<N: ops::Add<Output = N>> ops::Add<Point<N>> for Vector<N> {
Dylan Ede's avatar
Dylan Ede committed
136
137
138
139
140
141
142
    type Output = Point<N>;
    fn add(self, rhs: Point<N>) -> Point<N> {
        point(self.x + rhs.x, self.y + rhs.y)
    }
}

/// A straight line between two points, `p[0]` and `p[1]`
143
#[derive(Copy, Clone, Debug, PartialEq, PartialOrd)]
Dylan Ede's avatar
Dylan Ede committed
144
pub struct Line {
Jim Blandy's avatar
Jim Blandy committed
145
    pub p: [Point<f32>; 2],
Dylan Ede's avatar
Dylan Ede committed
146
}
Jim Blandy's avatar
Jim Blandy committed
147
148
/// A quadratic Bezier curve, starting at `p[0]`, ending at `p[2]`, with control
/// point `p[1]`.
149
#[derive(Copy, Clone, Debug, PartialEq, PartialOrd)]
Dylan Ede's avatar
Dylan Ede committed
150
pub struct Curve {
Jim Blandy's avatar
Jim Blandy committed
151
    pub p: [Point<f32>; 3],
Dylan Ede's avatar
Dylan Ede committed
152
}
Jim Blandy's avatar
Jim Blandy committed
153
154
/// A rectangle, with top-left corner at `min`, and bottom-right corner at
/// `max`.
155
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
Dylan Ede's avatar
Dylan Ede committed
156
157
pub struct Rect<N> {
    pub min: Point<N>,
Jim Blandy's avatar
Jim Blandy committed
158
    pub max: Point<N>,
Dylan Ede's avatar
Dylan Ede committed
159
}
Jim Blandy's avatar
Jim Blandy committed
160
impl<N: ops::Sub<Output = N> + Copy> Rect<N> {
Dylan Ede's avatar
Dylan Ede committed
161
162
163
164
165
166
167
168
169
170
171
172
173
174
    pub fn width(&self) -> N {
        self.max.x - self.min.x
    }
    pub fn height(&self) -> N {
        self.max.y - self.min.y
    }
}

pub trait BoundingBox<N> {
    fn bounding_box(&self) -> Rect<N> {
        let (min_x, max_x) = self.x_bounds();
        let (min_y, max_y) = self.y_bounds();
        Rect {
            min: point(min_x, min_y),
Jim Blandy's avatar
Jim Blandy committed
175
            max: point(max_x, max_y),
Dylan Ede's avatar
Dylan Ede committed
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
        }
    }
    fn x_bounds(&self) -> (N, N);
    fn y_bounds(&self) -> (N, N);
}

impl BoundingBox<f32> for Line {
    fn x_bounds(&self) -> (f32, f32) {
        let p = &self.p;
        if p[0].x < p[1].x {
            (p[0].x, p[1].x)
        } else {
            (p[1].x, p[0].x)
        }
    }
    fn y_bounds(&self) -> (f32, f32) {
        let p = &self.p;
        if p[0].y < p[1].y {
            (p[0].y, p[1].y)
        } else {
            (p[1].y, p[0].y)
        }
    }
}

impl BoundingBox<f32> for Curve {
    fn x_bounds(&self) -> (f32, f32) {
        let p = &self.p;
        if p[0].x <= p[1].x && p[1].x <= p[2].x {
            (p[0].x, p[2].x)
        } else if p[0].x >= p[1].x && p[1].x >= p[2].x {
            (p[2].x, p[0].x)
        } else {
            let t = (p[0].x - p[1].x) / (p[0].x - 2.0 * p[1].x + p[2].x);
            let _1mt = 1.0 - t;
Jim Blandy's avatar
Jim Blandy committed
211
            let inflection = _1mt * _1mt * p[0].x + 2.0 * _1mt * t * p[1].x + t * t * p[2].x;
Dylan Ede's avatar
Dylan Ede committed
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
            if p[1].x < p[0].x {
                (inflection, p[0].x.max(p[2].x))
            } else {
                (p[0].x.min(p[2].x), inflection)
            }
        }
    }

    fn y_bounds(&self) -> (f32, f32) {
        let p = &self.p;
        if p[0].y <= p[1].y && p[1].y <= p[2].y {
            (p[0].y, p[2].y)
        } else if p[0].y >= p[1].y && p[1].y >= p[2].y {
            (p[2].y, p[0].y)
        } else {
            let t = (p[0].y - p[1].y) / (p[0].y - 2.0 * p[1].y + p[2].y);
            let _1mt = 1.0 - t;
Jim Blandy's avatar
Jim Blandy committed
229
            let inflection = _1mt * _1mt * p[0].y + 2.0 * _1mt * t * p[1].y + t * t * p[2].y;
Dylan Ede's avatar
Dylan Ede committed
230
231
232
233
234
235
236
237
238
239
240
241
242
            if p[1].y < p[0].y {
                (inflection, p[0].y.max(p[2].y))
            } else {
                (p[0].y.min(p[2].y), inflection)
            }
        }
    }
}

pub trait Cut: Sized {
    fn cut_to(self, t: f32) -> Self;
    fn cut_from(self, t: f32) -> Self;
    fn cut_from_to(self, t0: f32, t1: f32) -> Self {
Jim Blandy's avatar
Jim Blandy committed
243
        self.cut_from(t0).cut_to((t1 - t0) / (1.0 - t0))
Dylan Ede's avatar
Dylan Ede committed
244
245
246
247
248
249
250
251
    }
}

impl Cut for Curve {
    fn cut_to(self, t: f32) -> Curve {
        let p = self.p;
        let a = p[0] + t * (p[1] - p[0]);
        let b = p[1] + t * (p[2] - p[1]);
Jim Blandy's avatar
Jim Blandy committed
252
253
        let c = a + t * (b - a);
        Curve { p: [p[0], a, c] }
Dylan Ede's avatar
Dylan Ede committed
254
255
256
257
258
    }
    fn cut_from(self, t: f32) -> Curve {
        let p = self.p;
        let a = p[0] + t * (p[1] - p[0]);
        let b = p[1] + t * (p[2] - p[1]);
Jim Blandy's avatar
Jim Blandy committed
259
260
        let c = a + t * (b - a);
        Curve { p: [c, b, p[2]] }
Dylan Ede's avatar
Dylan Ede committed
261
262
263
264
265
266
267
    }
}

impl Cut for Line {
    fn cut_to(self, t: f32) -> Line {
        let p = self.p;
        Line {
Jim Blandy's avatar
Jim Blandy committed
268
            p: [p[0], p[0] + t * (p[1] - p[0])],
Dylan Ede's avatar
Dylan Ede committed
269
270
271
272
273
        }
    }
    fn cut_from(self, t: f32) -> Line {
        let p = self.p;
        Line {
Jim Blandy's avatar
Jim Blandy committed
274
            p: [p[0] + t * (p[1] - p[0]), p[1]],
Dylan Ede's avatar
Dylan Ede committed
275
276
277
278
279
280
        }
    }
    fn cut_from_to(self, t0: f32, t1: f32) -> Line {
        let p = self.p;
        let v = p[1] - p[0];
        Line {
Jim Blandy's avatar
Jim Blandy committed
281
            p: [p[0] + t0 * v, p[0] + t1 * v],
Dylan Ede's avatar
Dylan Ede committed
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
        }
    }
}

/// The real valued solutions to a real quadratic equation.
#[derive(Copy, Clone, Debug)]
pub enum RealQuadraticSolution {
    /// Two zero-crossing solutions
    Two(f32, f32),
    /// One zero-crossing solution (equation is a straight line)
    One(f32),
    /// One zero-touching solution
    Touch(f32),
    /// No solutions
    None,
    /// All real numbers are solutions since a == b == c == 0.0
Jim Blandy's avatar
Jim Blandy committed
298
    All,
Dylan Ede's avatar
Dylan Ede committed
299
300
301
}

impl RealQuadraticSolution {
Jim Blandy's avatar
Jim Blandy committed
302
303
    /// If there are two solutions, this function ensures that they are in order
    /// (first < second)
Dylan Ede's avatar
Dylan Ede committed
304
305
306
    pub fn in_order(self) -> RealQuadraticSolution {
        use self::RealQuadraticSolution::*;
        match self {
Alex Butler's avatar
Alex Butler committed
307
308
309
310
311
312
313
            Two(x, y) => {
                if x < y {
                    Two(x, y)
                } else {
                    Two(y, x)
                }
            }
Jim Blandy's avatar
Jim Blandy committed
314
            other => other,
Dylan Ede's avatar
Dylan Ede committed
315
316
317
318
319
320
        }
    }
}

/// Solve a real quadratic equation, giving all real solutions, if any.
pub fn solve_quadratic_real(a: f32, b: f32, c: f32) -> RealQuadraticSolution {
Jim Blandy's avatar
Jim Blandy committed
321
    let discriminant = b * b - 4.0 * a * c;
Dylan Ede's avatar
Dylan Ede committed
322
323
    if discriminant > 0.0 {
        let sqrt_d = discriminant.sqrt();
Jim Blandy's avatar
Jim Blandy committed
324
        let common = -b + if b >= 0.0 { -sqrt_d } else { sqrt_d };
Dylan Ede's avatar
Dylan Ede committed
325
326
327
328
329
330
331
332
333
        let x1 = 2.0 * c / common;
        if a == 0.0 {
            RealQuadraticSolution::One(x1)
        } else {
            let x2 = common / (2.0 * a);
            RealQuadraticSolution::Two(x1, x2)
        }
    } else if discriminant < 0.0 {
        RealQuadraticSolution::None
Alex Butler's avatar
Alex Butler committed
334
335
336
337
    } else if b == 0.0 {
        if a == 0.0 {
            if c == 0.0 {
                RealQuadraticSolution::All
Dylan Ede's avatar
Dylan Ede committed
338
            } else {
Alex Butler's avatar
Alex Butler committed
339
                RealQuadraticSolution::None
Dylan Ede's avatar
Dylan Ede committed
340
341
            }
        } else {
Alex Butler's avatar
Alex Butler committed
342
            RealQuadraticSolution::Touch(0.0)
Dylan Ede's avatar
Dylan Ede committed
343
        }
Alex Butler's avatar
Alex Butler committed
344
345
    } else {
        RealQuadraticSolution::Touch(2.0 * c / -b)
Dylan Ede's avatar
Dylan Ede committed
346
347
348
349
350
    }
}

#[test]
fn quadratic_test() {
Alex Butler's avatar
Alex Butler committed
351
    solve_quadratic_real(-0.000_000_1, -2.0, 10.0);
Dylan Ede's avatar
Dylan Ede committed
352
}