X-Git-Url: http://git.dolda2000.com/gitweb/?a=blobdiff_plain;f=src%2Fcommon%2Fgeometry.rs;h=5a115fdf63c78049b9cd1b4264bb1ff6a2343799;hb=8012f86b052f550fe6644ec33a2713f381fc4347;hp=02f93b1efa29656561175cd37b61ba1005c8691a;hpb=e570927ad1703298a2c85599c7e25475c60b33d4;p=kaka%2Frust-sdl-test.git diff --git a/src/common/geometry.rs b/src/common/geometry.rs index 02f93b1..5a115fd 100644 --- a/src/common/geometry.rs +++ b/src/common/geometry.rs @@ -1,5 +1,7 @@ use std::ops::{Add, AddAssign, Sub, SubAssign, Mul, MulAssign, Div, DivAssign, Neg}; +////////// POINT /////////////////////////////////////////////////////////////// + #[macro_export] macro_rules! point { ( $x:expr, $y:expr ) => { @@ -181,46 +183,156 @@ impl Radians { } } +////////// 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 s >= 0.0 && s <= 1.0 && t >= 0.0 && t <= 1.0 { + return Intersection::Point(p1 + (s1 * t)) + } + } + + Intersection::None + } +} + +////////// DIMENSION /////////////////////////////////////////////////////////// + #[macro_export] -macro_rules! rect { - ( $x:expr, $y:expr ) => { - Rect { x: $x, y: $y } +macro_rules! dimen { + ( $w:expr, $h:expr ) => { + Dimension { width: $w, height: $h } }; } -#[derive(Default)] -pub struct Rect { +#[derive(Debug, Default, Copy, Clone, PartialEq)] +pub struct Dimension { pub width: T, pub height: T, } -impl + Copy> Rect { +impl + Copy> Dimension { #[allow(dead_code)] pub fn area(&self) -> T { self.width * self.height } } -impl From<(T, T)> for Rect { +impl From<(T, T)> for Dimension { fn from(item: (T, T)) -> Self { - Rect { + Dimension { width: item.0, height: item.1, } } } -#[macro_export] -macro_rules! hashmap { - ($($k:expr => $v:expr),*) => { - { - let mut map = std::collections::HashMap::new(); - $(map.insert($k, $v);)* - map +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.clone(); + 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::*; @@ -291,9 +403,50 @@ mod tests { } #[test] - fn area_for_rect_of_multipliable_type() { - let r: Rect<_> = (30, 20).into(); // the Into trait uses the From trait + 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 = Rect::from(("a".to_string(), "b".to_string())).area(); // this doesn't work, because area() is not implemented for String + // 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)]); } }