bresenham/
lib.rs

1//! Iterator-based Bresenham's line drawing algorithm
2//!
3//! [Bresenham's line drawing algorithm]
4//! (https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm) is fast
5//! algorithm to draw a line between two points. This crate implements the fast
6//! integer variant, using an iterator-based appraoch for flexibility. It
7//! calculates coordinates without knowing anything about drawing methods or
8//! surfaces.
9//!
10//! Example:
11//!
12//! ```rust
13//! extern crate bresenham;
14//! use bresenham::Bresenham;
15//!
16//! fn main() {
17//!     for (x, y) in Bresenham::new((0, 1), (6, 4)) {
18//!         println!("{}, {}", x, y);
19//!     }
20//! }
21//! ```
22//!
23//! Will print:
24//!
25//! ```text
26//! (0, 1)
27//! (1, 1)
28//! (2, 2)
29//! (3, 2)
30//! (4, 3)
31//! (5, 3)
32//! ```
33
34#![no_std]
35
36#[cfg(test)]
37extern crate std;
38
39use core::iter::Iterator;
40
41/// Convenient typedef for two machines-sized integers
42pub type Point = (isize, isize);
43
44/// Line-drawing iterator
45pub struct Bresenham {
46    x: isize,
47    y: isize,
48    dx: isize,
49    dy: isize,
50    x1: isize,
51    diff: isize,
52    octant: Octant,
53}
54
55struct Octant(u8);
56
57impl Octant {
58    /// adapted from http://codereview.stackexchange.com/a/95551
59    #[inline]
60    fn from_points(start: Point, end: Point) -> Octant {
61        let mut dx = end.0 - start.0;
62        let mut dy = end.1 - start.1;
63
64        let mut octant = 0;
65
66        if dy < 0 {
67            dx = -dx;
68            dy = -dy;
69            octant += 4;
70        }
71
72        if dx < 0 {
73            let tmp = dx;
74            dx = dy;
75            dy = -tmp;
76            octant += 2
77        }
78
79        if dx < dy {
80            octant += 1
81        }
82
83        Octant(octant)
84    }
85
86    #[inline]
87    fn to_octant0(&self, p: Point) -> Point {
88        match self.0 {
89            0 => (p.0, p.1),
90            1 => (p.1, p.0),
91            2 => (p.1, -p.0),
92            3 => (-p.0, p.1),
93            4 => (-p.0, -p.1),
94            5 => (-p.1, -p.0),
95            6 => (-p.1, p.0),
96            7 => (p.0, -p.1),
97            _ => unreachable!(),
98        }
99    }
100
101    #[inline]
102    fn from_octant0(&self, p: Point) -> Point {
103        match self.0 {
104            0 => (p.0, p.1),
105            1 => (p.1, p.0),
106            2 => (-p.1, p.0),
107            3 => (-p.0, p.1),
108            4 => (-p.0, -p.1),
109            5 => (-p.1, -p.0),
110            6 => (p.1, -p.0),
111            7 => (p.0, -p.1),
112            _ => unreachable!(),
113        }
114    }
115}
116
117impl Bresenham {
118    /// Creates a new iterator.Yields intermediate points between `start`
119    /// and `end`. Does include `start` but not `end`.
120    #[inline]
121    pub fn new(start: Point, end: Point) -> Bresenham {
122        let octant = Octant::from_points(start, end);
123
124        let start = octant.to_octant0(start);
125        let end = octant.to_octant0(end);
126
127        let dx = end.0 - start.0;
128        let dy = end.1 - start.1;
129
130        Bresenham {
131            x: start.0,
132            y: start.1,
133            dx: dx,
134            dy: dy,
135            x1: end.0,
136            diff: dy - dx,
137            octant: octant,
138        }
139    }
140}
141
142impl Iterator for Bresenham {
143    type Item = Point;
144
145    #[inline]
146    fn next(&mut self) -> Option<Self::Item> {
147        if self.x >= self.x1 {
148            return None;
149        }
150
151        let p = (self.x, self.y);
152
153        if self.diff >= 0 {
154            self.y += 1;
155            self.diff -= self.dx;
156        }
157
158        self.diff += self.dy;
159
160        // loop inc
161        self.x += 1;
162
163        Some(self.octant.from_octant0(p))
164    }
165}
166
167
168#[cfg(test)]
169mod tests {
170    use super::Bresenham;
171    use std::vec::Vec;
172
173    #[test]
174    fn test_wp_example() {
175        let bi = Bresenham::new((0, 1), (6, 4));
176        let res: Vec<_> = bi.collect();
177
178        assert_eq!(res, [(0, 1), (1, 1), (2, 2), (3, 2), (4, 3), (5, 3)])
179    }
180
181    #[test]
182    fn test_inverse_wp() {
183        let bi = Bresenham::new((6, 4), (0, 1));
184        let res: Vec<_> = bi.collect();
185
186        assert_eq!(res, [(6, 4), (5, 4), (4, 3), (3, 3), (2, 2), (1, 2)])
187    }
188
189    #[test]
190    fn test_straight_hline() {
191        let bi = Bresenham::new((2, 3), (5, 3));
192        let res: Vec<_> = bi.collect();
193
194        assert_eq!(res, [(2, 3), (3, 3), (4, 3)]);
195    }
196
197    #[test]
198    fn test_straight_vline() {
199        let bi = Bresenham::new((2, 3), (2, 6));
200        let res: Vec<_> = bi.collect();
201
202        assert_eq!(res, [(2, 3), (2, 4), (2, 5)]);
203    }
204}
bresenham/lib.rs

bresenham/
lib.rs
