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