author  alfadur 
Tue, 06 Nov 2018 23:45:54 +0300  
changeset 14149  8e2e98760003 
parent 14148  d3c9025abd13 
child 14150  6205a5230d23 
permissions  rwrr 
13936  1 
extern crate integral_geometry; 
13917  2 
extern crate vec2d; 
3 

14144  4 
use std::{ 
5 
cmp, 

6 
ops::Index 

7 
}; 

13917  8 

14137
3119d665d3c6
collapse rectangle types back together with consistent usage of size
alfadur
parents:
14135
diff
changeset

9 
use integral_geometry::{ArcPoints, EquidistantPoints, Line, Point, Rect, Size, SizeMask}; 
13938
1fa905aa4cdb
move point struct into integralgeometry and use it to refactor a bit
alfadur
parents:
13936
diff
changeset

10 

13917  11 
pub struct Land2D<T> { 
12 
pixels: vec2d::Vec2D<T>, 

14137
3119d665d3c6
collapse rectangle types back together with consistent usage of size
alfadur
parents:
14135
diff
changeset

13 
play_box: Rect, 
14078  14 
mask: SizeMask, 
13917  15 
} 
16 

13931  17 
impl<T: Copy + PartialEq> Land2D<T> { 
14052  18 
pub fn new(play_size: Size, fill_value: T) > Self { 
19 
let real_size = play_size.next_power_of_two(); 

14078  20 
let top_left = Point::new( 
14101  21 
((real_size.width  play_size.width) / 2) as i32, 
14078  22 
(real_size.height  play_size.height) as i32, 
23 
); 

14137
3119d665d3c6
collapse rectangle types back together with consistent usage of size
alfadur
parents:
14135
diff
changeset

24 
let play_box = Rect::from_size(top_left, play_size); 
13917  25 
Self { 
14078  26 
play_box, 
14052  27 
pixels: vec2d::Vec2D::new(real_size, fill_value), 
14078  28 
mask: real_size.to_mask(), 
13917  29 
} 
30 
} 

31 

14121  32 
pub fn raw_pixels(&self) > &[T] { 
33 
&self.pixels.raw_data() 

34 
} 

35 

13917  36 
#[inline] 
13924  37 
pub fn width(&self) > usize { 
38 
self.pixels.width() 

39 
} 

40 

41 
#[inline] 

42 
pub fn height(&self) > usize { 

43 
self.pixels.height() 

44 
} 

45 

46 
#[inline] 

14052  47 
pub fn size(&self) > Size { 
48 
self.pixels.size() 

49 
} 

50 

51 
#[inline] 

14050
4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

52 
pub fn play_width(&self) > usize { 
14135
7f5a591e1c43
separate rectangle types based on right/bottom edge inclusivity
alfadur
parents:
14121
diff
changeset

53 
self.play_box.width() 
14050
4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

54 
} 
4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

55 

4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

56 
#[inline] 
4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

57 
pub fn play_height(&self) > usize { 
14135
7f5a591e1c43
separate rectangle types based on right/bottom edge inclusivity
alfadur
parents:
14121
diff
changeset

58 
self.play_box.height() 
14052  59 
} 
60 

61 
#[inline] 

62 
pub fn play_size(&self) > Size { 

14135
7f5a591e1c43
separate rectangle types based on right/bottom edge inclusivity
alfadur
parents:
14121
diff
changeset

63 
self.play_box.size() 
14050
4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

64 
} 
4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

65 

4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

66 
#[inline] 
14137
3119d665d3c6
collapse rectangle types back together with consistent usage of size
alfadur
parents:
14135
diff
changeset

67 
pub fn play_box(&self) > Rect { 
14078  68 
self.play_box 
69 
} 

70 

71 
#[inline] 

13931  72 
pub fn is_valid_x(&self, x: i32) > bool { 
14032  73 
self.mask.contains_x(x as usize) 
13931  74 
} 
75 

76 
#[inline] 

77 
pub fn is_valid_y(&self, y: i32) > bool { 

14032  78 
self.mask.contains_y(y as usize) 
13931  79 
} 
80 

81 
#[inline] 

13924  82 
pub fn is_valid_coordinate(&self, x: i32, y: i32) > bool { 
13931  83 
self.is_valid_x(x) && self.is_valid_y(y) 
13917  84 
} 
85 

86 
#[inline] 

14030  87 
pub fn rows(&self) > impl Iterator<Item = &[T]> { 
88 
self.pixels.rows() 

89 
} 

90 

91 
#[inline] 

13940
1c30793b1cea
put back land2d.map accidentally replaced by testing code
alfadur
parents:
13938
diff
changeset

92 
pub fn map<U: Default, F: FnOnce(&mut T) > U>(&mut self, y: i32, x: i32, f: F) > U { 
13917  93 
if self.is_valid_coordinate(x, y) { 
13934
9c112f2ae02d
Raise levels of abstraction to implement draw_thick_line() avoiding code duplication
unc0rr
parents:
13931
diff
changeset

94 
unsafe { 
9c112f2ae02d
Raise levels of abstraction to implement draw_thick_line() avoiding code duplication
unc0rr
parents:
13931
diff
changeset

95 
// hey, I just checked that coordinates are valid! 
13940
1c30793b1cea
put back land2d.map accidentally replaced by testing code
alfadur
parents:
13938
diff
changeset

96 
f(self.pixels.get_unchecked_mut(y as usize, x as usize)) 
13931  97 
} 
13934
9c112f2ae02d
Raise levels of abstraction to implement draw_thick_line() avoiding code duplication
unc0rr
parents:
13931
diff
changeset

98 
} else { 
13940
1c30793b1cea
put back land2d.map accidentally replaced by testing code
alfadur
parents:
13938
diff
changeset

99 
U::default() 
13917  100 
} 
101 
} 

102 

13944
4162ea9ae333
Use integralgeometry iterators to implement Land2D::draw_thick_line, remove no longer unused functions from Land2D
unc0rr
parents:
13943
diff
changeset

103 
#[inline] 
4162ea9ae333
Use integralgeometry iterators to implement Land2D::draw_thick_line, remove no longer unused functions from Land2D
unc0rr
parents:
13943
diff
changeset

104 
pub fn map_point<U: Default, F: FnOnce(&mut T) > U>(&mut self, point: Point, f: F) > U { 
4162ea9ae333
Use integralgeometry iterators to implement Land2D::draw_thick_line, remove no longer unused functions from Land2D
unc0rr
parents:
13943
diff
changeset

105 
self.map(point.y, point.x, f) 
13934
9c112f2ae02d
Raise levels of abstraction to implement draw_thick_line() avoiding code duplication
unc0rr
parents:
13931
diff
changeset

106 
} 
9c112f2ae02d
Raise levels of abstraction to implement draw_thick_line() avoiding code duplication
unc0rr
parents:
13931
diff
changeset

107 

13938
1fa905aa4cdb
move point struct into integralgeometry and use it to refactor a bit
alfadur
parents:
13936
diff
changeset

108 
pub fn fill_from_iter<I>(&mut self, i: I, value: T) > usize 
13943
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

109 
where 
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

110 
I: std::iter::Iterator<Item = Point>, 
13938
1fa905aa4cdb
move point struct into integralgeometry and use it to refactor a bit
alfadur
parents:
13936
diff
changeset

111 
{ 
13943
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

112 
i.map(p { 
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

113 
self.map(p.y, p.x, v { 
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

114 
*v = value; 
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

115 
1 
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

116 
}) 
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

117 
}).count() 
13938
1fa905aa4cdb
move point struct into integralgeometry and use it to refactor a bit
alfadur
parents:
13936
diff
changeset

118 
} 
1fa905aa4cdb
move point struct into integralgeometry and use it to refactor a bit
alfadur
parents:
13936
diff
changeset

119 

14076
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14052
diff
changeset

120 
pub fn draw_line(&mut self, line: Line, value: T) > usize { 
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14052
diff
changeset

121 
self.fill_from_iter(line.into_iter(), value) 
13917  122 
} 
13924  123 

13948  124 
pub fn fill(&mut self, start_point: Point, border_value: T, fill_value: T) { 
125 
debug_assert!(self.is_valid_coordinate(start_point.x  1, start_point.y)); 

126 
debug_assert!(self.is_valid_coordinate(start_point.x, start_point.y)); 

13924  127 

14148  128 
let mask = self.mask; 
129 
let width = self.width(); 

130 

13924  131 
let mut stack: Vec<(usize, usize, usize, isize)> = Vec::new(); 
14148  132 
fn push( 
133 
mask: SizeMask, 

13924  134 
stack: &mut Vec<(usize, usize, usize, isize)>, 
135 
xl: usize, 

136 
xr: usize, 

137 
y: usize, 

138 
dir: isize, 

139 
) { 

140 
let yd = y as isize + dir; 

14148  141 
if mask.contains_y(yd as usize) { 
13924  142 
stack.push((xl, xr, yd as usize, dir)); 
143 
} 

144 
}; 

145 

13948  146 
let start_x_l = (start_point.x  1) as usize; 
147 
let start_x_r = start_point.x as usize; 

14148  148 
for dir in [1, 1].iter().cloned() { 
149 
push(mask, &mut stack, start_x_l, start_x_r, start_point.y as usize, dir); 

150 
} 

13924  151 

14148  152 
while let Some((mut xl, mut xr, y, dir)) = stack.pop() { 
153 
let row = &mut self.pixels[y][..]; 

14149
8e2e98760003
a bit more simplification without an apparent performance gain
alfadur
parents:
14148
diff
changeset

154 
while xl > 0 && row[xl] != border_value && row[xl] != fill_value 
13951  155 
{ 
156 
xl = 1; 

157 
} 

13924  158 

14149
8e2e98760003
a bit more simplification without an apparent performance gain
alfadur
parents:
14148
diff
changeset

159 
while xr < width  1 && row[xr] != border_value && row[xr] != fill_value 
13951  160 
{ 
161 
xr += 1; 

162 
} 

13924  163 

13951  164 
while xl < xr { 
14148  165 
while xl <= xr && (row[xl] == border_value  row[xl] == fill_value) 
13951  166 
{ 
167 
xl += 1; 

168 
} 

13924  169 

14148  170 
let x = xl; 
13924  171 

14149
8e2e98760003
a bit more simplification without an apparent performance gain
alfadur
parents:
14148
diff
changeset

172 
while xl <= xr && row[xl] != border_value && row[xl] != fill_value 
13951  173 
{ 
14148  174 
row[xl] = fill_value; 
13951  175 
xl += 1; 
176 
} 

13924  177 

13951  178 
if x < xl { 
14148  179 
push(mask, &mut stack, x, xl  1, y, dir); 
180 
push(mask, &mut stack, x, xl  1, y, dir); 

13924  181 
} 
182 
} 

183 
} 

184 
} 

13931  185 

186 
#[inline] 

187 
fn fill_circle_line<F: Fn(&mut T) > usize>( 

188 
&mut self, 

189 
y: i32, 

190 
x_from: i32, 

191 
x_to: i32, 

192 
f: &F, 

193 
) > usize { 

194 
let mut result = 0; 

195 

196 
if self.is_valid_y(y) { 

197 
for i in cmp::min(x_from, 0) as usize..cmp::max(x_to as usize, self.width()  1) { 

13934
9c112f2ae02d
Raise levels of abstraction to implement draw_thick_line() avoiding code duplication
unc0rr
parents:
13931
diff
changeset

198 
unsafe { 
9c112f2ae02d
Raise levels of abstraction to implement draw_thick_line() avoiding code duplication
unc0rr
parents:
13931
diff
changeset

199 
// coordinates are valid at this point 
13931  200 
result += f(self.pixels.get_unchecked_mut(y as usize, i)); 
201 
} 

202 
} 

203 
} 

204 

205 
result 

206 
} 

207 

208 
#[inline] 

209 
fn fill_circle_lines<F: Fn(&mut T) > usize>( 

210 
&mut self, 

211 
x: i32, 

212 
y: i32, 

213 
dx: i32, 

214 
dy: i32, 

215 
f: &F, 

216 
) > usize { 

217 
self.fill_circle_line(y + dy, x  dx, x + dx, f) 

218 
+ self.fill_circle_line(y  dy, x  dx, x + dx, f) 

219 
+ self.fill_circle_line(y + dx, x  dy, x + dy, f) 

220 
+ self.fill_circle_line(y  dx, x  dy, x + dy, f) 

221 
} 

222 

223 
pub fn change_round<F: Fn(&mut T) > usize>( 

224 
&mut self, 

225 
x: i32, 

226 
y: i32, 

227 
radius: i32, 

228 
f: F, 

229 
) > usize { 

13943
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

230 
ArcPoints::new(radius) 
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

231 
.map(&mut p: Point self.fill_circle_lines(x, y, p.x, p.y, &f)) 
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

232 
.sum() 
13934
9c112f2ae02d
Raise levels of abstraction to implement draw_thick_line() avoiding code duplication
unc0rr
parents:
13931
diff
changeset

233 
} 
13931  234 

14031  235 
fn fill_row(&mut self, center: Point, offset: Point, value: T) > usize { 
236 
let row_index = center.y + offset.y; 

237 
if self.is_valid_y(row_index) { 

238 
let from_x = cmp::max(0, center.x  offset.x) as usize; 

239 
let to_x = cmp::min(self.width()  1, (center.x + offset.x) as usize); 

240 
self.pixels[row_index as usize][from_x..=to_x] 

14078  241 
.iter_mut() 
242 
.for_each(v *v = value); 

14031  243 
to_x  from_x + 1 
244 
} else { 

245 
0 

246 
} 

247 
} 

248 

249 
pub fn fill_circle(&mut self, center: Point, radius: i32, value: T) > usize { 

14078  250 
let transforms = [[0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 0, 1]]; 
251 
ArcPoints::new(radius) 

252 
.map(vector { 

253 
transforms 

254 
.iter() 

255 
.map(m self.fill_row(center, vector.transform(m), value)) 

256 
.sum::<usize>() 

257 
}).sum() 

14031  258 
} 
259 

14076
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14052
diff
changeset

260 
pub fn draw_thick_line(&mut self, line: Line, radius: i32, value: T) > usize { 
13944
4162ea9ae333
Use integralgeometry iterators to implement Land2D::draw_thick_line, remove no longer unused functions from Land2D
unc0rr
parents:
13943
diff
changeset

261 
let mut result = 0; 
13931  262 

13949
a1895019bb94
change draw_thick_line iteration order to benchmark winner
alfadur
parents:
13948
diff
changeset

263 
for vector in ArcPoints::new(radius) { 
a1895019bb94
change draw_thick_line iteration order to benchmark winner
alfadur
parents:
13948
diff
changeset

264 
for delta in EquidistantPoints::new(vector) { 
14076
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14052
diff
changeset

265 
for point in line.into_iter() { 
13946  266 
self.map_point(point + delta, p { 
267 
if *p != value { 

268 
*p = value; 

269 
result += 1; 

270 
} 

271 
}) 

13944
4162ea9ae333
Use integralgeometry iterators to implement Land2D::draw_thick_line, remove no longer unused functions from Land2D
unc0rr
parents:
13943
diff
changeset

272 
} 
13943
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

273 
} 
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

274 
} 
a325ed57ebfe
Don't generate unnecessary duplication in case of equal coordinates
unc0rr
parents:
13940
diff
changeset

275 

13944
4162ea9ae333
Use integralgeometry iterators to implement Land2D::draw_thick_line, remove no longer unused functions from Land2D
unc0rr
parents:
13943
diff
changeset

276 
result 
13934
9c112f2ae02d
Raise levels of abstraction to implement draw_thick_line() avoiding code duplication
unc0rr
parents:
13931
diff
changeset

277 
} 
13917  278 
} 
279 

14144  280 
impl<T> Index<usize> for Land2D<T> { 
281 
type Output = [T]; 

282 
#[inline] 

283 
fn index(&self, row: usize) > &[T] { 

284 
&self.pixels[row] 

285 
} 

286 
} 

287 

13917  288 
#[cfg(test)] 
289 
mod tests { 

290 
use super::*; 

291 

292 
#[test] 

293 
fn basics() { 

14052  294 
let l: Land2D<u8> = Land2D::new(Size::new(30, 50), 0); 
14050
4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

295 

4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

296 
assert_eq!(l.play_width(), 30); 
4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

297 
assert_eq!(l.play_height(), 50); 
4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

298 
assert_eq!(l.width(), 32); 
4b40bdd214df
Use next_power_of_two() just like hedgewars engine does, expose original and real dimensions
unc0rr
parents:
13951
diff
changeset

299 
assert_eq!(l.height(), 64); 
13917  300 

301 
assert!(l.is_valid_coordinate(0, 0)); 

302 
assert!(!l.is_valid_coordinate(1, 1)); 

303 

304 
assert!(l.is_valid_coordinate(31, 63)); 

305 
assert!(!l.is_valid_coordinate(32, 63)); 

306 
assert!(!l.is_valid_coordinate(31, 64)); 

307 
} 

308 

13924  309 
#[test] 
310 
fn fill() { 

14032  311 
let mut l: Land2D<u8> = Land2D::new(Size::square(128), 0); 
13924  312 

14076
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14052
diff
changeset

313 
l.draw_line(Line::new(Point::new(0, 0), Point::new(32, 96)), 1); 
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14052
diff
changeset

314 
l.draw_line(Line::new(Point::new(32, 96), Point::new(64, 32)), 1); 
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14052
diff
changeset

315 
l.draw_line(Line::new(Point::new(64, 32), Point::new(96, 80)), 1); 
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14052
diff
changeset

316 
l.draw_line(Line::new(Point::new(96, 80), Point::new(128, 0)), 1); 
13924  317 

14076
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14052
diff
changeset

318 
l.draw_line(Line::new(Point::new(0, 128), Point::new(64, 96)), 1); 
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14052
diff
changeset

319 
l.draw_line(Line::new(Point::new(128, 128), Point::new(64, 96)), 1); 
13924  320 

13948  321 
l.fill(Point::new(32, 32), 1, 2); 
322 
l.fill(Point::new(16, 96), 1, 3); 

323 
l.fill(Point::new(60, 100), 1, 4); 

13924  324 

325 
assert_eq!(l.pixels[0][0], 1); 

326 
assert_eq!(l.pixels[96][64], 1); 

327 

328 
assert_eq!(l.pixels[40][32], 2); 

329 
assert_eq!(l.pixels[40][96], 2); 

330 
assert_eq!(l.pixels[5][0], 3); 

331 
assert_eq!(l.pixels[120][0], 3); 

332 
assert_eq!(l.pixels[5][127], 3); 

333 
assert_eq!(l.pixels[120][127], 3); 

334 
assert_eq!(l.pixels[35][64], 3); 

335 
assert_eq!(l.pixels[120][20], 4); 

336 
assert_eq!(l.pixels[120][100], 4); 

337 
assert_eq!(l.pixels[100][64], 4); 

338 
} 

13917  339 
} 