imageproc/drawing/
line.rs

1use crate::definitions::Image;
2use crate::drawing::Canvas;
3use image::{GenericImage, ImageBuffer, Pixel};
4use std::f32;
5use std::i32;
6use std::mem::{swap, transmute};
7
8/// Iterates over the coordinates in a line segment using
9/// [Bresenham's line drawing algorithm](https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm).
10pub struct BresenhamLineIter {
11    dx: f32,
12    dy: f32,
13    x: i32,
14    y: i32,
15    error: f32,
16    end_x: i32,
17    is_steep: bool,
18    y_step: i32,
19}
20
21impl BresenhamLineIter {
22    /// Creates a [`BresenhamLineIter`](struct.BresenhamLineIter.html) which will iterate over the integer coordinates
23    /// between `start` and `end`.
24    pub fn new(start: (f32, f32), end: (f32, f32)) -> BresenhamLineIter {
25        let (mut x0, mut y0) = (start.0, start.1);
26        let (mut x1, mut y1) = (end.0, end.1);
27
28        let is_steep = (y1 - y0).abs() > (x1 - x0).abs();
29        if is_steep {
30            swap(&mut x0, &mut y0);
31            swap(&mut x1, &mut y1);
32        }
33
34        if x0 > x1 {
35            swap(&mut x0, &mut x1);
36            swap(&mut y0, &mut y1);
37        }
38
39        let dx = x1 - x0;
40
41        BresenhamLineIter {
42            dx,
43            dy: (y1 - y0).abs(),
44            x: x0 as i32,
45            y: y0 as i32,
46            error: dx / 2f32,
47            end_x: x1 as i32,
48            is_steep,
49            y_step: if y0 < y1 { 1 } else { -1 },
50        }
51    }
52}
53
54impl Iterator for BresenhamLineIter {
55    type Item = (i32, i32);
56
57    fn next(&mut self) -> Option<(i32, i32)> {
58        if self.x > self.end_x {
59            None
60        } else {
61            let ret = if self.is_steep {
62                (self.y, self.x)
63            } else {
64                (self.x, self.y)
65            };
66
67            self.x += 1;
68            self.error -= self.dy;
69            if self.error < 0f32 {
70                self.y += self.y_step;
71                self.error += self.dx;
72            }
73
74            Some(ret)
75        }
76    }
77}
78
79fn clamp(x: f32, upper_bound: u32) -> f32 {
80    if x < 0f32 {
81        return 0f32;
82    }
83    if x >= upper_bound as f32 {
84        return (upper_bound - 1) as f32;
85    }
86    x
87}
88
89fn clamp_point<I: GenericImage>(p: (f32, f32), image: &I) -> (f32, f32) {
90    (clamp(p.0, image.width()), clamp(p.1, image.height()))
91}
92
93/// Iterates over the image pixels in a line segment using
94/// [Bresenham's line drawing algorithm](https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm).
95pub struct BresenhamLinePixelIter<'a, P: Pixel> {
96    iter: BresenhamLineIter,
97    image: &'a Image<P>,
98}
99
100impl<'a, P: Pixel> BresenhamLinePixelIter<'a, P> {
101    /// Creates a [`BresenhamLinePixelIter`](struct.BresenhamLinePixelIter.html) which will iterate over
102    /// the image pixels with coordinates between `start` and `end`.
103    pub fn new(
104        image: &Image<P>,
105        start: (f32, f32),
106        end: (f32, f32),
107    ) -> BresenhamLinePixelIter<'_, P> {
108        assert!(
109            image.width() >= 1 && image.height() >= 1,
110            "BresenhamLinePixelIter does not support empty images"
111        );
112        let iter = BresenhamLineIter::new(clamp_point(start, image), clamp_point(end, image));
113        BresenhamLinePixelIter { iter, image }
114    }
115}
116
117impl<'a, P: Pixel> Iterator for BresenhamLinePixelIter<'a, P> {
118    type Item = &'a P;
119
120    fn next(&mut self) -> Option<Self::Item> {
121        self.iter
122            .next()
123            .map(|p| self.image.get_pixel(p.0 as u32, p.1 as u32))
124    }
125}
126
127/// Iterates over the image pixels in a line segment using
128/// [Bresenham's line drawing algorithm](https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm).
129pub struct BresenhamLinePixelIterMut<'a, P: Pixel> {
130    iter: BresenhamLineIter,
131    image: &'a mut Image<P>,
132}
133
134impl<'a, P: Pixel> BresenhamLinePixelIterMut<'a, P> {
135    /// Creates a [`BresenhamLinePixelIterMut`](struct.BresenhamLinePixelIterMut.html) which will iterate over
136    /// the image pixels with coordinates between `start` and `end`.
137    pub fn new(
138        image: &mut Image<P>,
139        start: (f32, f32),
140        end: (f32, f32),
141    ) -> BresenhamLinePixelIterMut<'_, P> {
142        assert!(
143            image.width() >= 1 && image.height() >= 1,
144            "BresenhamLinePixelIterMut does not support empty images"
145        );
146        // The next two assertions are for https://github.com/image-rs/imageproc/issues/281
147        assert!(P::CHANNEL_COUNT > 0);
148        assert!(
149            image.width() < i32::max_value() as u32 && image.height() < i32::max_value() as u32,
150            "Image dimensions are too large"
151        );
152        let iter = BresenhamLineIter::new(clamp_point(start, image), clamp_point(end, image));
153        BresenhamLinePixelIterMut { iter, image }
154    }
155}
156
157impl<'a, P: Pixel> Iterator for BresenhamLinePixelIterMut<'a, P> {
158    type Item = &'a mut P;
159
160    fn next(&mut self) -> Option<Self::Item> {
161        self.iter
162            .next()
163            .map(|p| self.image.get_pixel_mut(p.0 as u32, p.1 as u32))
164            .map(|p| unsafe { transmute(p) })
165    }
166}
167
168/// Draws a line segment on a new copy of an image.
169///
170/// Draws as much of the line segment between start and end as lies inside the image bounds.
171///
172/// Uses [Bresenham's line drawing algorithm](https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm).
173#[must_use = "the function does not modify the original image"]
174pub fn draw_line_segment<I>(
175    image: &I,
176    start: (f32, f32),
177    end: (f32, f32),
178    color: I::Pixel,
179) -> Image<I::Pixel>
180where
181    I: GenericImage,
182{
183    let mut out = ImageBuffer::new(image.width(), image.height());
184    out.copy_from(image, 0, 0).unwrap();
185    draw_line_segment_mut(&mut out, start, end, color);
186    out
187}
188
189/// Draws a line segment on an image in place.
190///
191/// Draws as much of the line segment between start and end as lies inside the image bounds.
192///
193/// Uses [Bresenham's line drawing algorithm](https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm).
194pub fn draw_line_segment_mut<C>(canvas: &mut C, start: (f32, f32), end: (f32, f32), color: C::Pixel)
195where
196    C: Canvas,
197{
198    let (width, height) = canvas.dimensions();
199    let in_bounds = |x, y| x >= 0 && x < width as i32 && y >= 0 && y < height as i32;
200
201    let line_iterator = BresenhamLineIter::new(start, end);
202
203    for point in line_iterator {
204        let x = point.0;
205        let y = point.1;
206
207        if in_bounds(x, y) {
208            canvas.draw_pixel(x as u32, y as u32, color);
209        }
210    }
211}
212
213/// Draws an antialised line segment on a new copy of an image.
214///
215/// Draws as much of the line segment between `start` and `end` as lies inside the image bounds.
216///
217/// The parameters of blend are (line color, original color, line weight).
218/// Consider using [`interpolate`](fn.interpolate.html) for blend.
219///
220/// Uses [Xu's line drawing algorithm](https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm).
221#[must_use = "the function does not modify the original image"]
222pub fn draw_antialiased_line_segment<I, B>(
223    image: &I,
224    start: (i32, i32),
225    end: (i32, i32),
226    color: I::Pixel,
227    blend: B,
228) -> Image<I::Pixel>
229where
230    I: GenericImage,
231
232    B: Fn(I::Pixel, I::Pixel, f32) -> I::Pixel,
233{
234    let mut out = ImageBuffer::new(image.width(), image.height());
235    out.copy_from(image, 0, 0).unwrap();
236    draw_antialiased_line_segment_mut(&mut out, start, end, color, blend);
237    out
238}
239
240/// Draws an antialised line segment on an image in place.
241///
242/// Draws as much of the line segment between `start` and `end` as lies inside the image bounds.
243///
244/// The parameters of blend are (line color, original color, line weight).
245/// Consider using [`interpolate`](fn.interpolate.html) for blend.
246///
247/// Uses [Xu's line drawing algorithm](https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm).
248pub fn draw_antialiased_line_segment_mut<I, B>(
249    image: &mut I,
250    start: (i32, i32),
251    end: (i32, i32),
252    color: I::Pixel,
253    blend: B,
254) where
255    I: GenericImage,
256
257    B: Fn(I::Pixel, I::Pixel, f32) -> I::Pixel,
258{
259    let (mut x0, mut y0) = (start.0, start.1);
260    let (mut x1, mut y1) = (end.0, end.1);
261
262    let is_steep = (y1 - y0).abs() > (x1 - x0).abs();
263
264    if is_steep {
265        if y0 > y1 {
266            swap(&mut x0, &mut x1);
267            swap(&mut y0, &mut y1);
268        }
269        let plotter = Plotter {
270            image,
271            transform: |x, y| (y, x),
272            blend,
273        };
274        plot_wu_line(plotter, (y0, x0), (y1, x1), color);
275    } else {
276        if x0 > x1 {
277            swap(&mut x0, &mut x1);
278            swap(&mut y0, &mut y1);
279        }
280        let plotter = Plotter {
281            image,
282            transform: |x, y| (x, y),
283            blend,
284        };
285        plot_wu_line(plotter, (x0, y0), (x1, y1), color);
286    };
287}
288
289fn plot_wu_line<I, T, B>(
290    mut plotter: Plotter<'_, I, T, B>,
291    start: (i32, i32),
292    end: (i32, i32),
293    color: I::Pixel,
294) where
295    I: GenericImage,
296
297    T: Fn(i32, i32) -> (i32, i32),
298    B: Fn(I::Pixel, I::Pixel, f32) -> I::Pixel,
299{
300    let dx = end.0 - start.0;
301    let dy = end.1 - start.1;
302    let gradient = dy as f32 / dx as f32;
303    let mut fy = start.1 as f32;
304
305    for x in start.0..(end.0 + 1) {
306        plotter.plot(x, fy as i32, color, 1.0 - fy.fract());
307        plotter.plot(x, fy as i32 + 1, color, fy.fract());
308        fy += gradient;
309    }
310}
311
312struct Plotter<'a, I, T, B>
313where
314    I: GenericImage,
315
316    T: Fn(i32, i32) -> (i32, i32),
317    B: Fn(I::Pixel, I::Pixel, f32) -> I::Pixel,
318{
319    image: &'a mut I,
320    transform: T,
321    blend: B,
322}
323
324impl<'a, I, T, B> Plotter<'a, I, T, B>
325where
326    I: GenericImage,
327
328    T: Fn(i32, i32) -> (i32, i32),
329    B: Fn(I::Pixel, I::Pixel, f32) -> I::Pixel,
330{
331    fn in_bounds(&self, x: i32, y: i32) -> bool {
332        x >= 0 && x < self.image.width() as i32 && y >= 0 && y < self.image.height() as i32
333    }
334
335    pub fn plot(&mut self, x: i32, y: i32, line_color: I::Pixel, line_weight: f32) {
336        let (x_trans, y_trans) = (self.transform)(x, y);
337        if self.in_bounds(x_trans, y_trans) {
338            let original = self.image.get_pixel(x_trans as u32, y_trans as u32);
339            let blended = (self.blend)(line_color, original, line_weight);
340            self.image
341                .put_pixel(x_trans as u32, y_trans as u32, blended);
342        }
343    }
344}
345
346#[cfg(test)]
347mod tests {
348    use super::*;
349    use image::{GrayImage, Luma};
350
351    // As draw_line_segment is implemented in terms of BresenhamLineIter we
352    // haven't bothered wriing any tests specifically for BresenhamLineIter itself.
353
354    // Octants for line directions:
355    //
356    //   \ 5 | 6 /
357    //   4 \ | / 7
358    //   ---   ---
359    //   3 / | \ 0
360    //   / 2 | 1 \
361
362    #[test]
363    fn test_draw_line_segment_horizontal() {
364        let image = GrayImage::from_pixel(5, 5, Luma([1u8]));
365
366        let expected = gray_image!(
367            1, 1, 1, 1, 1;
368            4, 4, 4, 4, 4;
369            1, 1, 1, 1, 1;
370            1, 1, 1, 1, 1;
371            1, 1, 1, 1, 1);
372
373        let right = draw_line_segment(&image, (-3f32, 1f32), (6f32, 1f32), Luma([4u8]));
374        assert_pixels_eq!(right, expected);
375
376        let left = draw_line_segment(&image, (6f32, 1f32), (-3f32, 1f32), Luma([4u8]));
377        assert_pixels_eq!(left, expected);
378    }
379
380    #[test]
381    fn test_draw_line_segment_oct0_and_oct4() {
382        let image = GrayImage::from_pixel(5, 5, Luma([1u8]));
383
384        let expected = gray_image!(
385            1, 1, 1, 1, 1;
386            1, 9, 9, 1, 1;
387            1, 1, 1, 9, 9;
388            1, 1, 1, 1, 1;
389            1, 1, 1, 1, 1);
390
391        let oct0 = draw_line_segment(&image, (1f32, 1f32), (4f32, 2f32), Luma([9u8]));
392        assert_pixels_eq!(oct0, expected);
393
394        let oct4 = draw_line_segment(&image, (4f32, 2f32), (1f32, 1f32), Luma([9u8]));
395        assert_pixels_eq!(oct4, expected);
396    }
397
398    #[test]
399    fn test_draw_line_segment_diagonal() {
400        let image = GrayImage::from_pixel(5, 5, Luma([1u8]));
401
402        let expected = gray_image!(
403            1, 1, 1, 1, 1;
404            1, 6, 1, 1, 1;
405            1, 1, 6, 1, 1;
406            1, 1, 1, 6, 1;
407            1, 1, 1, 1, 1);
408
409        let down_right = draw_line_segment(&image, (1f32, 1f32), (3f32, 3f32), Luma([6u8]));
410        assert_pixels_eq!(down_right, expected);
411
412        let up_left = draw_line_segment(&image, (3f32, 3f32), (1f32, 1f32), Luma([6u8]));
413        assert_pixels_eq!(up_left, expected);
414    }
415
416    #[test]
417    fn test_draw_line_segment_oct1_and_oct5() {
418        let image = GrayImage::from_pixel(5, 5, Luma([1u8]));
419
420        let expected = gray_image!(
421            5, 1, 1, 1, 1;
422            5, 1, 1, 1, 1;
423            5, 1, 1, 1, 1;
424            1, 5, 1, 1, 1;
425            1, 5, 1, 1, 1);
426
427        let oct1 = draw_line_segment(&image, (0f32, 0f32), (1f32, 4f32), Luma([5u8]));
428        assert_pixels_eq!(oct1, expected);
429
430        let oct5 = draw_line_segment(&image, (1f32, 4f32), (0f32, 0f32), Luma([5u8]));
431        assert_pixels_eq!(oct5, expected);
432    }
433
434    #[test]
435    fn test_draw_line_segment_vertical() {
436        let image = GrayImage::from_pixel(5, 5, Luma([1u8]));
437
438        let expected = gray_image!(
439            1, 1, 1, 1, 1;
440            1, 1, 1, 8, 1;
441            1, 1, 1, 8, 1;
442            1, 1, 1, 8, 1;
443            1, 1, 1, 1, 1);
444
445        let down = draw_line_segment(&image, (3f32, 1f32), (3f32, 3f32), Luma([8u8]));
446        assert_pixels_eq!(down, expected);
447
448        let up = draw_line_segment(&image, (3f32, 3f32), (3f32, 1f32), Luma([8u8]));
449        assert_pixels_eq!(up, expected);
450    }
451
452    #[test]
453    fn test_draw_line_segment_oct2_and_oct6() {
454        let image = GrayImage::from_pixel(5, 5, Luma([1u8]));
455
456        let expected = gray_image!(
457            1, 1, 4, 1, 1;
458            1, 1, 4, 1, 1;
459            1, 4, 1, 1, 1;
460            1, 4, 1, 1, 1;
461            1, 1, 1, 1, 1);
462
463        let oct2 = draw_line_segment(&image, (2f32, 0f32), (1f32, 3f32), Luma([4u8]));
464        assert_pixels_eq!(oct2, expected);
465
466        let oct6 = draw_line_segment(&image, (1f32, 3f32), (2f32, 0f32), Luma([4u8]));
467        assert_pixels_eq!(oct6, expected);
468    }
469
470    #[test]
471    fn test_draw_line_segment_oct3_and_oct7() {
472        let image = GrayImage::from_pixel(5, 5, Luma([1u8]));
473
474        let expected = gray_image!(
475            1, 1, 1, 1, 1;
476            1, 1, 1, 1, 1;
477            1, 1, 1, 1, 1;
478            1, 1, 1, 2, 2;
479            2, 2, 2, 1, 1);
480
481        let oct3 = draw_line_segment(&image, (0f32, 4f32), (5f32, 3f32), Luma([2u8]));
482        assert_pixels_eq!(oct3, expected);
483
484        let oct7 = draw_line_segment(&image, (5f32, 3f32), (0f32, 4f32), Luma([2u8]));
485        assert_pixels_eq!(oct7, expected);
486    }
487
488    #[test]
489    fn test_draw_antialiased_line_segment_horizontal_and_vertical() {
490        use crate::pixelops::interpolate;
491        use image::imageops::rotate270;
492
493        let image = GrayImage::from_pixel(5, 5, Luma([1u8]));
494
495        let expected = gray_image!(
496            1, 1, 1, 1, 1;
497            1, 1, 1, 1, 1;
498            1, 1, 1, 1, 1;
499            1, 2, 2, 2, 2;
500            1, 1, 1, 1, 1);
501
502        let color = Luma([2u8]);
503        // Deliberately ends one pixel out of bounds
504        let right = draw_antialiased_line_segment(&image, (1, 3), (5, 3), color, interpolate);
505        assert_pixels_eq!(right, expected);
506
507        // Deliberately starts one pixel out of bounds
508        let left = draw_antialiased_line_segment(&image, (5, 3), (1, 3), color, interpolate);
509        assert_pixels_eq!(left, expected);
510
511        // Deliberately starts one pixel out of bounds
512        let down = draw_antialiased_line_segment(&image, (3, -1), (3, 3), color, interpolate);
513        assert_pixels_eq!(down, rotate270(&expected));
514
515        // Deliberately end one pixel out of bounds
516        let up = draw_antialiased_line_segment(&image, (3, 3), (3, -1), color, interpolate);
517        assert_pixels_eq!(up, rotate270(&expected));
518    }
519
520    #[test]
521    fn test_draw_antialiased_line_segment_diagonal() {
522        use crate::pixelops::interpolate;
523        use image::imageops::rotate90;
524
525        let image = GrayImage::from_pixel(5, 5, Luma([1u8]));
526
527        let expected = gray_image!(
528            1, 1, 1, 1, 1;
529            1, 1, 2, 1, 1;
530            1, 2, 1, 1, 1;
531            2, 1, 1, 1, 1;
532            1, 1, 1, 1, 1);
533
534        let color = Luma([2u8]);
535        let up_right = draw_antialiased_line_segment(&image, (0, 3), (2, 1), color, interpolate);
536        assert_pixels_eq!(up_right, expected);
537
538        let down_left = draw_antialiased_line_segment(&image, (2, 1), (0, 3), color, interpolate);
539        assert_pixels_eq!(down_left, expected);
540
541        let up_left = draw_antialiased_line_segment(&image, (1, 0), (3, 2), color, interpolate);
542        assert_pixels_eq!(up_left, rotate90(&expected));
543
544        let down_right = draw_antialiased_line_segment(&image, (3, 2), (1, 0), color, interpolate);
545        assert_pixels_eq!(down_right, rotate90(&expected));
546    }
547
548    #[test]
549    fn test_draw_antialiased_line_segment_oct7_and_oct3() {
550        use crate::pixelops::interpolate;
551
552        let image = GrayImage::from_pixel(5, 5, Luma([1u8]));
553
554        // Gradient is 3/4
555        let expected = gray_image!(
556            1,  1,  1,  13, 50;
557            1,  1,  25, 37,  1;
558            1,  37, 25,  1,  1;
559            50, 13, 1,   1,  1;
560            1,  1,  1,   1,  1);
561
562        let color = Luma([50u8]);
563        let oct7 = draw_antialiased_line_segment(&image, (0, 3), (4, 0), color, interpolate);
564        assert_pixels_eq!(oct7, expected);
565
566        let oct3 = draw_antialiased_line_segment(&image, (4, 0), (0, 3), color, interpolate);
567        assert_pixels_eq!(oct3, expected);
568    }
569
570    macro_rules! bench_antialiased_lines {
571        ($name:ident, $start:expr, $end:expr) => {
572            #[bench]
573            fn $name(b: &mut test::Bencher) {
574                use super::draw_antialiased_line_segment_mut;
575                use crate::pixelops::interpolate;
576
577                let mut image = GrayImage::new(500, 500);
578                let color = Luma([50u8]);
579                b.iter(|| {
580                    draw_antialiased_line_segment_mut(&mut image, $start, $end, color, interpolate);
581                    test::black_box(&image);
582                });
583            }
584        };
585    }
586
587    bench_antialiased_lines!(
588        bench_draw_antialiased_line_segment_horizontal,
589        (10, 10),
590        (450, 10)
591    );
592
593    bench_antialiased_lines!(
594        bench_draw_antialiased_line_segment_vertical,
595        (10, 10),
596        (10, 450)
597    );
598
599    bench_antialiased_lines!(
600        bench_draw_antialiased_line_segment_diagonal,
601        (10, 10),
602        (450, 450)
603    );
604
605    bench_antialiased_lines!(
606        bench_draw_antialiased_line_segment_shallow,
607        (10, 10),
608        (450, 80)
609    );
610
611    #[test]
612    fn test_draw_line_segment_horizontal_using_bresenham_line_pixel_iter_mut() {
613        let image = GrayImage::from_pixel(5, 5, Luma([1u8]));
614
615        let expected = gray_image!(
616            1, 1, 1, 1, 1;
617            4, 4, 4, 4, 4;
618            1, 1, 1, 1, 1;
619            1, 1, 1, 1, 1;
620            1, 1, 1, 1, 1);
621
622        let mut right = image.clone();
623        {
624            let right_iter =
625                BresenhamLinePixelIterMut::new(&mut right, (-3f32, 1f32), (6f32, 1f32));
626            for p in right_iter {
627                *p = Luma([4u8]);
628            }
629        }
630        assert_pixels_eq!(right, expected);
631
632        let mut left = image.clone();
633        {
634            let left_iter = BresenhamLinePixelIterMut::new(&mut left, (6f32, 1f32), (-3f32, 1f32));
635            for p in left_iter {
636                *p = Luma([4u8]);
637            }
638        }
639        assert_pixels_eq!(left, expected);
640    }
641}
imageproc/drawing/line.rs

imageproc/drawing/
line.rs
