1 use std::cmp; |
1 use std::cmp; |
|
2 use std::ops::{Add, Sub, Mul, Div, AddAssign, SubAssign, MulAssign, DivAssign}; |
|
3 |
|
4 #[derive(PartialEq, Eq, Clone, Copy, Debug)] |
|
5 pub struct Point { |
|
6 pub x: i32, |
|
7 pub y: i32, |
|
8 } |
|
9 |
|
10 impl Point { |
|
11 #[inline] |
|
12 pub fn new(x: i32, y: i32) -> Self { |
|
13 Self {x, y} |
|
14 } |
|
15 |
|
16 #[inline] |
|
17 pub fn zero() -> Self { |
|
18 Self::new(0, 0) |
|
19 } |
|
20 |
|
21 #[inline] |
|
22 pub fn signum(self) -> Self { |
|
23 Self::new(self.x.signum(), self.y.signum()) |
|
24 } |
|
25 |
|
26 #[inline] |
|
27 pub fn abs(self) -> Self { |
|
28 Self::new(self.x.abs(), self.y.abs()) |
|
29 } |
|
30 |
|
31 #[inline] |
|
32 pub fn dot(self, other: Point) -> i32 { |
|
33 self.x * other.x + self.y * other.y |
|
34 } |
|
35 |
|
36 #[inline] |
|
37 pub fn max_norm(self) -> i32 { |
|
38 std::cmp::max(self.x.abs(), self.y.abs()) |
|
39 } |
|
40 } |
|
41 |
|
42 macro_rules! bin_op_impl { |
|
43 ($op: ty, $name: tt) => { |
|
44 impl $op for Point { |
|
45 type Output = Self; |
|
46 |
|
47 #[inline] |
|
48 fn $name(self, rhs: Self) -> Self::Output { |
|
49 Self::new(self.x.$name(rhs.x), |
|
50 self.y.$name(rhs.y)) |
|
51 } |
|
52 } |
|
53 } |
|
54 } |
|
55 |
|
56 macro_rules! bin_assign_op_impl { |
|
57 ($op: ty, $name: tt) => { |
|
58 impl $op for Point { |
|
59 #[inline] |
|
60 fn $name(&mut self, rhs: Self){ |
|
61 self.x.$name(rhs.x); |
|
62 self.y.$name(rhs.y); |
|
63 } |
|
64 } |
|
65 } |
|
66 } |
|
67 |
|
68 bin_op_impl!(Add, add); |
|
69 bin_op_impl!(Sub, sub); |
|
70 bin_op_impl!(Mul, mul); |
|
71 bin_op_impl!(Div, div); |
|
72 bin_assign_op_impl!(AddAssign, add_assign); |
|
73 bin_assign_op_impl!(SubAssign, sub_assign); |
|
74 bin_assign_op_impl!(MulAssign, mul_assign); |
|
75 bin_assign_op_impl!(DivAssign, div_assign); |
2 |
76 |
3 pub struct LinePoints { |
77 pub struct LinePoints { |
4 e_x: i32, |
78 accumulator: Point, |
5 e_y: i32, |
79 direction: Point, |
6 d_x: i32, |
80 sign: Point, |
7 d_y: i32, |
81 current: Point, |
8 s_x: i32, |
82 total_steps: i32, |
9 s_y: i32, |
83 step: i32, |
10 x: i32, |
|
11 y: i32, |
|
12 d: i32, |
|
13 i: i32, |
|
14 } |
84 } |
15 |
85 |
16 impl LinePoints { |
86 impl LinePoints { |
17 pub fn new(x1: i32, y1: i32, x2: i32, y2: i32) -> Self { |
87 pub fn new(from: Point, to: Point) -> Self { |
18 let mut d_x: i32 = x2 - x1; |
88 let dir = to - from; |
19 let mut d_y: i32 = y2 - y1; |
|
20 let s_x: i32; |
|
21 let s_y: i32; |
|
22 |
|
23 if d_x > 0 { |
|
24 s_x = 1; |
|
25 } else if d_x < 0 { |
|
26 s_x = -1; |
|
27 d_x = -d_x; |
|
28 } else { |
|
29 s_x = d_x; |
|
30 } |
|
31 |
|
32 if d_y > 0 { |
|
33 s_y = 1; |
|
34 } else if d_y < 0 { |
|
35 s_y = -1; |
|
36 d_y = -d_y; |
|
37 } else { |
|
38 s_y = d_y; |
|
39 } |
|
40 |
89 |
41 Self { |
90 Self { |
42 e_x: 0, |
91 accumulator: Point::zero(), |
43 e_y: 0, |
92 direction: dir.abs(), |
44 d_x, |
93 sign: dir.signum(), |
45 d_y, |
94 current: from, |
46 s_x, |
95 total_steps: dir.max_norm(), |
47 s_y, |
96 step: 0, |
48 x: x1, |
|
49 y: y1, |
|
50 d: cmp::max(d_x, d_y), |
|
51 i: 0, |
|
52 } |
97 } |
53 } |
98 } |
54 } |
99 } |
55 |
100 |
56 impl Iterator for LinePoints { |
101 impl Iterator for LinePoints { |
57 type Item = (i32, i32); |
102 type Item = Point; |
58 |
103 |
59 fn next(&mut self) -> Option<Self::Item> { |
104 fn next(&mut self) -> Option<Self::Item> { |
60 if self.i <= self.d { |
105 if self.step <= self.total_steps { |
61 self.e_x += self.d_x; |
106 self.accumulator += self.direction; |
62 self.e_y += self.d_y; |
|
63 |
107 |
64 if self.e_x > self.d { |
108 if self.accumulator.x > self.total_steps { |
65 self.e_x -= self.d; |
109 self.accumulator.x -= self.total_steps; |
66 self.x += self.s_x; |
110 self.current.x += self.sign.x; |
67 } |
111 } |
68 if self.e_y > self.d { |
112 if self.accumulator.y > self.total_steps { |
69 self.e_y -= self.d; |
113 self.accumulator.y -= self.total_steps; |
70 self.y += self.s_y; |
114 self.current.y += self.sign.y; |
71 } |
115 } |
72 |
116 |
73 self.i += 1; |
117 self.step += 1; |
74 |
118 |
75 Some((self.x, self.y)) |
119 Some(self.current) |
76 } else { |
120 } else { |
77 None |
121 None |
78 } |
122 } |
79 } |
123 } |
80 } |
124 } |
81 |
125 |
82 #[cfg(test)] |
126 #[cfg(test)] |
83 mod tests { |
127 mod tests { |
84 use super::*; |
128 use super::*; |
85 |
129 |
|
130 fn get_points(coords: &[(i32, i32)]) -> Vec<Point> { |
|
131 coords.iter().map(|(x, y)| Point::new(*x, *y)).collect() |
|
132 } |
|
133 |
86 #[test] |
134 #[test] |
87 fn basic() { |
135 fn basic() { |
88 let v = vec![(0, 0), (1, 1), (2, 2), (3, 3), (123, 456)]; |
136 let line = LinePoints::new(Point::new(0, 0), Point::new(3, 3)); |
|
137 let v = get_points(&[(0, 0), (1, 1), (2, 2), (3, 3), (123, 456)]); |
89 |
138 |
90 for (&a, b) in v.iter().zip(LinePoints::new(0, 0, 3, 3)) { |
139 for (&a, b) in v.iter().zip(line) { |
|
140 assert_eq!(a, b); |
|
141 } |
|
142 } |
|
143 |
|
144 #[test] |
|
145 fn skewed() { |
|
146 let line = LinePoints::new(Point::new(0, 0), Point::new(5, -7)); |
|
147 let v = get_points(&[(0, 0), (1, -1), (2, -2), (2, -3), (3, -4), (4, -5), (4, -6), (5, -7)]); |
|
148 |
|
149 for (&a, b) in v.iter().zip(line) { |
91 assert_eq!(a, b); |
150 assert_eq!(a, b); |
92 } |
151 } |
93 } |
152 } |
94 } |
153 } |