geometry.rs

use std::ops;

/// A point in 2-dimensional space, with each dimension of type `N`.
///
/// 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.
///
/// 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;
/// ```
#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
pub struct Point<N> {
    pub x: N,
    pub y: N,
}

/// A vector in 2-dimensional space, with each dimension of type `N`.
///
/// Legal operations on vectors are addition and subtraction by vectors,
/// addition by points (to give points), and multiplication and division by
/// scalars.
#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
pub struct Vector<N> {
    pub x: N,
    pub y: N,
}
/// A convenience function for generating `Point`s.
#[inline]
pub fn point<N>(x: N, y: N) -> Point<N> {
    Point { x, y }
}
/// A convenience function for generating `Vector`s.
#[inline]
pub fn vector<N>(x: N, y: N) -> Vector<N> {
    Vector { x, y }
}

impl<N: ops::Sub<Output = N>> ops::Sub for Point<N> {
    type Output = Vector<N>;
    fn sub(self, rhs: Point<N>) -> Vector<N> {
        vector(self.x - rhs.x, self.y - rhs.y)
    }
}

impl<N: ops::Add<Output = N>> ops::Add for Vector<N> {
    type Output = Vector<N>;
    fn add(self, rhs: Vector<N>) -> Vector<N> {
        vector(self.x + rhs.x, self.y + rhs.y)
    }
}

impl<N: ops::Sub<Output = N>> ops::Sub for Vector<N> {
    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)
    }
}

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)
    }
}

impl<N: ops::Add<Output = N>> ops::Add<Vector<N>> for Point<N> {
    type Output = Point<N>;
    fn add(self, rhs: Vector<N>) -> Point<N> {
        point(self.x + rhs.x, self.y + rhs.y)
    }
}

impl<N: ops::Sub<Output = N>> ops::Sub<Vector<N>> for Point<N> {
    type Output = Point<N>;
    fn sub(self, rhs: Vector<N>) -> Point<N> {
        point(self.x - rhs.x, self.y - rhs.y)
    }
}

impl<N: ops::Add<Output = N>> ops::Add<Point<N>> for Vector<N> {
    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]`
#[derive(Copy, Clone, Debug, PartialEq, PartialOrd)]
pub struct Line {
    pub p: [Point<f32>; 2],
}
/// A quadratic Bezier curve, starting at `p[0]`, ending at `p[2]`, with control
/// point `p[1]`.
#[derive(Copy, Clone, Debug, PartialEq, PartialOrd)]
pub struct Curve {
    pub p: [Point<f32>; 3],
}
/// A rectangle, with top-left corner at `min`, and bottom-right corner at
/// `max`.
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Rect<N> {
    pub min: Point<N>,
    pub max: Point<N>,
}
impl<N: ops::Sub<Output = N> + Copy> Rect<N> {
    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),
            max: point(max_x, max_y),
        }
    }
    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;
            let inflection = _1mt * _1mt * p[0].x + 2.0 * _1mt * t * p[1].x + t * t * p[2].x;
            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;
            let inflection = _1mt * _1mt * p[0].y + 2.0 * _1mt * t * p[1].y + t * t * p[2].y;
            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 {
        self.cut_from(t0).cut_to((t1 - t0) / (1.0 - t0))
    }
}

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]);
        let c = a + t * (b - a);
        Curve { p: [p[0], a, c] }
    }
    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]);
        let c = a + t * (b - a);
        Curve { p: [c, b, p[2]] }
    }
}

impl Cut for Line {
    fn cut_to(self, t: f32) -> Line {
        let p = self.p;
        Line {
            p: [p[0], p[0] + t * (p[1] - p[0])],
        }
    }
    fn cut_from(self, t: f32) -> Line {
        let p = self.p;
        Line {
            p: [p[0] + t * (p[1] - p[0]), p[1]],
        }
    }
    fn cut_from_to(self, t0: f32, t1: f32) -> Line {
        let p = self.p;
        let v = p[1] - p[0];
        Line {
            p: [p[0] + t0 * v, p[0] + t1 * v],
        }
    }
}

/// 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
    All,
}

impl RealQuadraticSolution {
    /// If there are two solutions, this function ensures that they are in order
    /// (first < second)
    pub fn in_order(self) -> RealQuadraticSolution {
        use self::RealQuadraticSolution::*;
        match self {
            Two(x, y) => if x < y {
                Two(x, y)
            } else {
                Two(y, x)
            },
            other => other,
        }
    }
}

/// Solve a real quadratic equation, giving all real solutions, if any.
pub fn solve_quadratic_real(a: f32, b: f32, c: f32) -> RealQuadraticSolution {
    let discriminant = b * b - 4.0 * a * c;
    if discriminant > 0.0 {
        let sqrt_d = discriminant.sqrt();
        let common = -b + if b >= 0.0 { -sqrt_d } else { sqrt_d };
        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
    } else if b == 0.0 {
        if a == 0.0 {
            if c == 0.0 {
                RealQuadraticSolution::All
            } else {
                RealQuadraticSolution::None
            }
        } else {
            RealQuadraticSolution::Touch(0.0)
        }
    } else {
        RealQuadraticSolution::Touch(2.0 * c / -b)
    }
}

#[test]
fn quadratic_test() {
    solve_quadratic_real(-0.000_000_1, -2.0, 10.0);
}