src/common/geometry.rs

   1 use std::ops::{Add, AddAssign, Sub, SubAssign, Mul, MulAssign, Div, DivAssign, Neg};
   2
   3 ////////// POINT ///////////////////////////////////////////////////////////////
   4
   5 #[macro_export]
   6 macro_rules! point {
   7     ( $x:expr, $y:expr ) => {
   8         Point { x: $x, y: $y }
   9     };
  10 }
  11
  12 #[derive(Debug, Default, Copy, Clone, PartialEq)]
  13 pub struct Point<T> {
  14     pub x: T,
  15     pub y: T,
  16 }
  17
  18 impl Point<f64> {
  19     pub fn length(&self) -> f64 {
  20         ((self.x * self.x) + (self.y * self.y)).sqrt()
  21     }
  22
  23     pub fn normalized(&self) -> Self {
  24         let l = self.length();
  25         Self {
  26             x: self.x / l,
  27             y: self.y / l,
  28         }
  29     }
  30
  31     pub fn to_radians(&self) -> Radians {
  32         Radians(self.y.atan2(self.x))
  33     }
  34
  35     pub fn to_degrees(&self) -> Degrees {
  36         self.to_radians().to_degrees()
  37     }
  38
  39     pub fn to_i32(self) -> Point<i32> {
  40         Point {
  41             x: self.x as i32,
  42             y: self.y as i32,
  43         }
  44     }
  45 }
  46
  47 macro_rules! point_op {
  48     ($op:tt, $trait:ident($fn:ident), $trait_assign:ident($fn_assign:ident), $rhs:ident = $Rhs:ty => $x:expr, $y:expr) => {
  49         impl<T: $trait<Output = T>> $trait<$Rhs> for Point<T> {
  50             type Output = Self;
  51
  52             fn $fn(self, $rhs: $Rhs) -> Self {
  53                 Self {
  54                     x: self.x $op $x,
  55                     y: self.y $op $y,
  56                 }
  57             }
  58         }
  59
  60         impl<T: $trait<Output = T> + Copy> $trait_assign<$Rhs> for Point<T> {
  61             fn $fn_assign(&mut self, $rhs: $Rhs) {
  62                 *self = Self {
  63                     x: self.x $op $x,
  64                     y: self.y $op $y,
  65                 }
  66             }
  67         }
  68     }
  69 }
  70
  71 point_op!(+, Add(add), AddAssign(add_assign), rhs = Point<T> => rhs.x, rhs.y);
  72 point_op!(-, Sub(sub), SubAssign(sub_assign), rhs = Point<T> => rhs.x, rhs.y);
  73 point_op!(*, Mul(mul), MulAssign(mul_assign), rhs = Point<T> => rhs.x, rhs.y);
  74 point_op!(/, Div(div), DivAssign(div_assign), rhs = Point<T> => rhs.x, rhs.y);
  75 point_op!(+, Add(add), AddAssign(add_assign), rhs = (T, T) => rhs.0, rhs.1);
  76 point_op!(-, Sub(sub), SubAssign(sub_assign), rhs = (T, T) => rhs.0, rhs.1);
  77 point_op!(*, Mul(mul), MulAssign(mul_assign), rhs = (T, T) => rhs.0, rhs.1);
  78 point_op!(/, Div(div), DivAssign(div_assign), rhs = (T, T) => rhs.0, rhs.1);
  79
  80 ////////// multiply point with scalar //////////////////////////////////////////
  81 impl<T: Mul<Output = T> + Copy> Mul<T> for Point<T> {
  82     type Output = Self;
  83
  84     fn mul(self, rhs: T) -> Self {
  85         Self {
  86             x: self.x * rhs,
  87             y: self.y * rhs,
  88         }
  89     }
  90 }
  91
  92 impl<T: Mul<Output = T> + Copy> MulAssign<T> for Point<T> {
  93     fn mul_assign(&mut self, rhs: T) {
  94         *self = Self {
  95             x: self.x * rhs,
  96             y: self.y * rhs,
  97         }
  98     }
  99 }
 100
 101 ////////// divide point with scalar ////////////////////////////////////////////
 102 impl<T: Div<Output = T> + Copy> Div<T> for Point<T> {
 103     type Output = Self;
 104
 105     fn div(self, rhs: T) -> Self {
 106         Self {
 107             x: self.x / rhs,
 108             y: self.y / rhs,
 109         }
 110     }
 111 }
 112
 113 impl<T: Div<Output = T> + Copy> DivAssign<T> for Point<T> {
 114     fn div_assign(&mut self, rhs: T) {
 115         *self = Self {
 116             x: self.x / rhs,
 117             y: self.y / rhs,
 118         }
 119     }
 120 }
 121
 122 impl<T: Neg<Output = T>> Neg for Point<T> {
 123     type Output = Self;
 124
 125     fn neg(self) -> Self {
 126         Self {
 127             x: -self.x,
 128             y: -self.y,
 129         }
 130     }
 131 }
 132
 133 impl<T> From<(T, T)> for Point<T> {
 134     fn from(item: (T, T)) -> Self {
 135         Point {
 136             x: item.0,
 137             y: item.1,
 138         }
 139     }
 140 }
 141
 142 impl<T> From<Point<T>> for (T, T) {
 143     fn from(item: Point<T>) -> Self {
 144         (item.x, item.y)
 145     }
 146 }
 147
 148 impl From<Degrees> for Point<f64> {
 149     fn from(item: Degrees) -> Self {
 150         let r = item.0.to_radians();
 151         Point {
 152             x: r.cos(),
 153             y: r.sin(),
 154         }
 155     }
 156 }
 157
 158 impl From<Radians> for Point<f64> {
 159     fn from(item: Radians) -> Self {
 160         Point {
 161             x: item.0.cos(),
 162             y: item.0.sin(),
 163         }
 164     }
 165 }
 166
 167 #[derive(Debug, Default, PartialEq, Clone, Copy)]
 168 pub struct Degrees(pub f64);
 169 #[derive(Debug, Default, PartialEq, Clone, Copy)]
 170 pub struct Radians(pub f64);
 171
 172 impl Degrees {
 173     #[allow(dead_code)]
 174     fn to_radians(&self) -> Radians {
 175         Radians(self.0.to_radians())
 176     }
 177 }
 178
 179 impl Radians {
 180     #[allow(dead_code)]
 181     fn to_degrees(&self) -> Degrees {
 182         Degrees(self.0.to_degrees())
 183     }
 184 }
 185
 186 ////////// INTERSECTION ////////////////////////////////////////////////////////
 187
 188 #[derive(Debug)]
 189 pub enum Intersection {
 190     Point(Point<f64>),
 191     //Line(Point<f64>, Point<f64>), // TODO: overlapping collinear
 192     None,
 193 }
 194
 195 impl Intersection {
 196     pub fn lines(p1: Point<f64>, p2: Point<f64>, p3: Point<f64>, p4: Point<f64>) -> Intersection {
 197         let s1 = p2 - p1;
 198         let s2 = p4 - p3;
 199
 200         let denomimator = -s2.x * s1.y + s1.x * s2.y;
 201         if denomimator != 0.0 {
 202             let s = (-s1.y * (p1.x - p3.x) + s1.x * (p1.y - p3.y)) / denomimator;
 203             let t = ( s2.x * (p1.y - p3.y) - s2.y * (p1.x - p3.x)) / denomimator;
 204
 205             if s >= 0.0 && s <= 1.0 && t >= 0.0 && t <= 1.0 {
 206                 return Intersection::Point(p1 + (s1 * t))
 207             }
 208         }
 209
 210         Intersection::None
 211     }
 212 }
 213
 214 ////////// DIMENSION ///////////////////////////////////////////////////////////
 215
 216 #[macro_export]
 217 macro_rules! dimen {
 218     ( $w:expr, $h:expr ) => {
 219         Dimension { width: $w, height: $h }
 220     };
 221 }
 222
 223 #[derive(Debug, Default, Copy, Clone, PartialEq)]
 224 pub struct Dimension<T> {
 225     pub width: T,
 226     pub height: T,
 227 }
 228
 229 impl<T: Mul<Output = T> + Copy> Dimension<T> {
 230     #[allow(dead_code)]
 231     pub fn area(&self) -> T {
 232         self.width * self.height
 233     }
 234 }
 235
 236 impl<T> From<(T, T)> for Dimension<T> {
 237     fn from(item: (T, T)) -> Self {
 238         Dimension {
 239             width: item.0,
 240             height: item.1,
 241         }
 242     }
 243 }
 244
 245 impl<T> From<Dimension<T>> for (T, T) {
 246     fn from(item: Dimension<T>) -> Self {
 247         (item.width, item.height)
 248     }
 249 }
 250
 251 ////////////////////////////////////////////////////////////////////////////////
 252
 253 #[allow(dead_code)]
 254 pub fn supercover_line_int(p1: Point<isize>, p2: Point<isize>) -> Vec<Point<isize>> {
 255     let d = p2 - p1;
 256     let n = point!(d.x.abs(), d.y.abs());
 257     let step = point!(
 258         if d.x > 0 { 1 } else { -1 },
 259         if d.y > 0 { 1 } else { -1 }
 260     );
 261
 262     let mut p = p1.clone();
 263     let mut points = vec!(point!(p.x as isize, p.y as isize));
 264     let mut i = point!(0, 0);
 265     while i.x < n.x || i.y < n.y {
 266         let decision = (1 + 2 * i.x) * n.y - (1 + 2 * i.y) * n.x;
 267         if decision == 0 { // next step is diagonal
 268             p.x += step.x;
 269             p.y += step.y;
 270             i.x += 1;
 271             i.y += 1;
 272         } else if decision < 0 { // next step is horizontal
 273             p.x += step.x;
 274             i.x += 1;
 275         } else { // next step is vertical
 276             p.y += step.y;
 277             i.y += 1;
 278         }
 279         points.push(point!(p.x as isize, p.y as isize));
 280     }
 281
 282     points
 283 }
 284
 285 /// Calculates all points a line crosses, unlike Bresenham's line algorithm.
 286 /// There might be room for a lot of improvement here.
 287 pub fn supercover_line(mut p1: Point<f64>, mut p2: Point<f64>) -> Vec<Point<isize>> {
 288     let mut delta = p2 - p1;
 289     if (delta.x.abs() > delta.y.abs() && delta.x.is_sign_negative()) || (delta.x.abs() <= delta.y.abs() && delta.y.is_sign_negative()) {
 290         std::mem::swap(&mut p1, &mut p2);
 291         delta = -delta;
 292     }
 293
 294     let mut last = point!(p1.x as isize, p1.y as isize);
 295     let mut coords: Vec<Point<isize>> = vec!();
 296     coords.push(last);
 297
 298     if delta.x.abs() > delta.y.abs() {
 299         let k = delta.y / delta.x;
 300         let m = p1.y as f64 - p1.x as f64 * k;
 301         for x in (p1.x as isize + 1)..=(p2.x as isize) {
 302             let y = (k * x as f64 + m).floor();
 303             let next = point!(x as isize - 1, y as isize);
 304             if next != last {
 305                 coords.push(next);
 306             }
 307             let next = point!(x as isize, y as isize);
 308             coords.push(next);
 309             last = next;
 310         }
 311     } else {
 312         let k = delta.x / delta.y;
 313         let m = p1.x as f64 - p1.y as f64 * k;
 314         for y in (p1.y as isize + 1)..=(p2.y as isize) {
 315             let x = (k * y as f64 + m).floor();
 316             let next = point!(x as isize, y as isize - 1);
 317             if next != last {
 318                 coords.push(next);
 319             }
 320             let next = point!(x as isize, y as isize);
 321             coords.push(next);
 322             last = next;
 323         }
 324     }
 325
 326     let next = point!(p2.x as isize, p2.y as isize);
 327     if next != last {
 328         coords.push(next);
 329     }
 330
 331     coords
 332 }
 333
 334 ////////// TESTS ///////////////////////////////////////////////////////////////
 335
 336 #[cfg(test)]
 337 mod tests {
 338     use super::*;
 339
 340     #[test]
 341     fn immutable_copy_of_point() {
 342         let a = point!(0, 0);
 343         let mut b = a; // Copy
 344         assert_eq!(a, b); // PartialEq
 345         b.x = 1;
 346         assert_ne!(a, b); // PartialEq
 347     }
 348
 349     #[test]
 350     fn add_points() {
 351         let mut a = point!(1, 0);
 352         assert_eq!(a + point!(2, 2), point!(3, 2)); // Add
 353         a += point!(2, 2); // AddAssign
 354         assert_eq!(a, point!(3, 2));
 355         assert_eq!(point!(1, 0) + (2, 3), point!(3, 3));
 356     }
 357
 358     #[test]
 359     fn sub_points() {
 360         let mut a = point!(1, 0);
 361         assert_eq!(a - point!(2, 2), point!(-1, -2));
 362         a -= point!(2, 2);
 363         assert_eq!(a, point!(-1, -2));
 364         assert_eq!(point!(1, 0) - (2, 3), point!(-1, -3));
 365     }
 366
 367     #[test]
 368     fn mul_points() {
 369         let mut a = point!(1, 2);
 370         assert_eq!(a * 2, point!(2, 4));
 371         assert_eq!(a * point!(2, 3), point!(2, 6));
 372         a *= 2;
 373         assert_eq!(a, point!(2, 4));
 374         a *= point!(3, 1);
 375         assert_eq!(a, point!(6, 4));
 376         assert_eq!(point!(1, 0) * (2, 3), point!(2, 0));
 377     }
 378
 379     #[test]
 380     fn div_points() {
 381         let mut a = point!(4, 8);
 382         assert_eq!(a / 2, point!(2, 4));
 383         assert_eq!(a / point!(2, 4), point!(2, 2));
 384         a /= 2;
 385         assert_eq!(a, point!(2, 4));
 386         a /= point!(2, 4);
 387         assert_eq!(a, point!(1, 1));
 388         assert_eq!(point!(6, 3) / (2, 3), point!(3, 1));
 389     }
 390
 391     #[test]
 392     fn neg_point() {
 393         assert_eq!(point!(1, 1), -point!(-1, -1));
 394     }
 395
 396     #[test]
 397     fn angles() {
 398         assert_eq!(Radians(0.0).to_degrees(), Degrees(0.0));
 399         assert_eq!(Radians(std::f64::consts::PI).to_degrees(), Degrees(180.0));
 400         assert_eq!(Degrees(180.0).to_radians(), Radians(std::f64::consts::PI));
 401         assert!((Point::from(Degrees(90.0)) - point!(0.0, 1.0)).length() < 0.001);
 402         assert!((Point::from(Radians(std::f64::consts::FRAC_PI_2)) - point!(0.0, 1.0)).length() < 0.001);
 403     }
 404
 405     #[test]
 406     fn area_for_dimension_of_multipliable_type() {
 407         let r: Dimension<_> = (30, 20).into(); // the Into trait uses the From trait
 408         assert_eq!(r.area(), 30 * 20);
 409         // let a = Dimension::from(("a".to_string(), "b".to_string())).area(); // this doesn't work, because area() is not implemented for String
 410     }
 411
 412     #[test]
 413     fn intersection_of_lines() {
 414         let p1 = point!(0.0, 0.0);
 415         let p2 = point!(2.0, 2.0);
 416         let p3 = point!(0.0, 2.0);
 417         let p4 = point!(2.0, 0.0);
 418         let r = Intersection::lines(p1, p2, p3, p4);
 419         if let Intersection::Point(p) = r {
 420             assert_eq!(p, point!(1.0, 1.0));
 421         } else {
 422             panic!();
 423         }
 424     }
 425
 426     #[test]
 427     fn some_coordinates_on_line() {
 428         // horizontally up
 429         let coords = supercover_line(point!(0.0, 0.0), point!(3.3, 2.2));
 430         assert_eq!(coords.as_slice(), &[point!(0, 0), point!(1, 0), point!(1, 1), point!(2, 1), point!(2, 2), point!(3, 2)]);
 431
 432         // horizontally down
 433         let coords = supercover_line(point!(0.0, 5.0), point!(3.3, 2.2));
 434         assert_eq!(coords.as_slice(), &[point!(0, 5), point!(0, 4), point!(1, 4), point!(1, 3), point!(2, 3), point!(2, 2), point!(3, 2)]);
 435
 436         // vertically right
 437         let coords = supercover_line(point!(0.0, 0.0), point!(2.2, 3.3));
 438         assert_eq!(coords.as_slice(), &[point!(0, 0), point!(0, 1), point!(1, 1), point!(1, 2), point!(2, 2), point!(2, 3)]);
 439
 440         // vertically left
 441         let coords = supercover_line(point!(5.0, 0.0), point!(3.0, 3.0));
 442         assert_eq!(coords.as_slice(), &[point!(5, 0), point!(4, 0), point!(4, 1), point!(3, 1), point!(3, 2), point!(3, 3)]);
 443
 444         // negative
 445         let coords = supercover_line(point!(0.0, 0.0), point!(-3.0, -2.0));
 446         assert_eq!(coords.as_slice(), &[point!(-3, -2), point!(-2, -2), point!(-2, -1), point!(-1, -1), point!(-1, 0), point!(0, 0)]);
 447
 448         //
 449         let coords = supercover_line(point!(0.0, 0.0), point!(2.3, 1.1));
 450         assert_eq!(coords.as_slice(), &[point!(0, 0), point!(1, 0), point!(2, 0), point!(2, 1)]);
 451     }
 452 }