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 }