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