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
}