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