1 use integral_geometry::{Rect, Size};

     2 use std::cmp::{max, min, Ordering};

     3 

     4 pub struct Atlas {

     5     size: Size,

     6     free_rects: Vec<Rect>,

     7     used_rects: Vec<Rect>,

     8 }

     9 

    10 #[derive(PartialEq, Eq, PartialOrd, Ord)]

    11 struct Fit {

    12     short_size: u32,

    13     long_size: u32,

    14 }

    15 

    16 impl Fit {

    17     fn new() -> Self {

    18         Self {

    19             short_size: u32::max_value(),

    20             long_size: u32::max_value(),

    21         }

    22     }

    23 

    24     fn measure(container: Size, size: Size) -> Option<Self> {

    25         if container.contains(size) {

    26             let x_leftover = container.width - size.width;

    27             let y_leftover = container.height - size.height;

    28             Some(Self {

    29                 short_size: min(x_leftover, y_leftover) as u32,

    30                 long_size: max(x_leftover, y_leftover) as u32,

    31             })

    32         } else {

    33             None

    34         }

    35     }

    36 }

    37 

    38 fn split_rect(free_rect: Rect, rect: Rect) -> Vec<Rect> {

    39     let mut result = vec![];

    40     if free_rect.intersects(&rect) {

    41         if rect.left() > free_rect.left() {

    42             let trim = free_rect.right() - rect.left() + 1;

    43             result.push(free_rect.with_margins(0, -trim, 0, 0))

    44         }

    45         if rect.right() < free_rect.right() {

    46             let trim = rect.right() - free_rect.left() + 1;

    47             result.push(free_rect.with_margins(-trim, 0, 0, 0))

    48         }

    49         if rect.top() > free_rect.top() {

    50             let trim = free_rect.bottom() - rect.top() + 1;

    51             result.push(free_rect.with_margins(0, 0, 0, -trim));

    52         }

    53         if rect.bottom() < free_rect.bottom() {

    54             let trim = rect.bottom() - free_rect.top() + 1;

    55             result.push(free_rect.with_margins(0, 0, -trim, 0));

    56         }

    57     }

    58     result

    59 }

    60 

    61 impl Atlas {

    62     pub fn new(size: Size) -> Self {

    63         Self {

    64             size,

    65             free_rects: vec![Rect::at_origin(size)],

    66             used_rects: vec![],

    67         }

    68     }

    69 

    70     fn find_position(&self, size: Size) -> Option<(Rect, Fit)> {

    71         let mut best_rect = Rect::EMPTY;

    72         let mut best_fit = Fit::new();

    73 

    74         for rect in &self.free_rects {

    75             if let Some(fit) = Fit::measure(rect.size(), size) {

    76                 if fit < best_fit {

    77                     best_fit = fit;

    78                     best_rect = Rect::from_size(rect.top_left(), size);

    79                 }

    80             }

    81 

    82             if let Some(fit) = Fit::measure(rect.size(), size.transpose()) {

    83                 if fit < best_fit {

    84                     best_fit = fit;

    85                     best_rect = Rect::from_size(rect.top_left(), size.transpose());

    86                 }

    87             }

    88         }

    89 

    90         if best_rect == Rect::EMPTY {

    91             None

    92         } else {

    93             Some((best_rect, best_fit))

    94         }

    95     }

    96 

    97     fn prune(&mut self) {

    98         self.free_rects = self

    99             .free_rects

   100             .iter()

   101             .filter(|inner| {

   102                 self.free_rects

   103                     .iter()

   104                     .all(|outer| outer == *inner || !outer.contains_rect(inner))

   105             })

   106             .cloned()

   107             .collect();

   108     }

   109 

   110     pub fn insert_adaptive(&mut self, size: Size) -> Option<Rect> {

   111         let (rect, fit) = self.find_position(size)?;

   112 

   113         let mut rects_to_process = self.free_rects.len();

   114         let mut i = 0;

   115 

   116         while i < rects_to_process {

   117             let rects = split_rect(self.free_rects[i], rect);

   118             if !rects.is_empty() {

   119                 self.free_rects.remove(i);

   120                 self.free_rects.extend(rects);

   121                 rects_to_process -= 1

   122             } else {

   123                 i += 1;

   124             }

   125         }

   126 

   127         self.used_rects.push(rect);

   128         self.prune();

   129         Some(rect)

   130     }

   131 

   132     pub fn insert_set<Iter>(&mut self, sizes: Iter) -> Vec<Rect>

   133     where

   134         Iter: Iterator<Item = Size>,

   135     {

   136         unimplemented!()

   137     }

   138 

   139     pub fn reset(&mut self) {

   140         self.free_rects.clear();

   141         self.used_rects.clear();

   142         self.free_rects.push(Rect::at_origin(self.size));

   143     }

   144 }

   145 

   146 #[cfg(test)]

   147 mod tests {

   148     use super::Atlas;

   149     use integral_geometry::{Rect, Size};

   150 

   151     #[test]

   152     fn insert() {

   153         let atlas_size = Size::square(16);

   154         let mut atlas = Atlas::new(atlas_size);

   155 

   156         assert_eq!(None, atlas.insert_adaptive(Size::square(20)));

   157 

   158         let rect_size = Size::new(11, 3);

   159         let rect = atlas.insert_adaptive(rect_size).unwrap();

   160         assert_eq!(rect, Rect::at_origin(rect_size));

   161         assert_eq!(2, atlas.free_rects.len());

   162     }

   163 }