geometry.rs 9.52 KB
 Dylan Ede committed Feb 05, 2016 1 2 3 4 ``````use std::ops; /// A point in 2-dimensional space, with each dimension of type `N`. /// `````` Jim Blandy committed Mar 19, 2018 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 committed Feb 05, 2016 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; /// ``` `````` Dylan Ede committed Mar 15, 2016 17 ``````#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)] `````` Dylan Ede committed Feb 05, 2016 18 19 ``````pub struct Point { pub x: N, `````` Jim Blandy committed Mar 19, 2018 20 `````` pub y: N, `````` Dylan Ede committed Feb 05, 2016 21 22 23 24 ``````} /// A vector in 2-dimensional space, with each dimension of type `N`. /// `````` Jim Blandy committed Mar 19, 2018 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. `````` Dylan Ede committed Mar 15, 2016 28 ``````#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)] `````` Dylan Ede committed Feb 05, 2016 29 30 ``````pub struct Vector { pub x: N, `````` Jim Blandy committed Mar 19, 2018 31 `````` pub y: N, `````` Dylan Ede committed Feb 05, 2016 32 33 ``````} /// A convenience function for generating `Point`s. `````` Alex Butler committed Mar 21, 2018 34 ``````#[inline] `````` Dylan Ede committed Feb 05, 2016 35 ``````pub fn point(x: N, y: N) -> Point { `````` Jim Blandy committed Mar 19, 2018 36 `````` Point { x, y } `````` Dylan Ede committed Feb 05, 2016 37 38 ``````} /// A convenience function for generating `Vector`s. `````` Alex Butler committed Mar 21, 2018 39 ``````#[inline] `````` Dylan Ede committed Feb 05, 2016 40 ``````pub fn vector(x: N, y: N) -> Vector { `````` Jim Blandy committed Mar 19, 2018 41 `````` Vector { x, y } `````` Dylan Ede committed Feb 05, 2016 42 43 ``````} `````` Jim Blandy committed Mar 19, 2018 44 ``````impl> ops::Sub for Point { `````` Dylan Ede committed Feb 05, 2016 45 46 47 48 49 50 `````` type Output = Vector; fn sub(self, rhs: Point) -> Vector { vector(self.x - rhs.x, self.y - rhs.y) } } `````` Jim Blandy committed Mar 19, 2018 51 ``````impl> ops::Add for Vector { `````` Dylan Ede committed Feb 05, 2016 52 53 54 55 56 57 `````` type Output = Vector; fn add(self, rhs: Vector) -> Vector { vector(self.x + rhs.x, self.y + rhs.y) } } `````` Jim Blandy committed Mar 19, 2018 58 ``````impl> ops::Sub for Vector { `````` Dylan Ede committed Feb 05, 2016 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; fn sub(self, rhs: Vector) -> Vector { vector(self.x - rhs.x, self.y - rhs.y) } } impl ops::Mul for Vector { type Output = Vector; fn mul(self, rhs: f32) -> Vector { vector(self.x * rhs, self.y * rhs) } } impl ops::Mul> for f32 { type Output = Vector; fn mul(self, rhs: Vector) -> Vector { vector(self * rhs.x, self * rhs.y) } } impl ops::Mul for Vector { type Output = Vector; fn mul(self, rhs: f64) -> Vector { vector(self.x * rhs, self.y * rhs) } } impl ops::Mul> for f64 { type Output = Vector; fn mul(self, rhs: Vector) -> Vector { vector(self * rhs.x, self * rhs.y) } } `````` Dylan Ede committed Mar 15, 2016 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 for Vector { type Output = Vector; fn div(self, rhs: f32) -> Vector { vector(self.x / rhs, self.y / rhs) } } impl ops::Div> for f32 { type Output = Vector; fn div(self, rhs: Vector) -> Vector { vector(self / rhs.x, self / rhs.y) } } impl ops::Div for Vector { type Output = Vector; fn div(self, rhs: f64) -> Vector { vector(self.x / rhs, self.y / rhs) } } impl ops::Div> for f64 { type Output = Vector; fn div(self, rhs: Vector) -> Vector { vector(self / rhs.x, self / rhs.y) } } `````` Jim Blandy committed Mar 19, 2018 121 ``````impl> ops::Add> for Point { `````` Dylan Ede committed Feb 05, 2016 122 123 124 125 126 127 `````` type Output = Point; fn add(self, rhs: Vector) -> Point { point(self.x + rhs.x, self.y + rhs.y) } } `````` Jim Blandy committed Mar 19, 2018 128 ``````impl> ops::Sub> for Point { `````` Dylan Ede committed Feb 05, 2016 129 130 131 132 133 134 `````` type Output = Point; fn sub(self, rhs: Vector) -> Point { point(self.x - rhs.x, self.y - rhs.y) } } `````` Jim Blandy committed Mar 19, 2018 135 ``````impl> ops::Add> for Vector { `````` Dylan Ede committed Feb 05, 2016 136 137 138 139 140 141 142 `````` type Output = Point; fn add(self, rhs: Point) -> Point { point(self.x + rhs.x, self.y + rhs.y) } } /// A straight line between two points, `p[0]` and `p[1]` `````` Dylan Ede committed Mar 15, 2016 143 ``````#[derive(Copy, Clone, Debug, PartialEq, PartialOrd)] `````` Dylan Ede committed Feb 05, 2016 144 ``````pub struct Line { `````` Jim Blandy committed Mar 19, 2018 145 `````` pub p: [Point; 2], `````` Dylan Ede committed Feb 05, 2016 146 ``````} `````` Jim Blandy committed Mar 19, 2018 147 148 ``````/// A quadratic Bezier curve, starting at `p[0]`, ending at `p[2]`, with control /// point `p[1]`. `````` Dylan Ede committed Mar 15, 2016 149 ``````#[derive(Copy, Clone, Debug, PartialEq, PartialOrd)] `````` Dylan Ede committed Feb 05, 2016 150 ``````pub struct Curve { `````` Jim Blandy committed Mar 19, 2018 151 `````` pub p: [Point; 3], `````` Dylan Ede committed Feb 05, 2016 152 ``````} `````` Jim Blandy committed Mar 19, 2018 153 154 ``````/// A rectangle, with top-left corner at `min`, and bottom-right corner at /// `max`. `````` Dylan Ede committed Mar 15, 2016 155 ``````#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)] `````` Dylan Ede committed Feb 05, 2016 156 157 ``````pub struct Rect { pub min: Point, `````` Jim Blandy committed Mar 19, 2018 158 `````` pub max: Point, `````` Dylan Ede committed Feb 05, 2016 159 ``````} `````` Jim Blandy committed Mar 19, 2018 160 ``````impl + Copy> Rect { `````` Dylan Ede committed Feb 05, 2016 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 { fn bounding_box(&self) -> Rect { 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 committed Mar 19, 2018 175 `````` max: point(max_x, max_y), `````` Dylan Ede committed Feb 05, 2016 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 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 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 committed Mar 19, 2018 211 `````` let inflection = _1mt * _1mt * p[0].x + 2.0 * _1mt * t * p[1].x + t * t * p[2].x; `````` Dylan Ede committed Feb 05, 2016 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 committed Mar 19, 2018 229 `````` let inflection = _1mt * _1mt * p[0].y + 2.0 * _1mt * t * p[1].y + t * t * p[2].y; `````` Dylan Ede committed Feb 05, 2016 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 committed Mar 19, 2018 243 `````` self.cut_from(t0).cut_to((t1 - t0) / (1.0 - t0)) `````` Dylan Ede committed Feb 05, 2016 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 committed Mar 19, 2018 252 253 `````` let c = a + t * (b - a); Curve { p: [p[0], a, c] } `````` Dylan Ede committed Feb 05, 2016 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 committed Mar 19, 2018 259 260 `````` let c = a + t * (b - a); Curve { p: [c, b, p[2]] } `````` Dylan Ede committed Feb 05, 2016 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 committed Mar 19, 2018 268 `````` p: [p[0], p[0] + t * (p[1] - p[0])], `````` Dylan Ede committed Feb 05, 2016 269 270 271 272 273 `````` } } fn cut_from(self, t: f32) -> Line { let p = self.p; Line { `````` Jim Blandy committed Mar 19, 2018 274 `````` p: [p[0] + t * (p[1] - p[0]), p[1]], `````` Dylan Ede committed Feb 05, 2016 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 committed Mar 19, 2018 281 `````` p: [p[0] + t0 * v, p[0] + t1 * v], `````` Dylan Ede committed Feb 05, 2016 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 committed Mar 19, 2018 298 `````` All, `````` Dylan Ede committed Feb 05, 2016 299 300 301 ``````} impl RealQuadraticSolution { `````` Jim Blandy committed Mar 19, 2018 302 303 `````` /// If there are two solutions, this function ensures that they are in order /// (first < second) `````` Dylan Ede committed Feb 05, 2016 304 305 306 `````` pub fn in_order(self) -> RealQuadraticSolution { use self::RealQuadraticSolution::*; match self { `````` Alex Butler committed Dec 06, 2018 307 308 309 310 311 312 313 `````` Two(x, y) => { if x < y { Two(x, y) } else { Two(y, x) } } `````` Jim Blandy committed Mar 19, 2018 314 `````` other => other, `````` Dylan Ede committed Feb 05, 2016 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 committed Mar 19, 2018 321 `````` let discriminant = b * b - 4.0 * a * c; `````` Dylan Ede committed Feb 05, 2016 322 323 `````` if discriminant > 0.0 { let sqrt_d = discriminant.sqrt(); `````` Jim Blandy committed Mar 19, 2018 324 `````` let common = -b + if b >= 0.0 { -sqrt_d } else { sqrt_d }; `````` Dylan Ede committed Feb 05, 2016 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 committed Mar 19, 2018 334 335 336 337 `````` } else if b == 0.0 { if a == 0.0 { if c == 0.0 { RealQuadraticSolution::All `````` Dylan Ede committed Feb 05, 2016 338 `````` } else { `````` Alex Butler committed Mar 19, 2018 339 `````` RealQuadraticSolution::None `````` Dylan Ede committed Feb 05, 2016 340 341 `````` } } else { `````` Alex Butler committed Mar 19, 2018 342 `````` RealQuadraticSolution::Touch(0.0) `````` Dylan Ede committed Feb 05, 2016 343 `````` } `````` Alex Butler committed Mar 19, 2018 344 345 `````` } else { RealQuadraticSolution::Touch(2.0 * c / -b) `````` Dylan Ede committed Feb 05, 2016 346 347 348 349 350 `````` } } #[test] fn quadratic_test() { `````` Alex Butler committed Mar 19, 2018 351 `````` solve_quadratic_real(-0.000_000_1, -2.0, 10.0); `````` Dylan Ede committed Feb 05, 2016 352 ``}``