bracket_geometry/
line_bresenham.rs

1//! Original at: <https://github.com/mbr/bresenham-rs/blob/master/src/lib.rs>
2//! Modified to use more BTerm-friendly types
3//!
4use crate::prelude::Point;
5use core::iter::Iterator;
6
7/// Line-drawing iterator
8pub struct Bresenham {
9    x: i32,
10    y: i32,
11    dx: i32,
12    dy: i32,
13    x1: i32,
14    diff: i32,
15    octant: Octant,
16}
17
18struct Octant(u8);
19
20impl Octant {
21    /// adapted from <http://codereview.stackexchange.com/a/95551>
22    #[inline]
23    fn from_points(start: Point, end: Point) -> Octant {
24        let mut dx = end.x - start.x;
25        let mut dy = end.y - start.y;
26
27        let mut octant = 0;
28
29        if dy < 0 {
30            dx = -dx;
31            dy = -dy;
32            octant += 4;
33        }
34
35        if dx < 0 {
36            let tmp = dx;
37            dx = dy;
38            dy = -tmp;
39            octant += 2;
40        }
41
42        if dx < dy {
43            octant += 1;
44        }
45
46        Octant(octant)
47    }
48
49    #[inline]
50    fn to_octant0(&self, p: Point) -> Point {
51        match self.0 {
52            0 => Point::new(p.x, p.y),
53            1 => Point::new(p.y, p.x),
54            2 => Point::new(p.y, -p.x),
55            3 => Point::new(-p.x, p.y),
56            4 => Point::new(-p.x, -p.y),
57            5 => Point::new(-p.y, -p.x),
58            6 => Point::new(-p.y, p.x),
59            7 => Point::new(p.x, -p.y),
60            _ => unreachable!(),
61        }
62    }
63
64    #[inline]
65    fn from_octant0(&self, p: Point) -> Point {
66        match self.0 {
67            0 => Point::new(p.x, p.y),
68            1 => Point::new(p.y, p.x),
69            2 => Point::new(-p.y, p.x),
70            3 => Point::new(-p.x, p.y),
71            4 => Point::new(-p.x, -p.y),
72            5 => Point::new(-p.y, -p.x),
73            6 => Point::new(p.y, -p.x),
74            7 => Point::new(p.x, -p.y),
75            _ => unreachable!(),
76        }
77    }
78}
79
80impl Bresenham {
81    /// Creates a new iterator.Yields intermediate points between `start`
82    /// and `end`. Does include `start` but not `end`.
83    #[inline]
84    pub fn new(start: Point, end: Point) -> Bresenham {
85        let octant = Octant::from_points(start, end);
86
87        let start = octant.to_octant0(start);
88        let end = octant.to_octant0(end);
89
90        let dx = end.x - start.x;
91        let dy = end.y - start.y;
92
93        Bresenham {
94            x: start.x,
95            y: start.y,
96            dx,
97            dy,
98            x1: end.x,
99            diff: dy - dx,
100            octant,
101        }
102    }
103
104        /// Return the next point without checking if we are past `end`.
105        #[inline]
106        pub fn advance(&mut self) -> Point {
107            let p = Point::new(self.x, self.y);
108    
109            if self.diff >= 0 {
110                self.y += 1;
111                self.diff -= self.dx;
112            }
113    
114            self.diff += self.dy;
115    
116            // loop inc
117            self.x += 1;
118    
119            self.octant.from_octant0(p)
120        }
121}
122
123impl Iterator for Bresenham {
124    type Item = Point;
125
126    #[inline]
127    fn next(&mut self) -> Option<Self::Item> {
128        if self.x >= self.x1 {
129            None
130        } else {
131            Some(self.advance())
132        }
133    }
134}
135
136/// New type over `Bresenham` which include the `end` points when iterated over.
137pub struct BresenhamInclusive(Bresenham);
138impl BresenhamInclusive {
139    /// Creates a new iterator. Yields points `start..=end`.
140    #[inline]
141    pub fn new(start: Point, end: Point) -> Self {
142        Self(Bresenham::new(start, end))
143    }
144
145    /// Return the next point without checking if we are past `end`.
146    #[inline]
147    pub fn advance(&mut self) -> Point {
148        self.0.advance()
149    }
150}
151impl Iterator for BresenhamInclusive {
152    type Item = Point;
153
154    #[inline]
155    fn next(&mut self) -> Option<Self::Item> {
156        if self.0.x > self.0.x1 {
157            None
158        } else {
159            Some(self.0.advance())
160        }
161    }
162}
163
164#[cfg(test)]
165mod tests {
166    use super::*;
167    use std::vec::Vec;
168
169    #[test]
170    fn test_empty() {
171        let bi = Bresenham::new(Point::new(0, 0), Point::new(0, 0));
172        let res: Vec<_> = bi.collect();
173        assert_eq!(res, []);
174
175        let bi = BresenhamInclusive::new(Point::new(0, 0), Point::new(0, 0));
176        let res: Vec<_> = bi.collect();
177        assert_eq!(res, [Point::new(0, 0)]);
178
179        let mut bi = BresenhamInclusive::new(Point::new(0, 0), Point::new(0, 0));
180        bi.advance();
181        let res: Vec<_> = bi.collect();
182        assert_eq!(res, []);
183    }
184
185    #[test]
186    fn test_wp_example() {
187        let start = Point::new(0, 1);
188        let end = Point::new(6, 4);
189
190        let bi = Bresenham::new(start, end);
191        let res: Vec<_> = bi.collect();
192        let mut expected = vec![
193            Point::new(0, 1),
194            Point::new(1, 1),
195            Point::new(2, 2),
196            Point::new(3, 2),
197            Point::new(4, 3),
198            Point::new(5, 3)
199        ];
200        assert_eq!(res, expected);
201
202        let bi = BresenhamInclusive::new(start, end);
203        let res: Vec<_> = bi.collect();
204        expected.push(end);
205        assert_eq!(res, expected);
206    }
207
208    #[test]
209    fn test_inverse_wp() {
210        let start = Point::new(6, 4);
211        let end = Point::new(0, 1);
212
213        let bi = Bresenham::new(start, end);
214        let res: Vec<_> = bi.collect();
215        let mut expected = vec![
216            Point::new(6, 4),
217            Point::new(5, 4),
218            Point::new(4, 3),
219            Point::new(3, 3),
220            Point::new(2, 2),
221            Point::new(1, 2)
222        ];
223        assert_eq!(res, expected);
224
225        let bi = BresenhamInclusive::new(start, end);
226        let res: Vec<_> = bi.collect();
227        expected.push(end);
228        assert_eq!(res, expected);
229    }
230
231    #[test]
232    fn test_straight_hline() {
233        let start = Point::new(2, 3);
234        let end = Point::new(5, 3);
235
236        let bi = Bresenham::new(start, end);
237        let res: Vec<_> = bi.collect();
238        let mut expected = vec![Point::new(2, 3), Point::new(3, 3), Point::new(4, 3)];
239        assert_eq!(res, expected);
240
241        let bi = BresenhamInclusive::new(start, end);
242        let res: Vec<_> = bi.collect();
243        expected.push(end);
244        assert_eq!(res, expected);
245    }
246
247    #[test]
248    fn test_straight_vline() {
249        let start = Point::new(2, 3);
250        let end = Point::new(2, 6);
251
252        let bi = Bresenham::new(start, end);
253        let res: Vec<_> = bi.collect();
254        let mut expected = vec![Point::new(2, 3), Point::new(2, 4), Point::new(2, 5)];
255        assert_eq!(res, expected);
256
257        let bi = BresenhamInclusive::new(start, end);
258        let res: Vec<_> = bi.collect();
259        expected.push(end);
260        assert_eq!(res, expected);
261    }
262
263    #[test]
264    fn test_issue135_line() {
265        let line = Bresenham::new(Point::new(0, 6), Point::new(6, 0));
266        let res: Vec<Point> = line.collect();
267        assert!(res.len() == 6);
268        res.iter().for_each(|p| {
269            assert!(p.x >= 0);
270            assert!(p.x < 7);
271            assert!(p.y >= 0);
272            assert!(p.y < 7);
273        });
274    }
275
276    #[test]
277    fn test_line_sweep() {
278        use crate::prelude::*;
279        let mut angle = Degrees::new(0.0);
280        let start_point = Point::new(20, 20);
281        while angle.0 < 360.0 {
282            let end_point = project_angle(Point::new(0, 0), 8.0, angle) + start_point;
283            let line = Bresenham::new(start_point, end_point);
284            let res: Vec<Point> = line.collect();
285            assert!(res.len() > 0);
286            res.iter().for_each(|p| {
287                assert!(p.x >= 10);
288                assert!(p.x < 30);
289                assert!(p.y >= 10);
290                assert!(p.y < 30);
291            });
292            angle.0 += 1.0;
293        }
294    }
295}
bracket_geometry/line_bresenham.rs

bracket_geometry/
line_bresenham.rs
