1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

use {Point, sort_x, collect_vec_deque, FloatNum, SignedNum};
use steps::Steps;
use std::mem::swap;
use std::collections::VecDeque;

/// An implementation of [Xiaolin Wu's line algorithm].
///
/// This algorithm works based on floating-points and returns an extra variable for how much a
/// a point is covered, which is useful for anti-aliasing.
/// 
/// Note that due to the implementation, the returned line will always go from left to right. Also
/// see [`xiaolin_wu`] and [`xiaolin_wu_sorted`] for a version that reverses the resulting line in
/// this case.
/// 
/// Example:
/// 
/// ```
/// extern crate line_drawing;
/// use line_drawing::XiaolinWu; 
///
/// fn main() {
///     for ((x, y), value) in XiaolinWu::<f32, i8>::new((0.0, 0.0), (3.0, 6.0)) {
///         print!("(({}, {}), {}), ", x, y, value);
///     }
/// }
/// ```
///
/// ```text
/// ((0, 0), 0.5), ((0, 1), 0.5), ((1, 1), 0.5), ((1, 2), 1), ((1, 3), 0.5), ((2, 3), 0.5), ((2, 4), 1), ((2, 5), 0.5), ((3, 5), 0.5), ((3, 6), 0.5),
/// ```
/// 
/// [Xiaolin Wu's line algorithm]: https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm
/// [`xiaolin_wu`]: fn.xiaolin_wu.html
/// [`xiaolin_wu_sorted`]: fn.xiaolin_wu_sorted.html
pub struct XiaolinWu<I, O> {
    steep: bool,
    gradient: I,
    x: O,
    y: I,
    end_x: O,
    lower: bool
}

impl<I: FloatNum, O: SignedNum> XiaolinWu<I, O> {
    #[inline]
    pub fn new(mut start: Point<I>, mut end: Point<I>) -> XiaolinWu<I, O> {
        let steep = (end.1 - start.1).abs() > (end.0 - start.0).abs();

        if steep {
            start = (start.1, start.0);
            end = (end.1, end.0);
        }

        if start.0 > end.0 {
            swap(&mut start, &mut end);
        }

        let mut gradient = (end.1 - start.1) / (end.0 - start.0);
    
        if gradient == I::zero() {
            gradient = I::one();
        }

        XiaolinWu {
            steep, gradient,
            x: O::cast(start.0.round()),
            y: start.1,
            end_x: O::cast(end.0.round()),
            lower: false
        }
    }

    #[inline]
    pub fn steps(self) -> Steps<(Point<O>, I), XiaolinWu<I, O>> {
        Steps::new(self)
    }
}

impl<I: FloatNum, O: SignedNum> Iterator for XiaolinWu<I, O> {
    type Item = (Point<O>, I);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.x <= self.end_x {
            // get the fractional part of y
            let fpart = self.y - self.y.floor();
            
            // Calculate the integer value of y
            let mut y = O::cast(self.y);
            if self.lower {
                y += O::one();
            }

            // Get the point
            let point = if self.steep {
                (y, self.x)
            } else {
                (self.x, y)
            };

            if self.lower {
                // Return the lower point
                self.lower = false;
                self.x += O::one();
                self.y += self.gradient;
                Some((point, fpart))
            } else {
                if fpart > I::zero() {
                    // Set to return the lower point if the fractional part is > 0
                    self.lower = true;
                } else {
                    // Otherwise move on
                    self.x += O::one();
                    self.y += self.gradient;
                }

                // Return the remainer of the fractional part
                Some((point, I::one() - fpart))
            }
        } else {
            None
        }
    }
}

/// A convenience function to collect the points from [`XiaolinWu`] into a [`Vec`].
/// [`XiaolinWu`]: struct.XiaolinWu.html
/// [`Vec`]: https://doc.rust-lang.org/std/vec/struct.Vec.html
#[inline]
pub fn xiaolin_wu<I: FloatNum, O: SignedNum>(start: Point<I>, end: Point<I>) -> Vec<(Point<O>, I)> {
    XiaolinWu::new(start, end).collect()
}

/// Sorts the points before hand to ensure that the line is symmetrical and collects into a
/// [`VecDeque`].
/// [`VecDeque`]: https://doc.rust-lang.org/nightly/collections/vec_deque/struct.VecDeque.html
#[inline]
pub fn xiaolin_wu_sorted<I: FloatNum, O: SignedNum>(start: Point<I>, end: Point<I>) -> VecDeque<(Point<O>, I)> {
    let (start, end, reordered) = sort_x(start, end);
    collect_vec_deque(XiaolinWu::new(start, end), reordered)
}

#[test] 
fn tests() {
    use fuzzing::reverse_vec_deque;

    assert_eq!(
        xiaolin_wu::<_, i16>((0.0, 0.0), (6.0, 3.0)),
        [((0, 0), 1.0), ((1, 0), 0.5), ((1, 1), 0.5), ((2, 1), 1.0), ((3, 1), 0.5),
         ((3, 2), 0.5), ((4, 2), 1.0), ((5, 2), 0.5), ((5, 3), 0.5), ((6, 3), 1.0)]
    );

    // The algorithm reorders the points to be left-to-right

    assert_eq!(
        xiaolin_wu::<_, i16>((340.5, 290.77), (110.0, 170.0)),
        xiaolin_wu((110.0, 170.0), (340.5, 290.77))
    );

    // sorted_xiaolin_wu should prevent this

    assert_eq!(
        xiaolin_wu_sorted::<_, i16>((340.5, 290.77), (110.0, 170.0)),
        reverse_vec_deque(xiaolin_wu_sorted((110.0, 170.0), (340.5, 290.77)))
    );
}