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

use {FloatNum, Point, SignedNum};
use octant::Octant;
use steps::Steps;

/// An implementation of the [mid-point line drawing algorithm].
///
/// The biggest difference between this algorithm and [`Bresenham`] is that it uses floating-point points.
///
/// Example:
///
/// ```
/// extern crate line_drawing;
/// use line_drawing::Midpoint;
///
/// fn main() {
///     for (x, y) in Midpoint::<f32, i8>::new((0.2, 0.02), (2.8, 7.7)) {
///         print!("({}, {}), ", x, y);
///     }
/// }
/// ```
///
/// ```text
/// (0, 0), (1, 1), (1, 2), (1, 3), (2, 4), (2, 5), (2, 6), (3, 7), (3, 8),
/// ```
///
/// [mid-point line drawing algorithm]: http://www.mat.univie.ac.at/~kriegl/Skripten/CG/node25.html
/// [`Bresenham`]: struct.bresenham.html
pub struct Midpoint<I, O> {
    octant: Octant,
    point: Point<O>,
    a: I,
    b: I,
    k: I,
    end_x: O,
}

impl<I: FloatNum, O: SignedNum> Midpoint<I, O> {
    #[inline]
    pub fn new(start: Point<I>, end: Point<I>) -> Self {
        // Get the octant to use
        let octant = Octant::new(start, end);

        // Convert the points into the octant versions
        let start = octant.to(start);
        let end = octant.to(end);

        // Initialise the variables

        let a = -(end.1 - start.1);
        let b = end.0 - start.0;
        let c = start.0 * end.1 - end.0 * start.1;

        Self {
            octant,
            a,
            b,
            point: (O::cast(start.0.round()), O::cast(start.1.round())),
            k: a * (start.0.round() + I::one()) + b * (start.1.round() + I::cast(0.5)) + c,
            end_x: O::cast(end.0.round()),
        }
    }

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

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

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.point.0 <= self.end_x {
            let point = self.octant.from(self.point);

            // Take an N step
            if self.k <= I::zero() {
                self.k += self.b;
                self.point.1 += O::one();
            }

            // Take an E step
            self.k += self.a;
            self.point.0 += O::one();

            Some(point)
        } else {
            None
        }
    }
}

#[test]
fn tests() {
    let midpoint = |a, b| Midpoint::new(a, b).collect::<Vec<_>>();

    assert_eq!(
        midpoint((0.0, 0.0), (-5.0, -5.0)),
        [(0, 0), (-1, -1), (-2, -2), (-3, -3), (-4, -4), (-5, -5)]
    );

    assert_eq!(
        midpoint((0.0, 0.0), (6.0, 3.0)),
        [(0, 0), (1, 1), (2, 1), (3, 2), (4, 2), (5, 3), (6, 3)]
    );
}