1 use itertools::Itertools; |
1 use itertools::Itertools; |
2 use std::cmp::min; |
2 use std::cmp::min; |
3 |
3 |
4 use integral_geometry::{ |
4 use integral_geometry::{Line, Point, Polygon, Rect, Size}; |
5 Line, Point, Rect, Size, Polygon |
|
6 }; |
|
7 use land2d::Land2D; |
5 use land2d::Land2D; |
8 |
6 |
9 use outline_template::OutlineTemplate; |
7 use outline_template::OutlineTemplate; |
10 |
8 |
11 pub struct OutlinePoints { |
9 pub struct OutlinePoints { |
12 pub islands: Vec<Polygon>, |
10 pub islands: Vec<Polygon>, |
13 pub fill_points: Vec<Point>, |
11 pub fill_points: Vec<Point>, |
14 pub size: Size, |
12 pub size: Size, |
15 pub play_box: Rect, |
13 pub play_box: Rect, |
|
14 intersections_box: Rect, |
16 } |
15 } |
17 |
16 |
18 impl OutlinePoints { |
17 impl OutlinePoints { |
19 pub fn from_outline_template<I: Iterator<Item = u32>>( |
18 pub fn from_outline_template<I: Iterator<Item = u32>>( |
20 outline_template: &OutlineTemplate, |
19 outline_template: &OutlineTemplate, |
37 (rnd_a % rect.width) as i32, |
36 (rnd_a % rect.width) as i32, |
38 (rnd_b % rect.height) as i32, |
37 (rnd_b % rect.height) as i32, |
39 ) |
38 ) |
40 + play_box.top_left() |
39 + play_box.top_left() |
41 }) |
40 }) |
42 .collect::<Vec<_>>().into() |
41 .collect::<Vec<_>>() |
|
42 .into() |
43 }) |
43 }) |
44 .collect(), |
44 .collect(), |
45 fill_points: outline_template.fill_points.clone(), |
45 fill_points: outline_template.fill_points.clone(), |
|
46 intersections_box: Rect::at_origin(size) |
|
47 .with_margin(size.to_square().width as i32 * -2), |
46 } |
48 } |
47 } |
49 } |
48 |
50 |
49 pub fn total_len(&self) -> usize { |
51 pub fn total_len(&self) -> usize { |
50 self.islands.iter().map(|i| i.edges_count()).sum::<usize>() + self.fill_points.len() |
52 self.islands.iter().map(|i| i.edges_count()).sum::<usize>() + self.fill_points.len() |
77 |
79 |
78 (t1 > 0) != (t2 > 0) |
80 (t1 > 0) != (t2 > 0) |
79 } |
81 } |
80 |
82 |
81 #[inline] |
83 #[inline] |
82 fn solve_intersection(p: &Point, m: &Point, s: &Point, e: &Point) -> Option<(i32, u32)> { |
84 fn solve_intersection( |
|
85 intersections_box: &Rect, |
|
86 p: &Point, |
|
87 m: &Point, |
|
88 s: &Point, |
|
89 e: &Point, |
|
90 ) -> Option<(i32, u32)> { |
83 let f = *e - *s; |
91 let f = *e - *s; |
84 let aqpb = p.cross(f) as i64; |
92 let aqpb = p.cross(f) as i64; |
85 |
93 |
86 if aqpb != 0 { |
94 if aqpb != 0 { |
87 let iy = ((((s.x - m.x) as i64 * p.y as i64 + m.y as i64 * p.x as i64) |
95 let mut iy = ((((s.x - m.x) as i64 * p.y as i64 + m.y as i64 * p.x as i64) |
88 * f.y as i64 |
96 * f.y as i64 |
89 - s.y as i64 * f.x as i64 * p.y as i64) |
97 - s.y as i64 * f.x as i64 * p.y as i64) |
90 / aqpb) as i32; |
98 / aqpb) as i32; |
|
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 |
91 let ix = if p.y.abs() > f.y.abs() { |
107 let ix = if p.y.abs() > f.y.abs() { |
92 (iy - m.y) * p.x / p.y + m.x |
108 (iy - m.y) * p.x / p.y + m.x |
93 } else { |
109 } else { |
94 (iy - s.y) * f.x / f.y + s.x |
110 (iy - s.y) * f.x / f.y + s.x |
95 }; |
111 }; |
171 |
187 |
172 // now go through all other segments |
188 // now go through all other segments |
173 for s in self.segments_iter() { |
189 for s in self.segments_iter() { |
174 if s != segment { |
190 if s != segment { |
175 if intersect(&p, &mid_point, &s.start, &s.end) { |
191 if intersect(&p, &mid_point, &s.start, &s.end) { |
176 if let Some((t, d)) = solve_intersection(&p, &mid_point, &s.start, &s.end) { |
192 if let Some((t, d)) = solve_intersection( |
|
193 &self.intersections_box, |
|
194 &p, |
|
195 &mid_point, |
|
196 &s.start, |
|
197 &s.end, |
|
198 ) { |
177 if t > 0 { |
199 if t > 0 { |
178 dist_right = min(dist_right, d); |
200 dist_right = min(dist_right, d); |
179 } else { |
201 } else { |
180 dist_left = min(dist_left, d); |
202 dist_left = min(dist_left, d); |
181 } |
203 } |
187 // go through all points, including fill points |
209 // go through all points, including fill points |
188 for pi in self.iter() { |
210 for pi in self.iter() { |
189 if *pi != segment.start && *pi != segment.end { |
211 if *pi != segment.start && *pi != segment.end { |
190 if intersect(&p, &pi, &segment.start, &segment.end) { |
212 if intersect(&p, &pi, &segment.start, &segment.end) { |
191 // ray from segment.start |
213 // ray from segment.start |
192 if let Some((t, d)) = solve_intersection(&p, &mid_point, &segment.start, &pi) { |
214 if let Some((t, d)) = solve_intersection( |
|
215 &self.intersections_box, |
|
216 &p, |
|
217 &mid_point, |
|
218 &segment.start, |
|
219 &pi, |
|
220 ) { |
193 if t > 0 { |
221 if t > 0 { |
194 dist_right = min(dist_right, d); |
222 dist_right = min(dist_right, d); |
195 } else { |
223 } else { |
196 dist_left = min(dist_left, d); |
224 dist_left = min(dist_left, d); |
197 } |
225 } |
198 } |
226 } |
199 |
227 |
200 // ray from segment.end |
228 // ray from segment.end |
201 if let Some((t, d)) = solve_intersection(&p, &mid_point, &segment.end, &pi) { |
229 if let Some((t, d)) = solve_intersection( |
|
230 &self.intersections_box, |
|
231 &p, |
|
232 &mid_point, |
|
233 &segment.end, |
|
234 &pi, |
|
235 ) { |
202 if t > 0 { |
236 if t > 0 { |
203 dist_right = min(dist_right, d); |
237 dist_right = min(dist_right, d); |
204 } else { |
238 } else { |
205 dist_left = min(dist_left, d); |
239 dist_left = min(dist_left, d); |
206 } |
240 } |
237 ) { |
271 ) { |
238 for is in 0..self.islands.len() { |
272 for is in 0..self.islands.len() { |
239 let mut i = 0; |
273 let mut i = 0; |
240 while i < self.islands[is].edges_count() { |
274 while i < self.islands[is].edges_count() { |
241 let segment = self.islands[is].get_edge(i); |
275 let segment = self.islands[is].get_edge(i); |
242 if let Some(new_point) = self.divide_edge(segment, distance_divisor, random_numbers) { |
276 if let Some(new_point) = self.divide_edge(segment, distance_divisor, random_numbers) |
|
277 { |
243 self.islands[is].split_edge(i, new_point); |
278 self.islands[is].split_edge(i, new_point); |
244 i += 2; |
279 i += 2; |
245 } else { |
280 } else { |
246 i += 1; |
281 i += 1; |
247 } |
282 } |
289 } |
324 } |
290 } |
325 } |
291 |
326 |
292 #[test()] |
327 #[test()] |
293 fn points_test() { |
328 fn points_test() { |
294 ; |
|
295 let mut points = OutlinePoints { |
329 let mut points = OutlinePoints { |
296 |
|
297 islands: vec![ |
330 islands: vec![ |
298 Polygon::new(&[Point::new(0, 0), Point::new(20, 0), Point::new(30, 30)]), |
331 Polygon::new(&[Point::new(0, 0), Point::new(20, 0), Point::new(30, 30)]), |
299 Polygon::new(&[Point::new(10, 15), Point::new(15, 20), Point::new(20, 15)]), |
332 Polygon::new(&[Point::new(10, 15), Point::new(15, 20), Point::new(20, 15)]), |
300 ], |
333 ], |
301 fill_points: vec![Point::new(1, 1)], |
334 fill_points: vec![Point::new(1, 1)], |
302 play_box: Rect::from_box(0, 100, 0, 100).with_margin(10), |
335 play_box: Rect::from_box(0, 100, 0, 100).with_margin(10), |
303 size: Size::square(100), |
336 size: Size::square(100), |
|
337 intersections_box: Rect::from_box(0, 0, 100, 100), |
304 }; |
338 }; |
305 |
339 |
306 let segments: Vec<Line> = points.segments_iter().collect(); |
340 let segments: Vec<Line> = points.segments_iter().collect(); |
307 assert_eq!( |
341 assert_eq!( |
308 segments.first(), |
342 segments.first(), |
312 segments.last(), |
346 segments.last(), |
313 Some(&Line::new(Point::new(20, 15), Point::new(10, 15))) |
347 Some(&Line::new(Point::new(20, 15), Point::new(10, 15))) |
314 ); |
348 ); |
315 |
349 |
316 points.iter_mut().for_each(|p| p.x = 2); |
350 points.iter_mut().for_each(|p| p.x = 2); |
|
351 |
317 assert_eq!(points.fill_points[0].x, 2); |
352 assert_eq!(points.fill_points[0].x, 2); |
318 assert_eq!(points.islands[0].get_edge(0).start.x, 2); |
353 assert_eq!(points.islands[0].get_edge(0).start.x, 2); |
319 } |
354 } |