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