bracket_geometry/
circle_bresenham.rs

1use crate::prelude::Point;
2
3/// An implementation of [Bresenham's circle algorithm].
4/// [Bresenham's circle algorithm]: http://members.chello.at/~easyfilter/bresenham.html
5/// Derived from the line_drawing crate, but specialized to use BTerm's types.
6pub struct BresenhamCircle {
7    x: i32,
8    y: i32,
9    center: Point,
10    radius: i32,
11    error: i32,
12    quadrant: u8,
13}
14
15impl BresenhamCircle {
16    /// Creates a new circle, using the Bresenham Circle algorithm.
17    /// 
18    /// # Arguments
19    /// 
20    /// * `center` - the center of the circle.
21    /// * `radius` - the radius of the desired circle.
22    #[inline]
23    #[allow(dead_code)]
24    pub fn new(center: Point, radius: i32) -> Self {
25        Self {
26            center,
27            radius,
28            x: -radius,
29            y: 0,
30            error: 2 - 2 * radius,
31            quadrant: 1,
32        }
33    }
34}
35
36impl Iterator for BresenhamCircle {
37    type Item = Point;
38
39    #[inline]
40    fn next(&mut self) -> Option<Self::Item> {
41        if self.x < 0 {
42            let point = match self.quadrant {
43                1 => (self.center.x - self.x, self.center.y + self.y),
44                2 => (self.center.x - self.y, self.center.y - self.x),
45                3 => (self.center.x + self.x, self.center.y - self.y),
46                4 => (self.center.x + self.y, self.center.y + self.x),
47                _ => unreachable!(),
48            };
49
50            // Update the variables after each set of quadrants
51            if self.quadrant == 4 {
52                self.radius = self.error;
53
54                if self.radius <= self.y {
55                    self.y += 1;
56                    self.error += self.y * 2 + 1;
57                }
58
59                if self.radius > self.x || self.error > self.y {
60                    self.x += 1;
61                    self.error += self.x * 2 + 1;
62                }
63            }
64
65            self.quadrant = self.quadrant % 4 + 1;
66
67            Some(Point::from_tuple(point))
68        } else {
69            None
70        }
71    }
72}
73
74/// A version of the Bresenham circle that does not make diagonal jumps
75pub struct BresenhamCircleNoDiag {
76    x: i32,
77    y: i32,
78    center: Point,
79    // radius: i32,
80    error: i32,
81    quadrant: u8,
82}
83
84impl BresenhamCircleNoDiag {
85    /// Creates a Bresenham Circle without allowing diagonal gaps.
86    /// 
87    /// # Arguments
88    /// 
89    /// * `center` - the center of the circle
90    /// * `radius` - the radius of the circle
91    #[inline]
92    #[allow(dead_code)]
93    pub fn new(center: Point, radius: i32) -> Self {
94        Self {
95            center,
96            x: -radius,
97            y: 0,
98            error: 0,
99            quadrant: 1,
100        }
101    }
102}
103
104impl Iterator for BresenhamCircleNoDiag {
105    type Item = Point;
106
107    #[inline]
108    fn next(&mut self) -> Option<Self::Item> {
109        if self.x < 0 {
110            let point = match self.quadrant {
111                1 => (self.center.x - self.x, self.center.y + self.y),
112                2 => (self.center.x - self.y, self.center.y - self.x),
113                3 => (self.center.x + self.x, self.center.y - self.y),
114                4 => (self.center.x + self.y, self.center.y + self.x),
115                _ => unreachable!(),
116            };
117
118            // Update the variables after each set of quadrants.
119            if self.quadrant == 4 {
120                // This version moves in x or in y - not both - depending on the error.
121                if (self.error + 2 * self.x + 1).abs() <= (self.error + 2 * self.y + 1).abs() {
122                    self.error += self.x * 2 + 1;
123                    self.x += 1;
124                } else {
125                    self.error += self.y * 2 + 1;
126                    self.y += 1;
127                }
128            }
129
130            self.quadrant = self.quadrant % 4 + 1;
131
132            Some(Point::from_tuple(point))
133        } else {
134            None
135        }
136    }
137}
138
139#[cfg(test)]
140mod tests {
141    use crate::prelude::{BresenhamCircle, BresenhamCircleNoDiag, Point};
142
143    #[test]
144    fn circle_test_radius1() {
145        let circle = BresenhamCircle::new(Point::new(0, 0), 1);
146        let points: Vec<Point> = circle.collect();
147        assert_eq!(
148            points,
149            vec![
150                Point::new(1, 0),
151                Point::new(0, 1),
152                Point::new(-1, 0),
153                Point::new(0, -1)
154            ]
155        );
156    }
157
158    #[test]
159    fn circle_test_radius3() {
160        let circle = BresenhamCircle::new(Point::new(0, 0), 3);
161        let points: Vec<Point> = circle.collect();
162        assert_eq!(
163            points,
164            vec![
165                Point { x: 3, y: 0 },
166                Point { x: 0, y: 3 },
167                Point { x: -3, y: 0 },
168                Point { x: 0, y: -3 },
169                Point { x: 3, y: 1 },
170                Point { x: -1, y: 3 },
171                Point { x: -3, y: -1 },
172                Point { x: 1, y: -3 },
173                Point { x: 2, y: 2 },
174                Point { x: -2, y: 2 },
175                Point { x: -2, y: -2 },
176                Point { x: 2, y: -2 },
177                Point { x: 1, y: 3 },
178                Point { x: -3, y: 1 },
179                Point { x: -1, y: -3 },
180                Point { x: 3, y: -1 }
181            ]
182        );
183    }
184
185    #[test]
186    fn circle_nodiag_test_radius3() {
187        let circle = BresenhamCircleNoDiag::new(Point::new(0, 0), 3);
188        let points: Vec<Point> = circle.collect();
189        assert_eq!(
190            points,
191            vec![
192                Point { x: 3, y: 0 },
193                Point { x: 0, y: 3 },
194                Point { x: -3, y: 0 },
195                Point { x: 0, y: -3 },
196                Point { x: 3, y: 1 },
197                Point { x: -1, y: 3 },
198                Point { x: -3, y: -1 },
199                Point { x: 1, y: -3 },
200                Point { x: 2, y: 1 },
201                Point { x: -1, y: 2 },
202                Point { x: -2, y: -1 },
203                Point { x: 1, y: -2 },
204                Point { x: 2, y: 2 },
205                Point { x: -2, y: 2 },
206                Point { x: -2, y: -2 },
207                Point { x: 2, y: -2 },
208                Point { x: 1, y: 2 },
209                Point { x: -2, y: 1 },
210                Point { x: -1, y: -2 },
211                Point { x: 2, y: -1 },
212                Point { x: 1, y: 3 },
213                Point { x: -3, y: 1 },
214                Point { x: -1, y: -3 },
215                Point { x: 3, y: -1 }
216            ]
217        );
218    }
219}
bracket_geometry/circle_bresenham.rs

bracket_geometry/
circle_bresenham.rs
