blob: e730240cb9a9dd175a79d013a3a73f707cb671a7 [file] [log] [blame]
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);
}