# HG changeset patch # User unc0rr # Date 1541195962 -3600 # Node ID 4d22be35cfa29da4f42faab85f9741d364376acd # Parent 7845beb87cb5967ec726c413eabe5f981cbf8f03 Finish porting FindPoint() diff -r 7845beb87cb5 -r 4d22be35cfa2 hedgewars/uLandGenTemplateBased.pas --- a/hedgewars/uLandGenTemplateBased.pas Fri Nov 02 23:33:22 2018 +0300 +++ b/hedgewars/uLandGenTemplateBased.pas Fri Nov 02 22:59:22 2018 +0100 @@ -164,9 +164,9 @@ fp:= pa.ar[i + 1] else if (i <> si) then begin - p4:= pa.ar[i + 1]; - if p4.x = NTPX then - p4:= fp; + p4:= pa.ar[i + 1]; + if p4.x = NTPX then + p4:= fp; // check if it intersects t1:= (mp.x - pa.ar[i].x) * b - a * (mp.y - pa.ar[i].y); diff -r 7845beb87cb5 -r 4d22be35cfa2 rust/landgen/src/lib.rs --- a/rust/landgen/src/lib.rs Fri Nov 02 23:33:22 2018 +0300 +++ b/rust/landgen/src/lib.rs Fri Nov 02 22:59:22 2018 +0100 @@ -1,19 +1,24 @@ -pub mod template_based; +mod outline; pub mod outline_template; -mod outline; +pub mod template_based; extern crate integral_geometry; +extern crate itertools; extern crate land2d; -extern crate itertools; pub struct LandGenerationParameters { zero: T, basic: T, + distance_divisor: u32, } -impl LandGenerationParameters { +impl LandGenerationParameters { pub fn new(zero: T, basic: T) -> Self { - Self { zero, basic } + Self { + zero, + basic, + distance_divisor: 1, + } } } diff -r 7845beb87cb5 -r 4d22be35cfa2 rust/landgen/src/outline.rs --- a/rust/landgen/src/outline.rs Fri Nov 02 23:33:22 2018 +0300 +++ b/rust/landgen/src/outline.rs Fri Nov 02 22:59:22 2018 +0100 @@ -46,6 +46,13 @@ self.islands.iter().map(|i| i.len()).sum::() + self.fill_points.len() } + pub fn iter(&self) -> impl Iterator { + self.islands + .iter() + .flat_map(|i| i.iter()) + .chain(self.fill_points.iter()) + } + pub fn iter_mut(&mut self) -> impl Iterator { self.islands .iter_mut() @@ -56,8 +63,44 @@ fn divide_edge>( &self, segment: Line, + distance_divisor: u32, random_numbers: &mut I, ) -> Option { + #[inline] + fn intersect(p: &Point, m: &Point, p1: &Point, p2: &Point) -> bool { + let t1 = (m.x - p1.x) * p.y - p.x * (m.y - p1.y); + let t2 = (m.x - p2.x) * p.y - p.x * (m.y - p2.y); + + (t1 > 0) != (t2 > 0) + } + + #[inline] + fn solve_intersection(p: &Point, m: &Point, s: &Point, e: &Point) -> Option<(i32, u32)> { + let f = *e - *s; + let aqpb = (p.x * f.y - f.x * p.y) as i64; + + if aqpb != 0 { + let iy = ((((s.x - m.x) as i64 * p.y as i64 + m.y as i64 * p.x as i64) + * f.y as i64 + - s.y as i64 * f.x as i64 * p.y as i64) + / aqpb) as i32; + let ix = if p.y.abs() > f.y.abs() { + (iy - m.y) * p.x / p.y + m.x + } else { + (iy - s.y) * f.x / f.y + s.x + }; + + let intersection_point = Point::new(ix, iy); + let diff_point = *m - intersection_point; + let d = diff_point.integral_norm(); + let t = p.y * diff_point.y + p.x * diff_point.x; + + Some((t, d)) + } else { + None + } + } + let min_distance = 40; // new point should fall inside this box let map_box = self.play_box.with_margin(min_distance); @@ -125,11 +168,71 @@ } // now go through all other segments + for s in self.segments_iter() { + if s != segment { + if intersect(&p, &mid_point, &s.start, &s.end) { + if let Some((t, d)) = solve_intersection(&p, &mid_point, &s.start, &s.end) { + if t > 0 { + dist_left = min(d, dist_left); + } else { + dist_right = min(d, dist_right); + } + } + } + } + } - None + // go through all points, including fill points + for pi in self.iter() { + if *pi != segment.start && *pi != segment.end { + if intersect(&p, &pi, &segment.start, &segment.end) { + // ray from segment.start + if let Some((t, d)) = solve_intersection(&p, &mid_point, &segment.start, &pi) { + if t > 0 { + dist_left = min(d, dist_left); + } else { + dist_right = min(d, dist_right); + } + } + + // ray from segment.end + if let Some((t, d)) = solve_intersection(&p, &mid_point, &segment.end, &pi) { + if t > 0 { + dist_left = min(d, dist_left); + } else { + dist_right = min(d, dist_right); + } + } + } + } + } + + let max_dist = p.integral_norm() * 100 / distance_divisor; + dist_left = min(dist_left, max_dist); + dist_right = min(dist_right, max_dist); + + if dist_right + dist_left < min_distance as u32 * 2 + 10 { + // limits are too narrow, just divide + Some(mid_point) + } else { + // select distance within [-dist_left; dist_right], keeping min_distance in mind + let d = -(dist_left as i32) + + min_distance + + random_numbers.next().unwrap() as i32 + % (dist_right as i32 + dist_left as i32 - min_distance * 2); + + Some(Point::new( + mid_point.x + p.x * d / distance_divisor as i32, + mid_point.y + p.y * d / distance_divisor as i32, + )) + } } - fn divide_edges>(&mut self, random_numbers: &mut I) { + fn divide_edges>( + &mut self, + distance_divisor: u32, + random_numbers: &mut I, + ) { for is in 0..self.islands.len() { let mut i = 0; let mut segment; @@ -151,7 +254,8 @@ segment = Line::new(island[i], end_point); } - if let Some(new_point) = self.divide_edge(segment, random_numbers) { + if let Some(new_point) = self.divide_edge(segment, distance_divisor, random_numbers) + { self.islands[is].insert(i + 1, new_point); i += 2; } else { @@ -161,14 +265,16 @@ } } - pub fn bezierize(&mut self) { - unimplemented!() - } + pub fn bezierize(&mut self) {} - pub fn distort>(&mut self, random_numbers: &mut I) { + pub fn distort>( + &mut self, + distance_divisor: u32, + random_numbers: &mut I, + ) { loop { let old_len = self.total_len(); - self.divide_edges(random_numbers); + self.divide_edges(distance_divisor, random_numbers); if self.total_len() == old_len { break; @@ -193,15 +299,15 @@ } pub fn mirror(&mut self) { - let width = self.size.width as i32; - self.iter_mut() - .for_each(|p| p.x = width - 1 - p.x); + let r = self.size.width as i32 - 1; + + self.iter_mut().for_each(|p| p.x = r - p.x); } pub fn flip(&mut self) { - let height = self.size.height as i32; - self.iter_mut() - .for_each(|p| p.y = height - 1 - p.y); + let t = self.size.height as i32 - 1; + + self.iter_mut().for_each(|p| p.y = t - p.y); } } diff -r 7845beb87cb5 -r 4d22be35cfa2 rust/landgen/src/outline_template.rs --- a/rust/landgen/src/outline_template.rs Fri Nov 02 23:33:22 2018 +0300 +++ b/rust/landgen/src/outline_template.rs Fri Nov 02 22:59:22 2018 +0100 @@ -1,6 +1,5 @@ use integral_geometry::{Point, Rect, Size}; - pub struct OutlineTemplate { pub islands: Vec>, pub fill_points: Vec, diff -r 7845beb87cb5 -r 4d22be35cfa2 rust/landgen/src/template_based.rs --- a/rust/landgen/src/template_based.rs Fri Nov 02 23:33:22 2018 +0300 +++ b/rust/landgen/src/template_based.rs Fri Nov 02 22:59:22 2018 +0100 @@ -6,7 +6,6 @@ use outline::OutlinePoints; use outline_template::OutlineTemplate; - pub struct TemplatedLandGenerator { outline_template: OutlineTemplate, } @@ -25,8 +24,12 @@ ) -> Land2D { let mut land = Land2D::new(self.outline_template.size, parameters.basic); - let mut points = - OutlinePoints::from_outline_template(&self.outline_template, land.play_box(), land.size(), random_numbers); + let mut points = OutlinePoints::from_outline_template( + &self.outline_template, + land.play_box(), + land.size(), + random_numbers, + ); // mirror if self.outline_template.can_mirror { @@ -46,7 +49,7 @@ } } - points.distort(random_numbers); + points.distort(parameters.distance_divisor, random_numbers); points.draw(&mut land, parameters.zero);