author | alfadur |
Sat, 03 Nov 2018 02:21:45 +0300 | |
changeset 14111 | 5c1ce63114a5 |
parent 14110 | 7e25f4800af8 |
child 14112 | 6a3bcb7c2981 |
permissions | -rw-r--r-- |
14074 | 1 |
use itertools::Itertools; |
14086 | 2 |
use std::cmp::min; |
14074 | 3 |
|
14083 | 4 |
use integral_geometry::{Line, Point, Rect, Size}; |
14074 | 5 |
use land2d::Land2D; |
6 |
||
7 |
use outline_template::OutlineTemplate; |
|
8 |
||
9 |
pub struct OutlinePoints { |
|
10 |
pub islands: Vec<Vec<Point>>, |
|
11 |
pub fill_points: Vec<Point>, |
|
12 |
pub size: Size, |
|
14083 | 13 |
pub play_box: Rect, |
14074 | 14 |
} |
15 |
||
16 |
impl OutlinePoints { |
|
17 |
pub fn from_outline_template<I: Iterator<Item = u32>>( |
|
18 |
outline_template: &OutlineTemplate, |
|
14083 | 19 |
play_box: Rect, |
20 |
size: Size, |
|
14074 | 21 |
random_numbers: &mut I, |
22 |
) -> Self { |
|
23 |
Self { |
|
14083 | 24 |
play_box, |
25 |
size, |
|
14074 | 26 |
islands: outline_template |
27 |
.islands |
|
28 |
.iter() |
|
29 |
.map(|i| { |
|
30 |
i.iter() |
|
31 |
.zip(random_numbers.tuples()) |
|
32 |
.map(|(rect, (rnd_a, rnd_b))| { |
|
14083 | 33 |
rect.top_left() |
34 |
+ Point::new( |
|
35 |
(rnd_a % rect.width) as i32, |
|
36 |
(rnd_b % rect.height) as i32, |
|
37 |
) |
|
38 |
+ play_box.top_left() |
|
14074 | 39 |
}).collect() |
40 |
}).collect(), |
|
41 |
fill_points: outline_template.fill_points.clone(), |
|
42 |
} |
|
43 |
} |
|
44 |
||
45 |
pub fn total_len(&self) -> usize { |
|
46 |
self.islands.iter().map(|i| i.len()).sum::<usize>() + self.fill_points.len() |
|
47 |
} |
|
48 |
||
14105 | 49 |
pub fn iter(&self) -> impl Iterator<Item = &Point> { |
50 |
self.islands |
|
51 |
.iter() |
|
52 |
.flat_map(|i| i.iter()) |
|
53 |
.chain(self.fill_points.iter()) |
|
54 |
} |
|
55 |
||
14074 | 56 |
pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut Point> { |
57 |
self.islands |
|
58 |
.iter_mut() |
|
59 |
.flat_map(|i| i.iter_mut()) |
|
60 |
.chain(self.fill_points.iter_mut()) |
|
61 |
} |
|
62 |
||
63 |
fn divide_edge<I: Iterator<Item = u32>>( |
|
64 |
&self, |
|
14081
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
65 |
segment: Line, |
14105 | 66 |
distance_divisor: u32, |
14074 | 67 |
random_numbers: &mut I, |
68 |
) -> Option<Point> { |
|
14105 | 69 |
#[inline] |
70 |
fn intersect(p: &Point, m: &Point, p1: &Point, p2: &Point) -> bool { |
|
71 |
let t1 = (m.x - p1.x) * p.y - p.x * (m.y - p1.y); |
|
72 |
let t2 = (m.x - p2.x) * p.y - p.x * (m.y - p2.y); |
|
73 |
||
74 |
(t1 > 0) != (t2 > 0) |
|
75 |
} |
|
76 |
||
77 |
#[inline] |
|
78 |
fn solve_intersection(p: &Point, m: &Point, s: &Point, e: &Point) -> Option<(i32, u32)> { |
|
79 |
let f = *e - *s; |
|
80 |
let aqpb = (p.x * f.y - f.x * p.y) as i64; |
|
81 |
||
82 |
if aqpb != 0 { |
|
83 |
let iy = ((((s.x - m.x) as i64 * p.y as i64 + m.y as i64 * p.x as i64) |
|
84 |
* f.y as i64 |
|
85 |
- s.y as i64 * f.x as i64 * p.y as i64) |
|
86 |
/ aqpb) as i32; |
|
87 |
let ix = if p.y.abs() > f.y.abs() { |
|
88 |
(iy - m.y) * p.x / p.y + m.x |
|
89 |
} else { |
|
90 |
(iy - s.y) * f.x / f.y + s.x |
|
91 |
}; |
|
92 |
||
93 |
let intersection_point = Point::new(ix, iy); |
|
94 |
let diff_point = *m - intersection_point; |
|
95 |
let d = diff_point.integral_norm(); |
|
96 |
let t = p.y * diff_point.y + p.x * diff_point.x; |
|
97 |
||
98 |
Some((t, d)) |
|
99 |
} else { |
|
100 |
None |
|
101 |
} |
|
102 |
} |
|
103 |
||
14086 | 104 |
let min_distance = 40; |
105 |
// new point should fall inside this box |
|
106 |
let map_box = self.play_box.with_margin(min_distance); |
|
107 |
||
14111 | 108 |
let p = -segment.scaled_normal(); |
14086 | 109 |
let mid_point = segment.center(); |
110 |
||
14110 | 111 |
if (p.integral_norm() < min_distance as u32 * 3) || !map_box.contains_inside(mid_point) { |
14086 | 112 |
return None; |
113 |
} |
|
114 |
||
115 |
let full_box = Rect::from_size(Point::zero(), self.size).with_margin(min_distance); |
|
116 |
||
117 |
let mut dist_left = (self.size.width + self.size.height) as u32; |
|
118 |
let mut dist_right = dist_left; |
|
119 |
||
120 |
// find distances to map borders |
|
121 |
if p.x != 0 { |
|
122 |
// check against left border |
|
123 |
let iyl = (map_box.left() - mid_point.x) * p.y / p.x + mid_point.y; |
|
124 |
let dl = Point::new(mid_point.x - map_box.left(), mid_point.y - iyl).integral_norm(); |
|
125 |
let t = p.x * (mid_point.x - full_box.left()) + p.y * (mid_point.y - iyl); |
|
126 |
||
127 |
if t > 0 { |
|
128 |
dist_left = dl; |
|
129 |
} else { |
|
130 |
dist_right = dl; |
|
131 |
} |
|
132 |
||
133 |
// right border |
|
134 |
let iyr = (map_box.right() - mid_point.x) * p.y / p.x + mid_point.y; |
|
135 |
let dr = Point::new(mid_point.x - full_box.right(), mid_point.y - iyr).integral_norm(); |
|
136 |
||
137 |
if t > 0 { |
|
138 |
dist_right = dr; |
|
139 |
} else { |
|
140 |
dist_left = dr; |
|
141 |
} |
|
142 |
} |
|
143 |
||
144 |
if p.y != 0 { |
|
145 |
// top border |
|
146 |
let ixl = (map_box.top() - mid_point.y) * p.x / p.y + mid_point.x; |
|
147 |
let dl = Point::new(mid_point.y - map_box.top(), mid_point.x - ixl).integral_norm(); |
|
148 |
let t = p.y * (mid_point.y - full_box.top()) + p.x * (mid_point.x - ixl); |
|
149 |
||
150 |
if t > 0 { |
|
151 |
dist_left = min(dist_left, dl); |
|
152 |
} else { |
|
153 |
dist_right = min(dist_right, dl); |
|
154 |
} |
|
155 |
||
156 |
// bottom border |
|
157 |
let ixr = (map_box.bottom() - mid_point.y) * p.x / p.y + mid_point.x; |
|
158 |
let dr = Point::new(mid_point.y - full_box.bottom(), mid_point.x - ixr).integral_norm(); |
|
159 |
||
160 |
if t > 0 { |
|
161 |
dist_right = min(dist_right, dr); |
|
162 |
} else { |
|
163 |
dist_left = min(dist_left, dr); |
|
164 |
} |
|
165 |
} |
|
166 |
||
167 |
// now go through all other segments |
|
14105 | 168 |
for s in self.segments_iter() { |
169 |
if s != segment { |
|
170 |
if intersect(&p, &mid_point, &s.start, &s.end) { |
|
171 |
if let Some((t, d)) = solve_intersection(&p, &mid_point, &s.start, &s.end) { |
|
172 |
if t > 0 { |
|
173 |
dist_left = min(d, dist_left); |
|
174 |
} else { |
|
175 |
dist_right = min(d, dist_right); |
|
176 |
} |
|
177 |
} |
|
178 |
} |
|
179 |
} |
|
180 |
} |
|
14086 | 181 |
|
14105 | 182 |
// go through all points, including fill points |
183 |
for pi in self.iter() { |
|
184 |
if *pi != segment.start && *pi != segment.end { |
|
185 |
if intersect(&p, &pi, &segment.start, &segment.end) { |
|
186 |
// ray from segment.start |
|
187 |
if let Some((t, d)) = solve_intersection(&p, &mid_point, &segment.start, &pi) { |
|
188 |
if t > 0 { |
|
189 |
dist_left = min(d, dist_left); |
|
190 |
} else { |
|
191 |
dist_right = min(d, dist_right); |
|
192 |
} |
|
193 |
} |
|
194 |
||
195 |
// ray from segment.end |
|
196 |
if let Some((t, d)) = solve_intersection(&p, &mid_point, &segment.end, &pi) { |
|
197 |
if t > 0 { |
|
198 |
dist_left = min(d, dist_left); |
|
199 |
} else { |
|
200 |
dist_right = min(d, dist_right); |
|
201 |
} |
|
202 |
} |
|
203 |
} |
|
204 |
} |
|
205 |
} |
|
206 |
||
207 |
let max_dist = p.integral_norm() * 100 / distance_divisor; |
|
208 |
dist_left = min(dist_left, max_dist); |
|
209 |
dist_right = min(dist_right, max_dist); |
|
210 |
||
211 |
if dist_right + dist_left < min_distance as u32 * 2 + 10 { |
|
212 |
// limits are too narrow, just divide |
|
213 |
Some(mid_point) |
|
214 |
} else { |
|
215 |
// select distance within [-dist_left; dist_right], keeping min_distance in mind |
|
216 |
let d = -(dist_left as i32) |
|
217 |
+ min_distance |
|
218 |
+ random_numbers.next().unwrap() as i32 |
|
219 |
% (dist_right as i32 + dist_left as i32 - min_distance * 2); |
|
220 |
||
221 |
Some(Point::new( |
|
222 |
mid_point.x + p.x * d / distance_divisor as i32, |
|
223 |
mid_point.y + p.y * d / distance_divisor as i32, |
|
224 |
)) |
|
225 |
} |
|
14074 | 226 |
} |
227 |
||
14105 | 228 |
fn divide_edges<I: Iterator<Item = u32>>( |
229 |
&mut self, |
|
230 |
distance_divisor: u32, |
|
231 |
random_numbers: &mut I, |
|
232 |
) { |
|
14074 | 233 |
for is in 0..self.islands.len() { |
234 |
let mut i = 0; |
|
14081
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
235 |
let mut segment; |
14074 | 236 |
|
237 |
loop { |
|
238 |
{ |
|
239 |
let island = &self.islands[is]; |
|
14081
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
240 |
let mut end_point; |
14074 | 241 |
if i < island.len() { |
242 |
end_point = if i + 1 < island.len() { |
|
243 |
island[i + 1] |
|
244 |
} else { |
|
245 |
island[0] |
|
246 |
}; |
|
247 |
} else { |
|
14081
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
248 |
break; |
14074 | 249 |
} |
14081
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
250 |
|
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
251 |
segment = Line::new(island[i], end_point); |
14074 | 252 |
} |
253 |
||
14105 | 254 |
if let Some(new_point) = self.divide_edge(segment, distance_divisor, random_numbers) |
255 |
{ |
|
14074 | 256 |
self.islands[is].insert(i + 1, new_point); |
257 |
i += 2; |
|
258 |
} else { |
|
259 |
i += 1; |
|
260 |
} |
|
261 |
} |
|
262 |
} |
|
263 |
} |
|
264 |
||
14105 | 265 |
pub fn bezierize(&mut self) {} |
14074 | 266 |
|
14105 | 267 |
pub fn distort<I: Iterator<Item = u32>>( |
268 |
&mut self, |
|
269 |
distance_divisor: u32, |
|
270 |
random_numbers: &mut I, |
|
271 |
) { |
|
14074 | 272 |
loop { |
273 |
let old_len = self.total_len(); |
|
14105 | 274 |
self.divide_edges(distance_divisor, random_numbers); |
14074 | 275 |
|
14098 | 276 |
if self.total_len() == old_len { |
14074 | 277 |
break; |
278 |
} |
|
279 |
} |
|
280 |
||
281 |
self.bezierize(); |
|
282 |
} |
|
283 |
||
284 |
pub fn draw<T: Copy + PartialEq>(&self, land: &mut Land2D<T>, value: T) { |
|
14081
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
285 |
for segment in self.segments_iter() { |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
286 |
land.draw_line(segment, value); |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
287 |
} |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
288 |
} |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
289 |
|
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
290 |
fn segments_iter(&self) -> OutlineSegmentsIterator { |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
291 |
OutlineSegmentsIterator { |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
292 |
outline: self, |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
293 |
island: 0, |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
294 |
index: 0, |
14074 | 295 |
} |
296 |
} |
|
14100 | 297 |
|
298 |
pub fn mirror(&mut self) { |
|
14105 | 299 |
let r = self.size.width as i32 - 1; |
300 |
||
301 |
self.iter_mut().for_each(|p| p.x = r - p.x); |
|
14100 | 302 |
} |
303 |
||
304 |
pub fn flip(&mut self) { |
|
14105 | 305 |
let t = self.size.height as i32 - 1; |
306 |
||
307 |
self.iter_mut().for_each(|p| p.y = t - p.y); |
|
14100 | 308 |
} |
14074 | 309 |
} |
14081
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
310 |
|
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
311 |
struct OutlineSegmentsIterator<'a> { |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
312 |
outline: &'a OutlinePoints, |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
313 |
island: usize, |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
314 |
index: usize, |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
315 |
} |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
316 |
|
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
317 |
impl<'a> Iterator for OutlineSegmentsIterator<'a> { |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
318 |
type Item = Line; |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
319 |
|
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
320 |
fn next(&mut self) -> Option<Self::Item> { |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
321 |
if self.island < self.outline.islands.len() { |
14083 | 322 |
if self.index + 1 < self.outline.islands[self.island].len() { |
323 |
let result = Some(Line::new( |
|
324 |
self.outline.islands[self.island][self.index], |
|
325 |
self.outline.islands[self.island][self.index + 1], |
|
326 |
)); |
|
327 |
||
328 |
self.index += 1; |
|
329 |
||
330 |
result |
|
331 |
} else if self.index + 1 == self.outline.islands[self.island].len() { |
|
332 |
let result = Some(Line::new( |
|
333 |
self.outline.islands[self.island][self.index], |
|
334 |
self.outline.islands[self.island][0], |
|
335 |
)); |
|
336 |
||
337 |
self.island += 1; |
|
338 |
self.index = 0; |
|
339 |
||
340 |
result |
|
14081
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
341 |
} else { |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
342 |
self.island += 1; |
14083 | 343 |
self.index = 0; |
14081
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
344 |
self.next() |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
345 |
} |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
346 |
} else { |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
347 |
None |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
348 |
} |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
349 |
} |
e5904ead4864
Introduce OutlineSegmentsIterator, some refactoring
unC0Rr
parents:
14074
diff
changeset
|
350 |
} |
14083 | 351 |
|
352 |
#[test()] |
|
353 |
fn points_test() { |
|
354 |
let mut points = OutlinePoints { |
|
355 |
islands: vec![ |
|
356 |
vec![Point::new(0, 0), Point::new(20, 0), Point::new(30, 30)], |
|
357 |
vec![Point::new(10, 15), Point::new(15, 20), Point::new(20, 15)], |
|
358 |
], |
|
359 |
fill_points: vec![Point::new(1, 1)], |
|
360 |
play_box: Rect::from_box(0, 100, 0, 100).with_margin(10), |
|
361 |
size: Size::square(100), |
|
362 |
}; |
|
363 |
||
364 |
let segments: Vec<Line> = points.segments_iter().collect(); |
|
365 |
assert_eq!( |
|
366 |
segments.first(), |
|
367 |
Some(&Line::new(Point::new(0, 0), Point::new(20, 0))) |
|
368 |
); |
|
369 |
assert_eq!( |
|
370 |
segments.last(), |
|
371 |
Some(&Line::new(Point::new(20, 15), Point::new(10, 15))) |
|
372 |
); |
|
373 |
||
374 |
points.iter_mut().for_each(|p| p.x = 2); |
|
375 |
assert_eq!(points.fill_points[0].x, 2); |
|
376 |
assert_eq!(points.islands[0][0].x, 2); |
|
377 |
} |