X-Git-Url: http://dolda2000.com/gitweb/?a=blobdiff_plain;f=src%2Fgeometry.rs;fp=src%2Fgeometry.rs;h=540db53bff9568f488024837ac44857636c5eb34;hb=953b4c960649b82f4e186c2a9afee5367270f0fc;hp=0000000000000000000000000000000000000000;hpb=0c56b1f7a5568d6bfbebd196cf63ccef503cf959;p=kaka%2Frust-sdl-test.git diff --git a/src/geometry.rs b/src/geometry.rs new file mode 100644 index 0000000..540db53 --- /dev/null +++ b/src/geometry.rs @@ -0,0 +1,529 @@ +use std::ops::{Add, AddAssign, Sub, SubAssign, Mul, MulAssign, Div, DivAssign, Neg}; + +////////// POINT /////////////////////////////////////////////////////////////// + +#[macro_export] +macro_rules! point { + ( $x:expr, $y:expr ) => { + Point { x: $x, y: $y } + }; +} + +#[derive(Debug, Default, Copy, Clone, PartialEq)] +pub struct Point { + pub x: T, + pub y: T, +} + +impl Point { + pub fn length(&self) -> f64 { + ((self.x * self.x) + (self.y * self.y)).sqrt() + } + + pub fn normalized(&self) -> Self { + let l = self.length(); + Self { + x: self.x / l, + y: self.y / l, + } + } + + pub fn to_angle(&self) -> Angle { + self.y.atan2(self.x).radians() + } + + pub fn to_i32(self) -> Point { + Point { + x: self.x as i32, + y: self.y as i32, + } + } +} + +macro_rules! impl_point_op { + ($op:tt, $trait:ident($fn:ident), $trait_assign:ident($fn_assign:ident), $rhs:ident = $Rhs:ty => $x:expr, $y:expr) => { + impl> $trait<$Rhs> for Point { + type Output = Self; + + fn $fn(self, $rhs: $Rhs) -> Self { + Self { + x: self.x $op $x, + y: self.y $op $y, + } + } + } + + impl + Copy> $trait_assign<$Rhs> for Point { + fn $fn_assign(&mut self, $rhs: $Rhs) { + *self = Self { + x: self.x $op $x, + y: self.y $op $y, + } + } + } + } +} + +impl_point_op!(+, Add(add), AddAssign(add_assign), rhs = Point => rhs.x, rhs.y); +impl_point_op!(-, Sub(sub), SubAssign(sub_assign), rhs = Point => rhs.x, rhs.y); +impl_point_op!(*, Mul(mul), MulAssign(mul_assign), rhs = Point => rhs.x, rhs.y); +impl_point_op!(/, Div(div), DivAssign(div_assign), rhs = Point => rhs.x, rhs.y); +impl_point_op!(+, Add(add), AddAssign(add_assign), rhs = (T, T) => rhs.0, rhs.1); +impl_point_op!(-, Sub(sub), SubAssign(sub_assign), rhs = (T, T) => rhs.0, rhs.1); +impl_point_op!(*, Mul(mul), MulAssign(mul_assign), rhs = (T, T) => rhs.0, rhs.1); +impl_point_op!(/, Div(div), DivAssign(div_assign), rhs = (T, T) => rhs.0, rhs.1); +impl_point_op!(*, Mul(mul), MulAssign(mul_assign), rhs = Dimension => rhs.width, rhs.height); +impl_point_op!(/, Div(div), DivAssign(div_assign), rhs = Dimension => rhs.width, rhs.height); + +////////// multiply point with scalar ////////////////////////////////////////// +impl + Copy> Mul for Point { + type Output = Self; + + fn mul(self, rhs: T) -> Self { + Self { + x: self.x * rhs, + y: self.y * rhs, + } + } +} + +impl + Copy> MulAssign for Point { + fn mul_assign(&mut self, rhs: T) { + *self = Self { + x: self.x * rhs, + y: self.y * rhs, + } + } +} + +////////// divide point with scalar //////////////////////////////////////////// +impl + Copy> Div for Point { + type Output = Self; + + fn div(self, rhs: T) -> Self { + Self { + x: self.x / rhs, + y: self.y / rhs, + } + } +} + +impl + Copy> DivAssign for Point { + fn div_assign(&mut self, rhs: T) { + *self = Self { + x: self.x / rhs, + y: self.y / rhs, + } + } +} + +impl> Neg for Point { + type Output = Self; + + fn neg(self) -> Self { + Self { + x: -self.x, + y: -self.y, + } + } +} + +impl From<(T, T)> for Point { + fn from(item: (T, T)) -> Self { + Point { + x: item.0, + y: item.1, + } + } +} + +impl From> for (T, T) { + fn from(item: Point) -> Self { + (item.x, item.y) + } +} + +impl From for Point { + fn from(item: Angle) -> Self { + Point { + x: item.0.cos(), + y: item.0.sin(), + } + } +} + +////////// ANGLE /////////////////////////////////////////////////////////////// + +#[derive(Debug, Default, Clone, Copy)] +pub struct Angle(pub f64); + +pub trait ToAngle { + fn radians(self) -> Angle; + fn degrees(self) -> Angle; +} + +macro_rules! impl_angle { + ($($type:ty),*) => { + $( + impl ToAngle for $type { + fn radians(self) -> Angle { + Angle(self as f64) + } + + fn degrees(self) -> Angle { + Angle((self as f64).to_radians()) + } + } + + impl Mul<$type> for Angle { + type Output = Self; + + fn mul(self, rhs: $type) -> Self { + Angle(self.0 * (rhs as f64)) + } + } + + impl MulAssign<$type> for Angle { + fn mul_assign(&mut self, rhs: $type) { + self.0 *= rhs as f64; + } + } + + impl Div<$type> for Angle { + type Output = Self; + + fn div(self, rhs: $type) -> Self { + Angle(self.0 / (rhs as f64)) + } + } + + impl DivAssign<$type> for Angle { + fn div_assign(&mut self, rhs: $type) { + self.0 /= rhs as f64; + } + } + )* + } +} + +impl_angle!(f32, f64, i8, i16, i32, i64, isize, u8, u16, u32, u64, usize); + +impl Angle { + pub fn to_radians(self) -> f64 { + self.0 + } + + pub fn to_degrees(self) -> f64 { + self.0.to_degrees() + } + + /// Returns the reflection of the incident when mirrored along this angle. + pub fn mirror(&self, incidence: Angle) -> Angle { + Angle((std::f64::consts::PI + self.0 * 2.0 - incidence.0) % std::f64::consts::TAU) + } +} + +impl PartialEq for Angle { + fn eq(&self, rhs: &Angle) -> bool { + self.0 % std::f64::consts::TAU == rhs.0 % std::f64::consts::TAU + } +} + +// addition and subtraction of angles + +impl Add for Angle { + type Output = Self; + + fn add(self, rhs: Angle) -> Self { + Angle(self.0 + rhs.0) + } +} + +impl AddAssign for Angle { + fn add_assign(&mut self, rhs: Angle) { + self.0 += rhs.0; + } +} + +impl Sub for Angle { + type Output = Self; + + fn sub(self, rhs: Angle) -> Self { + Angle(self.0 - rhs.0) + } +} + +impl SubAssign for Angle { + fn sub_assign(&mut self, rhs: Angle) { + self.0 -= rhs.0; + } +} + +////////// INTERSECTION //////////////////////////////////////////////////////// + +#[derive(Debug)] +pub enum Intersection { + Point(Point), + //Line(Point, Point), // TODO: overlapping collinear + None, +} + +impl Intersection { + pub fn lines(p1: Point, p2: Point, p3: Point, p4: Point) -> Intersection { + let s1 = p2 - p1; + let s2 = p4 - p3; + + let denomimator = -s2.x * s1.y + s1.x * s2.y; + if denomimator != 0.0 { + let s = (-s1.y * (p1.x - p3.x) + s1.x * (p1.y - p3.y)) / denomimator; + let t = ( s2.x * (p1.y - p3.y) - s2.y * (p1.x - p3.x)) / denomimator; + + if (0.0..=1.0).contains(&s) && (0.0..=1.0).contains(&t) { + return Intersection::Point(p1 + (s1 * t)) + } + } + + Intersection::None + } +} + +////////// DIMENSION /////////////////////////////////////////////////////////// + +#[macro_export] +macro_rules! dimen { + ( $w:expr, $h:expr ) => { + Dimension { width: $w, height: $h } + }; +} + +#[derive(Debug, Default, Copy, Clone, PartialEq)] +pub struct Dimension { + pub width: T, + pub height: T, +} + +impl + Copy> Dimension { + #[allow(dead_code)] + pub fn area(&self) -> T { + self.width * self.height + } +} + +impl From<(T, T)> for Dimension { + fn from(item: (T, T)) -> Self { + Dimension { + width: item.0, + height: item.1, + } + } +} + +impl From> for (T, T) { + fn from(item: Dimension) -> Self { + (item.width, item.height) + } +} + +//////////////////////////////////////////////////////////////////////////////// + +#[allow(dead_code)] +pub fn supercover_line_int(p1: Point, p2: Point) -> Vec> { + let d = p2 - p1; + let n = point!(d.x.abs(), d.y.abs()); + let step = point!( + if d.x > 0 { 1 } else { -1 }, + if d.y > 0 { 1 } else { -1 } + ); + + let mut p = p1; + let mut points = vec!(point!(p.x as isize, p.y as isize)); + let mut i = point!(0, 0); + while i.x < n.x || i.y < n.y { + let decision = (1 + 2 * i.x) * n.y - (1 + 2 * i.y) * n.x; + if decision == 0 { // next step is diagonal + p.x += step.x; + p.y += step.y; + i.x += 1; + i.y += 1; + } else if decision < 0 { // next step is horizontal + p.x += step.x; + i.x += 1; + } else { // next step is vertical + p.y += step.y; + i.y += 1; + } + points.push(point!(p.x as isize, p.y as isize)); + } + + points +} + +/// Calculates all points a line crosses, unlike Bresenham's line algorithm. +/// There might be room for a lot of improvement here. +pub fn supercover_line(mut p1: Point, mut p2: Point) -> Vec> { + let mut delta = p2 - p1; + if (delta.x.abs() > delta.y.abs() && delta.x.is_sign_negative()) || (delta.x.abs() <= delta.y.abs() && delta.y.is_sign_negative()) { + std::mem::swap(&mut p1, &mut p2); + delta = -delta; + } + + let mut last = point!(p1.x as isize, p1.y as isize); + let mut coords: Vec> = vec!(); + coords.push(last); + + if delta.x.abs() > delta.y.abs() { + let k = delta.y / delta.x; + let m = p1.y as f64 - p1.x as f64 * k; + for x in (p1.x as isize + 1)..=(p2.x as isize) { + let y = (k * x as f64 + m).floor(); + let next = point!(x as isize - 1, y as isize); + if next != last { + coords.push(next); + } + let next = point!(x as isize, y as isize); + coords.push(next); + last = next; + } + } else { + let k = delta.x / delta.y; + let m = p1.x as f64 - p1.y as f64 * k; + for y in (p1.y as isize + 1)..=(p2.y as isize) { + let x = (k * y as f64 + m).floor(); + let next = point!(x as isize, y as isize - 1); + if next != last { + coords.push(next); + } + let next = point!(x as isize, y as isize); + coords.push(next); + last = next; + } + } + + let next = point!(p2.x as isize, p2.y as isize); + if next != last { + coords.push(next); + } + + coords +} + +////////// TESTS /////////////////////////////////////////////////////////////// + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn immutable_copy_of_point() { + let a = point!(0, 0); + let mut b = a; // Copy + assert_eq!(a, b); // PartialEq + b.x = 1; + assert_ne!(a, b); // PartialEq + } + + #[test] + fn add_points() { + let mut a = point!(1, 0); + assert_eq!(a + point!(2, 2), point!(3, 2)); // Add + a += point!(2, 2); // AddAssign + assert_eq!(a, point!(3, 2)); + assert_eq!(point!(1, 0) + (2, 3), point!(3, 3)); + } + + #[test] + fn sub_points() { + let mut a = point!(1, 0); + assert_eq!(a - point!(2, 2), point!(-1, -2)); + a -= point!(2, 2); + assert_eq!(a, point!(-1, -2)); + assert_eq!(point!(1, 0) - (2, 3), point!(-1, -3)); + } + + #[test] + fn mul_points() { + let mut a = point!(1, 2); + assert_eq!(a * 2, point!(2, 4)); + assert_eq!(a * point!(2, 3), point!(2, 6)); + a *= 2; + assert_eq!(a, point!(2, 4)); + a *= point!(3, 1); + assert_eq!(a, point!(6, 4)); + assert_eq!(point!(1, 0) * (2, 3), point!(2, 0)); + } + + #[test] + fn div_points() { + let mut a = point!(4, 8); + assert_eq!(a / 2, point!(2, 4)); + assert_eq!(a / point!(2, 4), point!(2, 2)); + a /= 2; + assert_eq!(a, point!(2, 4)); + a /= point!(2, 4); + assert_eq!(a, point!(1, 1)); + assert_eq!(point!(6, 3) / (2, 3), point!(3, 1)); + } + + #[test] + fn neg_point() { + assert_eq!(point!(1, 1), -point!(-1, -1)); + } + + #[test] + fn angles() { + assert_eq!(0.radians(), 0.degrees()); + assert_eq!(0.degrees(), 360.degrees()); + assert_eq!(180.degrees(), std::f64::consts::PI.radians()); + assert_eq!(std::f64::consts::PI.radians().to_degrees(), 180.0); + assert!((Point::from(90.degrees()) - point!(0.0, 1.0)).length() < 0.001); + assert!((Point::from(std::f64::consts::FRAC_PI_2.radians()) - point!(0.0, 1.0)).length() < 0.001); + } + + #[test] + fn area_for_dimension_of_multipliable_type() { + let r: Dimension<_> = (30, 20).into(); // the Into trait uses the From trait + assert_eq!(r.area(), 30 * 20); + // let a = Dimension::from(("a".to_string(), "b".to_string())).area(); // this doesn't work, because area() is not implemented for String + } + + #[test] + fn intersection_of_lines() { + let p1 = point!(0.0, 0.0); + let p2 = point!(2.0, 2.0); + let p3 = point!(0.0, 2.0); + let p4 = point!(2.0, 0.0); + let r = Intersection::lines(p1, p2, p3, p4); + if let Intersection::Point(p) = r { + assert_eq!(p, point!(1.0, 1.0)); + } else { + panic!(); + } + } + + #[test] + fn some_coordinates_on_line() { + // horizontally up + let coords = supercover_line(point!(0.0, 0.0), point!(3.3, 2.2)); + assert_eq!(coords.as_slice(), &[point!(0, 0), point!(1, 0), point!(1, 1), point!(2, 1), point!(2, 2), point!(3, 2)]); + + // horizontally down + let coords = supercover_line(point!(0.0, 5.0), point!(3.3, 2.2)); + 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)]); + + // vertically right + let coords = supercover_line(point!(0.0, 0.0), point!(2.2, 3.3)); + assert_eq!(coords.as_slice(), &[point!(0, 0), point!(0, 1), point!(1, 1), point!(1, 2), point!(2, 2), point!(2, 3)]); + + // vertically left + let coords = supercover_line(point!(5.0, 0.0), point!(3.0, 3.0)); + assert_eq!(coords.as_slice(), &[point!(5, 0), point!(4, 0), point!(4, 1), point!(3, 1), point!(3, 2), point!(3, 3)]); + + // negative + let coords = supercover_line(point!(0.0, 0.0), point!(-3.0, -2.0)); + assert_eq!(coords.as_slice(), &[point!(-3, -2), point!(-2, -2), point!(-2, -1), point!(-1, -1), point!(-1, 0), point!(0, 0)]); + + // + let coords = supercover_line(point!(0.0, 0.0), point!(2.3, 1.1)); + assert_eq!(coords.as_slice(), &[point!(0, 0), point!(1, 0), point!(2, 0), point!(2, 1)]); + } +}