bracket_geometry/
lines.rs

1use crate::prelude::{Bresenham, DistanceAlg, Point};
2
3/// Enumeration of available 2D Distance algorithms
4pub enum LineAlg {
5    /// Use Bresenham's rasterization algorithm for line definition
6    Bresenham,
7    /// Use a vector approach to line solving.
8    Vector,
9}
10
11/// Plots a line between two 2D points and returns a vector of points along the line.
12pub fn line2d(algorithm: LineAlg, start: Point, end: Point) -> Vec<Point> {
13    match algorithm {
14        LineAlg::Bresenham => line2d_bresenham(start, end),
15        LineAlg::Vector => line2d_vector(start, end),
16    }
17}
18
19/// Uses a Bresenham's algorithm to plot a line between two points. On some CPUs, this is faster
20/// than Bresenham.
21pub fn line2d_bresenham(start: Point, end: Point) -> Vec<Point> {
22    let line = Bresenham::new(start, end);
23    line.chain(std::iter::once(end)).collect()
24}
25
26/// Uses a 2D vector algorithm to plot a line between two points. On some CPUs, this is faster
27/// than Bresenham.
28pub fn line2d_vector(start: Point, end: Point) -> Vec<Point> {
29    use ultraviolet::Vec2;
30
31    if start == end {
32        return vec![start];
33    }
34
35    let mut pos = Vec2::new(start.x as f32, start.y as f32);
36    let dest = Vec2::new(end.x as f32, end.y as f32);
37    let n_steps = DistanceAlg::Pythagoras.distance2d(start, end);
38    let slope = (dest - pos).normalized();
39    let mut result: Vec<Point> = Vec::with_capacity(n_steps as usize + 1);
40    let mut count = 0;
41    result.push(start);
42    loop {
43        pos += slope;
44        let new_point = Point::new(pos.x.round() as i32, pos.y.round() as i32);
45        if result[result.len() - 1] != new_point {
46            if count == n_steps as i32 {
47                result.push(end);
48                break;
49            }
50            result.push(new_point);
51            if new_point == end {
52                // arrived
53                break;
54            }
55        }
56        count += 1;
57    }
58
59    result
60}
61
62#[cfg(test)]
63mod tests {
64    use crate::prelude::{line2d_bresenham, line2d_vector, Point};
65
66    #[test]
67    fn vector_line_h() {
68        let pt = Point::new(0, 0);
69        let pt2 = Point::new(5, 0);
70        let line = line2d_vector(pt, pt2);
71        assert_eq!(
72            line,
73            vec![
74                Point::new(0, 0),
75                Point::new(1, 0),
76                Point::new(2, 0),
77                Point::new(3, 0),
78                Point::new(4, 0),
79                Point::new(5, 0)
80            ]
81        );
82    }
83
84    #[test]
85    fn vector_line_v() {
86        let pt = Point::new(0, 0);
87        let pt2 = Point::new(0, 5);
88        let line = line2d_vector(pt, pt2);
89        assert_eq!(
90            line,
91            vec![
92                Point::new(0, 0),
93                Point::new(0, 1),
94                Point::new(0, 2),
95                Point::new(0, 3),
96                Point::new(0, 4),
97                Point::new(0, 5)
98            ]
99        );
100    }
101
102    #[test]
103    fn vector_line_v_neg() {
104        let pt = Point::new(0, 0);
105        let pt2 = Point::new(0, -5);
106        let line = line2d_vector(pt, pt2);
107        assert_eq!(
108            line,
109            vec![
110                Point::new(0, 0),
111                Point::new(0, -1),
112                Point::new(0, -2),
113                Point::new(0, -3),
114                Point::new(0, -4),
115                Point::new(0, -5)
116            ]
117        );
118    }
119
120    #[test]
121    fn bresenham_line_h() {
122        let pt = Point::new(0, 0);
123        let pt2 = Point::new(5, 0);
124        let line = line2d_bresenham(pt, pt2);
125        assert_eq!(
126            line,
127            vec![
128                Point::new(0, 0),
129                Point::new(1, 0),
130                Point::new(2, 0),
131                Point::new(3, 0),
132                Point::new(4, 0),
133                Point::new(5, 0)
134            ]
135        );
136    }
137
138    #[test]
139    fn bresenham_line_v() {
140        let pt = Point::new(0, 0);
141        let pt2 = Point::new(0, 5);
142        let line = line2d_bresenham(pt, pt2);
143        assert_eq!(
144            line,
145            vec![
146                Point::new(0, 0),
147                Point::new(0, 1),
148                Point::new(0, 2),
149                Point::new(0, 3),
150                Point::new(0, 4),
151                Point::new(0, 5)
152            ]
153        );
154    }
155
156    #[test]
157    fn bresenham_line_v_neg() {
158        let pt = Point::new(0, 0);
159        let pt2 = Point::new(0, -5);
160        let line = line2d_bresenham(pt, pt2);
161        assert_eq!(
162            line,
163            vec![
164                Point::new(0, 0),
165                Point::new(0, -1),
166                Point::new(0, -2),
167                Point::new(0, -3),
168                Point::new(0, -4),
169                Point::new(0, -5)
170            ]
171        );
172    }
173
174    #[test]
175    pub fn infinite_loop_bug181() {
176        let pt = Point { x: 2, y: 2 };
177        let pt2 = Point { x: 7, y: -4 };
178        let line = line2d_vector(pt, pt2);
179
180        assert_eq!(line[line.len() - 1], pt2);
181    }
182}
bracket_geometry/lines.rs

bracket_geometry/
lines.rs
