src/rbp.rs

   1 // flow-rbp: A library for packing rectangles into two-dimensional finite bins.
   2 // zlib License (see LICENSE)
   3
   4 /// Specifies the different heuristic rules that can be used when deciding where to place a new
   5 /// rectangle.
   6 #[derive(Clone, Debug)]
   7 pub enum FreeRectHeuristic {
   8     /// Choose to pack `R` into such `Fi` that `min(wf - w, hf - h)` is the smallest. In other words, we
   9     /// minimize the length of the shorter leftover side.
  10     ShortSideFit,
  11
  12     /// Pack `R` into an `Fi` such that `max(wf - w, hf - h)` is the smallest. That is, we minimize
  13     /// the length of the longer leftover side.
  14     LongSideFit,
  15
  16     /// Pick the `Fi ∈ F` that is smallest in area to place the next rectangle `R` into. If there is a
  17     /// tie, we use the [`ShortSideFit`](crate::rbp::FreeRectHeuristic::ShortSideFit) rule to break it.
  18     AreaFit,
  19
  20     /// Orient and place each rectangle to the position where the y-coordinate of the top side of the
  21     /// rectangle is the smallest and if there are several such valid positions, pick the one that has
  22     /// the smallest x-coordinate value.
  23     BottomLeft,
  24
  25     /// Place `R` into a position where the length of the perimeter of `R` that is touched by the bin
  26     /// edge or by a previously packed rectangle is maximized.
  27     ContactPoint,
  28 }
  29
  30 /// Specifies the different error types that can occur.
  31 #[derive(PartialEq, Clone, Debug)]
  32 pub enum RectsBinPackError {
  33     /// Invalid argument
  34     InvalidArg,
  35 }
  36
  37 /// Specifies the properties of a 2D rectangle.
  38 #[derive(Clone, Debug)]
  39 pub struct Rect2D {
  40     /// is the x offset
  41     pub x: i32,
  42
  43     /// is the y offset
  44     pub y: i32,
  45
  46     /// is the width
  47     pub width: i32,
  48
  49     /// is the height
  50     pub height: i32,
  51 }
  52
  53 impl Rect2D {
  54     /// Instantiates a 2D rectangle of size (0, 0, 0, 0).
  55     ///
  56     /// # Examples
  57     ///
  58     /// ```
  59     /// use flow_rbp::Rect2D;
  60     ///
  61     /// let rect = Rect2D::new();
  62     /// assert_eq!(rect.x, 0);
  63     /// assert_eq!(rect.y, 0);
  64     /// assert_eq!(rect.width, 0);
  65     /// assert_eq!(rect.height, 0);
  66     /// ```
  67     pub fn new() -> Self {
  68         Self {
  69             x: 0,
  70             y: 0,
  71             width: 0,
  72             height: 0,
  73         }
  74     }
  75
  76     /// Instantiates a 2D rectangle with given size properties.
  77     ///
  78     /// # Arguments
  79     ///
  80     /// * `x` - is the x offset.
  81     /// * `y` - is the y offset.
  82     /// * `width` - is the width.
  83     /// * `height` - is the height.
  84     ///
  85     /// # Errors
  86     ///
  87     /// [`InvalidArg`](crate::rbp::RectsBinPackError::InvalidArg)
  88     /// is returned if `x < 0 || y < 0 || width <= 0 || height <= 0`.
  89     ///
  90     /// # Examples
  91     ///
  92     /// ```
  93     /// use flow_rbp::Rect2D;
  94     ///
  95     /// let rect = Rect2D::with_details(0, 0, 32, 16).unwrap();
  96     /// assert_eq!(rect.x, 0);
  97     /// assert_eq!(rect.y, 0);
  98     /// assert_eq!(rect.width, 32);
  99     /// assert_eq!(rect.height, 16);
 100     ///
 101     /// // this should fail:
 102     /// assert_eq!(Rect2D::with_details(0, 0, 0, 0).is_err(), true);
 103     /// ```
 104     pub fn with_details(
 105         x: i32,
 106         y: i32,
 107         width: i32,
 108         height: i32,
 109     ) -> Result<Self, RectsBinPackError> {
 110         if x >= 0 && y >= 0 && width > 0 && height > 0 {
 111             Ok(Self {
 112                 x,
 113                 y,
 114                 width,
 115                 height,
 116             })
 117         } else {
 118             Err(RectsBinPackError::InvalidArg)
 119         }
 120     }
 121 }
 122
 123 /// Specifies the properties of a rectangle bin.
 124 #[derive(Clone, Debug)]
 125 pub struct RectsBinPack {
 126     /// is the width of the bin
 127     width: i32,
 128
 129     /// is the height of the bin
 130     height: i32,
 131
 132     /// is the flag indicating whether rotation is allowed or not
 133     allow_flip: bool,
 134
 135     /// is the vector holding the used rects
 136     used_rects: Vec<Rect2D>,
 137
 138     /// is the vector holding the free rects
 139     free_rects: Vec<Rect2D>,
 140 }
 141
 142 impl RectsBinPack {
 143     /// Instantiates a empty bin of given size.
 144     ///
 145     /// # Arguments
 146     ///
 147     /// * `width` - is the width of the bin
 148     /// * `height` - is the height of the bin
 149     /// * `allow_flip` - is the flag indicating whether the packing algorithm is allowed to rotate
 150     /// the input rectangle 90 degrees clockwise to consider a better placement.
 151     ///
 152     /// # Errors
 153     ///
 154     /// [`RectsBinPackError::InvalidArg`](crate::rbp::RectsBinPackError)
 155     /// is returned if `width <= 0 || height <= 0`.
 156     ///
 157     /// # Examples
 158     ///
 159     /// ```
 160     /// use flow_rbp::RectsBinPack;
 161     /// use flow_rbp::FreeRectHeuristic;
 162     ///
 163     /// let mut rbp = RectsBinPack::new(32, 32, false).unwrap();
 164     /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true);
 165     /// assert_eq!(rbp.insert(33, 33, FreeRectHeuristic::BottomLeft).is_none(), true);
 166     /// ```
 167     pub fn new(width: i32, height: i32, allow_flip: bool) -> Result<Self, RectsBinPackError> {
 168         if width > 0 && height > 0 {
 169             Ok(Self {
 170                 width,
 171                 height,
 172                 allow_flip,
 173                 used_rects: Vec::new(),
 174                 free_rects: vec![Rect2D::with_details(0, 0, width, height).unwrap()],
 175             })
 176         } else {
 177             Err(RectsBinPackError::InvalidArg)
 178         }
 179     }
 180
 181     /// Insert a single rectangle into the bin, possibly rotated.
 182     ///
 183     /// # Arguments
 184     ///
 185     /// * `width` - is the rectangle width
 186     /// * `height` - is the rectangle height
 187     /// * `heuristic` - is the heuristic method to use when packing
 188     ///
 189     /// # Examples
 190     ///
 191     /// ```
 192     /// use flow_rbp::RectsBinPack;
 193     /// use flow_rbp::FreeRectHeuristic;
 194     ///
 195     /// let mut rbp = RectsBinPack::new(32, 32, false).unwrap();
 196     /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true);
 197     /// assert_eq!(rbp.insert(33, 33, FreeRectHeuristic::BottomLeft).is_none(), true);
 198     /// ```
 199     pub fn insert(
 200         &mut self,
 201         width: i32,
 202         height: i32,
 203         heuristic: FreeRectHeuristic,
 204     ) -> Option<Rect2D> {
 205         let output = match heuristic {
 206             FreeRectHeuristic::ShortSideFit => self.get_rect_for_best_short_side_fit(width, height),
 207             FreeRectHeuristic::BottomLeft => self.get_rect_for_bottom_left(width, height),
 208             FreeRectHeuristic::ContactPoint => self.get_rect_for_contact_point(width, height),
 209             FreeRectHeuristic::LongSideFit => self.get_rect_for_best_long_side_fit(width, height),
 210             FreeRectHeuristic::AreaFit => self.get_rect_for_best_area_fit(width, height),
 211         };
 212
 213         if let Some(new_rect) = output {
 214             let mut i: usize = 0;
 215             while i < self.free_rects.len() {
 216                 if let Some(free_rect) = self.free_rects.get(i) {
 217                     if self.is_split_free_node(&free_rect.clone(), &new_rect) {
 218                         self.free_rects.remove(i);
 219                         continue;
 220                     }
 221                 }
 222
 223                 i += 1;
 224             }
 225
 226             self.prune_free_list();
 227             self.used_rects.push(new_rect.clone());
 228
 229             return Some(new_rect);
 230         } else {
 231             return None;
 232         }
 233     }
 234
 235     /// Computes the ratio of used surface area to the total bin area.
 236     ///
 237     /// # Examples
 238     ///
 239     /// ```
 240     /// use flow_rbp::RectsBinPack;
 241     /// use flow_rbp::FreeRectHeuristic;
 242     ///
 243     /// let mut rbp = RectsBinPack::new(32, 32, false).unwrap();
 244     ///
 245     /// // occupancy should be 0.0 initially:
 246     /// assert_eq!(rbp.get_occupancy(), 0.0);
 247     ///
 248     /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true);
 249     /// assert_eq!(rbp.get_occupancy(), 0.25);
 250     /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true);
 251     /// assert_eq!(rbp.get_occupancy(), 0.5);
 252     /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true);
 253     /// assert_eq!(rbp.get_occupancy(), 0.75);
 254     /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true);
 255     ///
 256     /// // occupancy should now be full as in 1.0:
 257     /// assert_eq!(rbp.get_occupancy(), 1.0);
 258     /// ```
 259     pub fn get_occupancy(&self) -> f32 {
 260         let mut used_surface_area: i32 = 0;
 261
 262         for i in 0..self.used_rects.len() {
 263             if let Some(rect) = self.used_rects.get(i) {
 264                 used_surface_area += rect.width * rect.height;
 265             }
 266         }
 267
 268         // return occupancy:
 269         return used_surface_area as f32 / (self.width * self.height) as f32;
 270     }
 271
 272     /// Computes the placement score for the contact point variant.
 273     fn get_score_for_contact_point(&self, x: i32, y: i32, width: i32, height: i32) -> i32 {
 274         let mut score: i32 = 0;
 275
 276         if x == 0 || x + width == self.width {
 277             score += height;
 278         }
 279
 280         if y == 0 || y + height == self.height {
 281             score += width;
 282         }
 283
 284         for i in 0..self.used_rects.len() {
 285             if let Some(used_rect) = self.used_rects.get(i) {
 286                 if used_rect.x == x + width || used_rect.x + used_rect.width == x {
 287                     score += self.get_common_interval_len(
 288                         used_rect.y,
 289                         used_rect.y + used_rect.height,
 290                         y,
 291                         y + height,
 292                     );
 293                 }
 294
 295                 if used_rect.y == y + height || used_rect.y + used_rect.height == y {
 296                     score += self.get_common_interval_len(
 297                         used_rect.x,
 298                         used_rect.x + used_rect.width,
 299                         x,
 300                         x + width,
 301                     );
 302                 }
 303             }
 304         }
 305
 306         return score;
 307     }
 308
 309     /// Computes the rect for bottom left placement variant.
 310     fn get_rect_for_bottom_left(&self, width: i32, height: i32) -> Option<Rect2D> {
 311         let mut new_rect = Rect2D::new();
 312
 313         let mut best_x = std::i32::MAX;
 314         let mut best_y = std::i32::MAX;
 315
 316         for i in 0..self.free_rects.len() {
 317             if let Some(free_rect) = self.free_rects.get(i) {
 318                 // true to place the rect in upright (non-flipped) orientation:
 319                 if free_rect.width >= width && free_rect.height >= height {
 320                     let top_side_y = free_rect.y + height;
 321
 322                     if top_side_y < best_y || (top_side_y == best_y && free_rect.x < best_x) {
 323                         new_rect.x = free_rect.x;
 324                         new_rect.y = free_rect.y;
 325                         new_rect.width = width;
 326                         new_rect.height = height;
 327                         best_x = free_rect.x;
 328                         best_y = top_side_y;
 329                     }
 330                 }
 331
 332                 if self.allow_flip && free_rect.width >= height && free_rect.height >= width {
 333                     let top_side_y = free_rect.y + width;
 334
 335                     if top_side_y < best_y || (top_side_y == best_y && free_rect.x < best_x) {
 336                         new_rect.x = free_rect.x;
 337                         new_rect.y = free_rect.y;
 338                         new_rect.width = height;
 339                         new_rect.height = width;
 340                         best_x = free_rect.x;
 341                         best_y = top_side_y;
 342                     }
 343                 }
 344             } else {
 345                 return None;
 346             }
 347         }
 348
 349         if new_rect.height == 0 || new_rect.width == 0 {
 350             return None;
 351         }
 352
 353         return Some(new_rect);
 354     }
 355
 356     /// Computes the rect for short side fit variant.
 357     fn get_rect_for_best_short_side_fit(&self, width: i32, height: i32) -> Option<Rect2D> {
 358         let mut new_rect = Rect2D::new();
 359
 360         let mut best_short_side_fit = std::i32::MAX;
 361         let mut best_long_side_fit = std::i32::MAX;
 362
 363         for i in 0..self.free_rects.len() {
 364             if let Some(free_rect) = self.free_rects.get(i) {
 365                 // try to place the rect in upright (non-flipped) orientation:
 366                 if free_rect.width >= width && free_rect.height >= height {
 367                     let left_over_horiz = free_rect.width - width;
 368                     let left_over_vert = free_rect.height - height;
 369                     let short_side_fit = std::cmp::min(left_over_horiz, left_over_vert);
 370                     let long_side_fit = std::cmp::max(left_over_horiz, left_over_vert);
 371
 372                     if short_side_fit < best_short_side_fit
 373                         || (short_side_fit == best_short_side_fit
 374                             && long_side_fit < best_long_side_fit)
 375                     {
 376                         new_rect.x = free_rect.x;
 377                         new_rect.y = free_rect.y;
 378                         new_rect.width = width;
 379                         new_rect.height = height;
 380                         best_short_side_fit = short_side_fit;
 381                         best_long_side_fit = long_side_fit;
 382                     }
 383                 }
 384
 385                 if self.allow_flip && free_rect.width >= height && free_rect.height >= width {
 386                     let flipped_left_over_horiz = free_rect.width - height;
 387                     let flipped_left_over_vert = free_rect.height - width;
 388                     let flipped_short_side_fit =
 389                         std::cmp::min(flipped_left_over_horiz, flipped_left_over_vert);
 390                     let flipped_long_side_fit =
 391                         std::cmp::max(flipped_left_over_horiz, flipped_left_over_vert);
 392
 393                     if flipped_short_side_fit < best_short_side_fit
 394                         || (flipped_short_side_fit == best_short_side_fit
 395                             && flipped_long_side_fit < best_long_side_fit)
 396                     {
 397                         new_rect.x = free_rect.x;
 398                         new_rect.y = free_rect.y;
 399                         new_rect.width = height;
 400                         new_rect.height = width;
 401                         best_short_side_fit = flipped_short_side_fit;
 402                         best_long_side_fit = flipped_long_side_fit;
 403                     }
 404                 }
 405             } else {
 406                 return None;
 407             }
 408         }
 409
 410         if new_rect.height == 0 || new_rect.width == 0 {
 411             return None;
 412         }
 413
 414         return Some(new_rect);
 415     }
 416
 417     /// Computes the rect for long side fit variant.
 418     fn get_rect_for_best_long_side_fit(&self, width: i32, height: i32) -> Option<Rect2D> {
 419         let mut new_rect = Rect2D::new();
 420
 421         let mut best_short_side_fit = std::i32::MAX;
 422         let mut best_long_side_fit = std::i32::MAX;
 423
 424         for i in 0..self.free_rects.len() {
 425             if let Some(free_rect) = self.free_rects.get(i) {
 426                 // try to place the rect in upright (non-flipped) orientation:
 427                 if free_rect.width >= width && free_rect.height >= height {
 428                     let left_over_horiz = free_rect.width - width;
 429                     let left_over_vert = free_rect.height - height;
 430                     let short_side_fit = std::cmp::min(left_over_horiz, left_over_vert);
 431                     let long_side_fit = std::cmp::max(left_over_horiz, left_over_vert);
 432
 433                     if long_side_fit < best_long_side_fit
 434                         || (long_side_fit == best_long_side_fit
 435                             && short_side_fit < best_short_side_fit)
 436                     {
 437                         new_rect.x = free_rect.x;
 438                         new_rect.y = free_rect.y;
 439                         new_rect.width = width;
 440                         new_rect.height = height;
 441                         best_short_side_fit = short_side_fit;
 442                         best_long_side_fit = long_side_fit;
 443                     }
 444                 }
 445
 446                 if self.allow_flip && free_rect.width >= height && free_rect.height >= width {
 447                     let left_over_horiz = free_rect.width - height;
 448                     let left_over_vert = free_rect.height - width;
 449                     let short_side_fit = std::cmp::min(left_over_horiz, left_over_vert);
 450                     let long_side_fit = std::cmp::max(left_over_horiz, left_over_vert);
 451
 452                     if long_side_fit < best_long_side_fit
 453                         || (long_side_fit == best_long_side_fit
 454                             && short_side_fit < best_short_side_fit)
 455                     {
 456                         new_rect.x = free_rect.x;
 457                         new_rect.y = free_rect.y;
 458                         new_rect.width = height;
 459                         new_rect.height = width;
 460                         best_short_side_fit = short_side_fit;
 461                         best_long_side_fit = long_side_fit;
 462                     }
 463                 }
 464             } else {
 465                 return None;
 466             }
 467         }
 468
 469         if new_rect.height == 0 || new_rect.width == 0 {
 470             return None;
 471         }
 472
 473         return Some(new_rect);
 474     }
 475
 476     /// Computes the rect for best area fit variant.
 477     fn get_rect_for_best_area_fit(&self, width: i32, height: i32) -> Option<Rect2D> {
 478         let mut new_rect = Rect2D::new();
 479
 480         let mut best_area_fit = std::i32::MAX;
 481         let mut best_short_side_fit = std::i32::MAX;
 482
 483         for i in 0..self.free_rects.len() {
 484             if let Some(free_rect) = self.free_rects.get(i) {
 485                 let area_fit = free_rect.width * free_rect.height - width * height;
 486
 487                 // try to place rect in upright (non-flipped) orientation:
 488                 if free_rect.width >= width && free_rect.height >= height {
 489                     let left_over_horiz = free_rect.width - width;
 490                     let left_over_vert = free_rect.height - height;
 491                     let short_side_fit = std::cmp::min(left_over_horiz, left_over_vert);
 492
 493                     if area_fit < best_area_fit
 494                         || (area_fit == best_area_fit && short_side_fit < best_short_side_fit)
 495                     {
 496                         new_rect.x = free_rect.x;
 497                         new_rect.y = free_rect.y;
 498                         new_rect.width = width;
 499                         new_rect.height = height;
 500                         best_short_side_fit = short_side_fit;
 501                         best_area_fit = area_fit;
 502                     }
 503                 }
 504
 505                 if self.allow_flip && free_rect.width >= height && free_rect.height >= width {
 506                     let left_over_horiz = free_rect.width - height;
 507                     let left_over_vert = free_rect.height - width;
 508                     let short_side_fit = std::cmp::min(left_over_horiz, left_over_vert);
 509
 510                     if area_fit < best_area_fit
 511                         || (area_fit == best_area_fit && short_side_fit < best_short_side_fit)
 512                     {
 513                         new_rect.x = free_rect.x;
 514                         new_rect.y = free_rect.y;
 515                         new_rect.width = height;
 516                         new_rect.height = width;
 517                         best_short_side_fit = short_side_fit;
 518                         best_area_fit = area_fit;
 519                     }
 520                 }
 521             } else {
 522                 return None;
 523             }
 524         }
 525
 526         if new_rect.height == 0 || new_rect.width == 0 {
 527             return None;
 528         }
 529
 530         return Some(new_rect);
 531     }
 532
 533     /// Computes the rect for contact point variant.
 534     fn get_rect_for_contact_point(&self, width: i32, height: i32) -> Option<Rect2D> {
 535         let mut new_rect = Rect2D::new();
 536         let mut best_contact_score = -1;
 537
 538         for i in 0..self.free_rects.len() {
 539             if let Some(free_rect) = self.free_rects.get(i) {
 540                 // try to place the rect in upright (non-flipped) orientation:
 541                 if free_rect.width >= width && free_rect.height >= height {
 542                     let contact_score =
 543                         self.get_score_for_contact_point(free_rect.x, free_rect.y, width, height);
 544
 545                     if contact_score > best_contact_score {
 546                         new_rect.x = free_rect.x;
 547                         new_rect.y = free_rect.y;
 548                         new_rect.width = width;
 549                         new_rect.height = height;
 550                         best_contact_score = contact_score;
 551                     }
 552                 }
 553
 554                 if self.allow_flip && free_rect.width >= height && free_rect.height >= width {
 555                     let contact_score =
 556                         self.get_score_for_contact_point(free_rect.x, free_rect.y, height, width);
 557
 558                     if contact_score > best_contact_score {
 559                         new_rect.x = free_rect.x;
 560                         new_rect.y = free_rect.y;
 561                         new_rect.width = height;
 562                         new_rect.height = width;
 563                         best_contact_score = contact_score;
 564                     }
 565                 }
 566             } else {
 567                 return None;
 568             }
 569         }
 570
 571         if new_rect.height == 0 || new_rect.width == 0 {
 572             return None;
 573         }
 574
 575         return Some(new_rect);
 576     }
 577
 578     /// returns true if the free rect was split
 579     fn is_split_free_node(&mut self, free_rect: &Rect2D, used_rect: &Rect2D) -> bool {
 580         // test with SAT if the rects even intersect:
 581         if used_rect.x >= free_rect.x + free_rect.width
 582             || used_rect.x + used_rect.width <= free_rect.x
 583             || used_rect.y >= free_rect.y + free_rect.height
 584             || used_rect.y + used_rect.height <= free_rect.y
 585         {
 586             return false;
 587         }
 588
 589         if used_rect.x < free_rect.x + free_rect.width
 590             && used_rect.x + used_rect.width > free_rect.x
 591         {
 592             // new node at the top side of the used node:
 593             if used_rect.y > free_rect.y && used_rect.y < free_rect.y + free_rect.height {
 594                 let mut new_rect = free_rect.clone();
 595                 new_rect.height = used_rect.y - new_rect.y;
 596                 self.free_rects.push(new_rect);
 597             }
 598
 599             // new node at the bottom side of the used node:
 600             if used_rect.y + used_rect.height < free_rect.y + free_rect.height {
 601                 let mut new_rect = free_rect.clone();
 602                 new_rect.y = used_rect.y + used_rect.height;
 603                 new_rect.height = free_rect.y + free_rect.height - (used_rect.y + used_rect.height);
 604                 self.free_rects.push(new_rect);
 605             }
 606         }
 607
 608         if used_rect.y < free_rect.y + free_rect.height
 609             && used_rect.y + used_rect.height > free_rect.y
 610         {
 611             // new node at the left side of the used node:
 612             if used_rect.x > free_rect.x && used_rect.x < free_rect.x + free_rect.width {
 613                 let mut new_rect = free_rect.clone();
 614                 new_rect.width = used_rect.x - new_rect.x;
 615                 self.free_rects.push(new_rect);
 616             }
 617
 618             // new node at the right side of the used node:
 619             if used_rect.x + used_rect.width < free_rect.x + free_rect.width {
 620                 let mut new_rect = free_rect.clone();
 621                 new_rect.x = used_rect.x + used_rect.width;
 622                 new_rect.width = free_rect.x + free_rect.width - (used_rect.x + used_rect.width);
 623                 self.free_rects.push(new_rect);
 624             }
 625         }
 626
 627         return true;
 628     }
 629
 630     /// goes through the free rect list and removes any redundant entries
 631     fn prune_free_list(&mut self) {
 632         // go through each pair and remove any rects that are redundant:
 633         let mut keep: Vec<bool> = vec![true; self.free_rects.len()];
 634         for i in 0..self.free_rects.len() {
 635             for j in i + 1..self.free_rects.len() {
 636                 if let Some(free_rect_i) = self.free_rects.get(i)
 637                     && let Some(free_rect_j) = self.free_rects.get(j)
 638                 {
 639                     if self.is_contained_on(free_rect_i, free_rect_j) {
 640                         if let Some(value) = keep.get_mut(i) {
 641                             *value = false;
 642                         }
 643                         break;
 644                     }
 645
 646                     if self.is_contained_on(free_rect_j, free_rect_i) {
 647                         if let Some(value) = keep.get_mut(j) {
 648                             *value = false;
 649                         }
 650                     }
 651                 }
 652             }
 653         }
 654
 655         // remove all items marked false:
 656         let mut iter = keep.iter();
 657         self.free_rects.retain(|_| *iter.next().unwrap());
 658     }
 659
 660     /// determine whether rect A is contained on rect B
 661     fn is_contained_on(&self, a: &Rect2D, b: &Rect2D) -> bool {
 662         return a.x >= b.x
 663             && a.y >= b.y
 664             && a.x + a.width <= b.x + b.width
 665             && a.y + a.height <= b.y + b.height;
 666     }
 667
 668     /// returns 0 if the two intervals i1 and i2 are disjoint, or the length of their
 669     /// overlap otherwise.
 670     fn get_common_interval_len(
 671         &self,
 672         i1_start: i32,
 673         i1_end: i32,
 674         i2_start: i32,
 675         i2_end: i32,
 676     ) -> i32 {
 677         if i1_end < i2_start || i2_end < i1_start {
 678             return 0;
 679         }
 680
 681         return std::cmp::min(i1_end, i2_end) - std::cmp::max(i1_start, i2_start);
 682     }
 683 } // impl RectsBinPack
 684
 685 // unit tests:
 686 #[cfg(test)]
 687 mod tests {
 688     use super::*;
 689
 690     #[test]
 691     fn rect2d_basics() {
 692         let rect = Rect2D::new();
 693
 694         assert_eq!(rect.x, 0);
 695         assert_eq!(rect.y, 0);
 696         assert_eq!(rect.width, 0);
 697         assert_eq!(rect.height, 0);
 698
 699         let rect = Rect2D::with_details(2, 4, 16, 32).unwrap();
 700
 701         assert_eq!(rect.x, 2);
 702         assert_eq!(rect.y, 4);
 703         assert_eq!(rect.width, 16);
 704         assert_eq!(rect.height, 32);
 705
 706         assert_eq!(
 707             Rect2D::with_details(-1, 4, 16, 32).unwrap_err(),
 708             RectsBinPackError::InvalidArg
 709         );
 710         assert_eq!(
 711             Rect2D::with_details(0, -1, 16, 32).unwrap_err(),
 712             RectsBinPackError::InvalidArg
 713         );
 714         assert_eq!(
 715             Rect2D::with_details(0, 0, 0, 32).unwrap_err(),
 716             RectsBinPackError::InvalidArg
 717         );
 718         assert_eq!(
 719             Rect2D::with_details(2, 4, 16, 0).unwrap_err(),
 720             RectsBinPackError::InvalidArg
 721         );
 722         assert_eq!(
 723             Rect2D::with_details(-1, -1, 0, 0).unwrap_err(),
 724             RectsBinPackError::InvalidArg
 725         );
 726     }
 727
 728     #[test]
 729     fn rbp_invalid_arg() {
 730         assert_eq!(
 731             RectsBinPack::new(0, 0, false).unwrap_err(),
 732             RectsBinPackError::InvalidArg
 733         );
 734         assert_eq!(
 735             RectsBinPack::new(32, 0, false).unwrap_err(),
 736             RectsBinPackError::InvalidArg
 737         );
 738         assert_eq!(
 739             RectsBinPack::new(0, 32, false).unwrap_err(),
 740             RectsBinPackError::InvalidArg
 741         );
 742
 743         assert_eq!(
 744             RectsBinPack::new(0, 0, true).unwrap_err(),
 745             RectsBinPackError::InvalidArg
 746         );
 747         assert_eq!(
 748             RectsBinPack::new(32, 0, true).unwrap_err(),
 749             RectsBinPackError::InvalidArg
 750         );
 751         assert_eq!(
 752             RectsBinPack::new(0, 32, true).unwrap_err(),
 753             RectsBinPackError::InvalidArg
 754         );
 755     }
 756
 757     #[test]
 758     fn rbp_basics() {
 759         let mut rbp = RectsBinPack::new(32, 32, false).unwrap();
 760         assert_eq!(rbp.get_occupancy(), 0.0);
 761
 762         assert_eq!(
 763             rbp.insert(16, 16, FreeRectHeuristic::ShortSideFit)
 764                 .is_some(),
 765             true
 766         );
 767         assert_eq!(
 768             rbp.insert(16, 16, FreeRectHeuristic::LongSideFit).is_some(),
 769             true
 770         );
 771         assert_eq!(
 772             rbp.insert(16, 16, FreeRectHeuristic::AreaFit).is_some(),
 773             true
 774         );
 775         assert_eq!(
 776             rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(),
 777             true
 778         );
 779         assert_eq!(rbp.get_occupancy(), 1.0);
 780
 781         assert_eq!(
 782             rbp.insert(1, 1, FreeRectHeuristic::ContactPoint).is_none(),
 783             true
 784         );
 785     }
 786 }