mapping_algorithms/lines/
bresenham.rs

1// SPDX-License-Identifier: MIT
2/*
3 * Copyright (c) [2023 - Present] Emily Matheys <emilymatt96@gmail.com>
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a copy
6 * of this software and associated documentation files (the "Software"), to deal
7 * in the Software without restriction, including without limitation the rights
8 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 * copies of the Software, and to permit persons to whom the Software is
10 * furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be included in all
13 * copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21 * SOFTWARE.
22 */
23
24use nalgebra::{ComplexField, Point, RealField, Scalar};
25use num_traits::AsPrimitive;
26
27use crate::{array, Vec};
28
29/// This is a free-form version of the bresenham line-drawing algorithm,
30/// allowing for any input, any output, and N dimensions, under the constraints of the function.
31///
32/// # Arguments
33/// * `start_point`: A [`Point`] of floating type `F` and `N` dimensions, representing the starting point of the line.
34/// * `end_point`: A [`Point`] of floating type `F` and `N` dimensions, representing the ending point of the line.
35///
36/// # Generics
37/// * F: either [`prim@f32`] or [`prim@f64`]
38/// * N: a usize, representing the dimension to use
39///
40/// # Returns
41/// A [`Vec`] of [`Point`]s with inner type `T`, representing the drawn line, including the starting point and ending point.
42///
43/// NOTE: The returned [`Vec`] will always go from the starting point to the ending point, regardless of direction in axis.
44#[cfg_attr(
45    feature = "tracing",
46    tracing::instrument("Plot Bresenham Line", skip_all)
47)]
48pub fn plot_bresenham_line<F, T, const N: usize>(
49    start_point: Point<F, N>,
50    end_point: Point<F, N>,
51) -> Vec<Point<T, N>>
52where
53    F: RealField + AsPrimitive<usize> + AsPrimitive<T>,
54    usize: AsPrimitive<F>,
55    T: Scalar + Copy,
56{
57    let deltas: [F; N] =
58        array::from_fn(|idx| <F as ComplexField>::abs(end_point[idx] - start_point[idx]));
59    let steps: [F; N] = array::from_fn(|idx| {
60        if end_point[idx] > start_point[idx] {
61            F::one()
62        } else {
63            -F::one()
64        }
65    });
66    let primary_axis = deltas
67        .iter()
68        .enumerate()
69        .max_by(|a, b| a.1.partial_cmp(b.1).unwrap())
70        .unwrap()
71        .0;
72
73    let mut current_point = start_point;
74    let mut errors = Vec::from([F::zero(); N]);
75    let mut points = Vec::with_capacity(<F as AsPrimitive<usize>>::as_(
76        deltas[primary_axis] + F::one(),
77    ));
78    while <F as ComplexField>::abs(current_point[primary_axis] - end_point[primary_axis])
79        >= F::one()
80    {
81        points.push(current_point.map(|element| element.as_()));
82
83        for axis in 0..N {
84            if axis == primary_axis {
85                continue;
86            }
87
88            errors[axis] += deltas[axis] / deltas[primary_axis];
89
90            if errors[axis] >= F::one() - (F::one() / (N + 1).as_()) {
91                current_point[axis] += steps[axis];
92                errors[axis] -= F::one();
93            }
94        }
95
96        current_point[primary_axis] += steps[primary_axis];
97    }
98
99    points.push(end_point.map(|element| element.as_()));
100    points
101}
102
103#[cfg(feature = "pregenerated")]
104macro_rules! impl_bresenham_algorithm {
105    ($precision:expr, doc $doc:tt, $nd:expr, $out:expr) => {
106        ::paste::paste! {
107            #[doc = "A premade variant of the bresenham line function for " $doc "-precision floating-point arithmetic, returns a [`Vec`] of [`Point`]s with inner type " $out "."]
108            pub fn [<plot_$nd d_$out _bresenham_line>](start_point: Point<$precision, $nd>, end_point: Point<$precision, $nd>) -> Vec<Point<$out, $nd>> {
109                    super::plot_bresenham_line::<$precision, $out, $nd>(start_point, end_point)
110            }
111        }
112    };
113
114    ($prec:expr, doc $doc:tt, $nd:expr) => {
115        impl_bresenham_algorithm!($prec, doc $doc, $nd, i32);
116        impl_bresenham_algorithm!($prec, doc $doc, $nd, i64);
117        impl_bresenham_algorithm!($prec, doc $doc, $nd, isize);
118
119        impl_bresenham_algorithm!($prec, doc $doc, $nd, u32);
120        impl_bresenham_algorithm!($prec, doc $doc, $nd, u64);
121        impl_bresenham_algorithm!($prec, doc $doc, $nd, usize);
122
123        impl_bresenham_algorithm!($prec, doc $doc, $nd, f32);
124        impl_bresenham_algorithm!($prec, doc $doc, $nd, f64);
125    };
126
127    ($prec:expr, doc $doc:tt) => {
128        ::paste::paste! {
129            pub(super) mod [<$doc _precision>] {
130                use nalgebra::Point;
131                use crate::Vec;
132
133                impl_bresenham_algorithm!($prec, doc $doc, 2);
134                impl_bresenham_algorithm!($prec, doc $doc, 3);
135            }
136        }
137    }
138}
139
140#[cfg(feature = "pregenerated")]
141impl_bresenham_algorithm!(f32, doc single);
142#[cfg(feature = "pregenerated")]
143impl_bresenham_algorithm!(f64, doc double);
144
145#[cfg(test)]
146mod tests {
147    use super::*;
148    use nalgebra::{Point2, Point3};
149
150    fn calculate_expected_vec_size<const N: usize>(
151        start: Point<f32, N>,
152        end: Point<f32, N>,
153    ) -> usize {
154        let arr: [f32; N] = array::from_fn(|idx| f32::abs(end[idx] - start[idx]));
155        arr.into_iter().max_by(|a, b| a.total_cmp(b)).unwrap() as usize + 1
156    }
157
158    #[test]
159    fn test_plot_bresenham_line_2d_nonsteep_pos() {
160        let start = Point2::new(0.0f32, 0.0f32);
161        let end = Point2::new(10.0f32, 3.0f32);
162        let res = plot_bresenham_line(start, end);
163        assert_eq!(
164            res,
165            Vec::<Point2<isize>>::from([
166                Point2::new(0, 0),
167                Point2::new(1, 0),
168                Point2::new(2, 0),
169                Point2::new(3, 1),
170                Point2::new(4, 1),
171                Point2::new(5, 1),
172                Point2::new(6, 2),
173                Point2::new(7, 2),
174                Point2::new(8, 2),
175                Point2::new(9, 3),
176                Point2::new(10, 3),
177            ])
178        );
179    }
180
181    #[test]
182    fn test_plot_bresenham_line_2d_steep_pos() {
183        let start = Point2::new(0.0f32, 0.0f32);
184        let end = Point2::new(3.0f32, 10.0f32);
185        let res = plot_bresenham_line(start, end);
186        assert_eq!(res.len(), calculate_expected_vec_size(start, end));
187        assert_eq!(
188            res,
189            Vec::<Point2<isize>>::from([
190                Point2::new(0, 0),
191                Point2::new(0, 1),
192                Point2::new(0, 2),
193                Point2::new(1, 3),
194                Point2::new(1, 4),
195                Point2::new(1, 5),
196                Point2::new(2, 6),
197                Point2::new(2, 7),
198                Point2::new(2, 8),
199                Point2::new(3, 9),
200                Point2::new(3, 10),
201            ])
202        );
203    }
204
205    #[test]
206    fn test_plot_bresenham_line_2d_nonsteep_neg() {
207        let start = Point2::new(0.0f32, 0.0f32);
208        let end = Point2::new(-10.0f32, -3.0f32);
209        let res = plot_bresenham_line(start, end);
210        assert_eq!(res.len(), calculate_expected_vec_size(start, end));
211        assert_eq!(
212            res,
213            Vec::<Point2<isize>>::from([
214                Point2::new(0, 0),
215                Point2::new(-1, 0),
216                Point2::new(-2, 0),
217                Point2::new(-3, -1),
218                Point2::new(-4, -1),
219                Point2::new(-5, -1),
220                Point2::new(-6, -2),
221                Point2::new(-7, -2),
222                Point2::new(-8, -2),
223                Point2::new(-9, -3),
224                Point2::new(-10, -3),
225            ])
226        );
227    }
228
229    #[test]
230    fn test_plot_bresenham_line_2d_steep_neg() {
231        let start = Point2::new(0.0f32, 0.0f32);
232        let end = Point2::new(-3.0f32, -10.0f32);
233        let res = plot_bresenham_line(start, end);
234        assert_eq!(res.len(), calculate_expected_vec_size(start, end));
235        assert_eq!(
236            res,
237            Vec::<Point2<isize>>::from([
238                Point2::new(0, 0),
239                Point2::new(0, -1),
240                Point2::new(0, -2),
241                Point2::new(-1, -3),
242                Point2::new(-1, -4),
243                Point2::new(-1, -5),
244                Point2::new(-2, -6),
245                Point2::new(-2, -7),
246                Point2::new(-2, -8),
247                Point2::new(-3, -9),
248                Point2::new(-3, -10),
249            ])
250        );
251    }
252
253    #[test]
254    fn test_plot_bresenham_line_3d_x() {
255        let start = Point3::new(0.0f32, 0.0f32, 0.0f32);
256        let end = Point3::new(-3.0f32, -10.0f32, 7.0f32);
257        let res = plot_bresenham_line(start, end);
258        assert_eq!(res.len(), calculate_expected_vec_size(start, end));
259        assert_eq!(
260            res,
261            Vec::<Point3<isize>>::from([
262                Point3::new(0, 0, 0),
263                Point3::new(0, -1, 0),
264                Point3::new(0, -2, 1),
265                Point3::new(-1, -3, 2),
266                Point3::new(-1, -4, 3),
267                Point3::new(-1, -5, 3),
268                Point3::new(-2, -6, 4),
269                Point3::new(-2, -7, 5),
270                Point3::new(-2, -8, 5),
271                Point3::new(-2, -9, 6),
272                Point3::new(-3, -10, 7),
273            ])
274        );
275    }
276
277    #[test]
278    fn test_small_deltas() {
279        let start = Point3::new(512.0, 512.0, 512.0);
280        let end = Point3::new(512.5, 511.294, 512.1);
281
282        let res: Vec<Point3<usize>> = plot_bresenham_line(start, end);
283        assert_eq!(res.len(), 1)
284    }
285}
mapping_algorithms/lines/bresenham.rs

mapping_algorithms/lines/
bresenham.rs
