X-Git-Url: http://git.dolda2000.com/gitweb/?a=blobdiff_plain;f=src%2Fcommon%2Fgeometry.rs;h=5a115fdf63c78049b9cd1b4264bb1ff6a2343799;hb=8012f86b052f550fe6644ec33a2713f381fc4347;hp=5a03ffb79da30bf2b36007fe0c920bf88989bd18;hpb=1f42d724d84ed1c014ff40ccc91058472391be0c;p=kaka%2Frust-sdl-test.git diff --git a/src/common/geometry.rs b/src/common/geometry.rs index 5a03ffb..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,6 +183,36 @@ 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! dimen { ( $w:expr, $h:expr ) => { @@ -188,7 +220,7 @@ macro_rules! dimen { }; } -#[derive(Debug, Default)] +#[derive(Debug, Default, Copy, Clone, PartialEq)] pub struct Dimension { pub width: T, pub height: T, @@ -210,17 +242,97 @@ impl From<(T, T)> for Dimension { } } -#[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::*; @@ -296,4 +408,45 @@ mod tests { 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)]); + } }