rectangle_pack/
bin_section.rs

1use crate::packed_location::RotatedBy;
2use crate::{BoxSizeHeuristicFn, PackedLocation, RectToInsert, WidthHeightDepth};
3
4use core::{
5    cmp::Ordering,
6    fmt::{Debug, Display, Error as FmtError, Formatter},
7};
8
9mod overlaps;
10
11/// Given two sets of containers, which of these is the more suitable for our packing.
12///
13/// Useful when we're determining how to split up the remaining volume/area of a box/rectangle.
14///
15/// For example - we might deem it best to cut the remaining region vertically, or horizontally,
16/// or along the Z-axis.
17///
18/// This decision is based on the more suitable contains heuristic. We determine all 6 possible
19/// ways to divide up remaining space, sort them using the more suitable contains heuristic function
20/// and choose the best one.
21///
22/// Ordering::Greater means the first set of containers is better.
23/// Ordering::Less means the second set of containers is better.
24pub type ComparePotentialContainersFn =
25    dyn Fn([WidthHeightDepth; 3], [WidthHeightDepth; 3], &BoxSizeHeuristicFn) -> Ordering;
26
27/// Select the container that has the smallest box.
28///
29/// If there is a tie on the smallest boxes, select whichever also has the second smallest box.
30pub fn contains_smallest_box(
31    mut container1: [WidthHeightDepth; 3],
32    mut container2: [WidthHeightDepth; 3],
33    heuristic: &BoxSizeHeuristicFn,
34) -> Ordering {
35    container1.sort_by(|a, b| heuristic(*a).cmp(&heuristic(*b)));
36    container2.sort_by(|a, b| heuristic(*a).cmp(&heuristic(*b)));
37
38    match heuristic(container2[0]).cmp(&heuristic(container1[0])) {
39        Ordering::Equal => heuristic(container2[1]).cmp(&heuristic(container1[1])),
40        o => o,
41    }
42}
43
44/// A rectangular section within a target bin that takes up one or more layers
45#[derive(Debug, Eq, PartialEq, Copy, Clone, Default, Ord, PartialOrd)]
46pub struct BinSection {
47    pub(crate) x: u32,
48    pub(crate) y: u32,
49    pub(crate) z: u32,
50    pub(crate) whd: WidthHeightDepth,
51}
52
53/// An error while attempting to place a rectangle within a bin section;
54#[derive(Debug, Eq, PartialEq)]
55#[allow(missing_docs)]
56pub enum BinSectionError {
57    PlacementWiderThanBinSection,
58    PlacementTallerThanBinSection,
59    PlacementDeeperThanBinSection,
60}
61
62impl Display for BinSectionError {
63    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), FmtError> {
64        let err = match self {
65            BinSectionError::PlacementWiderThanBinSection => {
66                "Can not place a rectangle inside of a bin that is wider than that rectangle."
67            }
68            BinSectionError::PlacementTallerThanBinSection => {
69                "Can not place a rectangle inside of a bin that is taller than that rectangle."
70            }
71            BinSectionError::PlacementDeeperThanBinSection => {
72                "Can not place a rectangle inside of a bin that is deeper than that rectangle."
73            }
74        };
75
76        f.write_str(err)
77    }
78}
79
80impl BinSection {
81    /// Create a new BinSection
82    pub fn new(x: u32, y: u32, z: u32, whd: WidthHeightDepth) -> Self {
83        BinSection { x, y, z, whd }
84    }
85
86    // TODO: Delete - just the old API before we had the WidthHeightDepth struct
87    fn new_spread(x: u32, y: u32, z: u32, width: u32, height: u32, depth: u32) -> Self {
88        BinSection {
89            x,
90            y,
91            z,
92            whd: WidthHeightDepth {
93                width,
94                height,
95                depth,
96            },
97        }
98    }
99}
100
101impl BinSection {
102    /// See if a `LayeredRect` can fit inside of this BinSection.
103    ///
104    /// If it can we return the `BinSection`s that would be created by placing the `LayeredRect`
105    /// inside of this `BinSection`.
106    ///
107    /// Consider the diagram below of a smaller box placed into of a larger one.
108    ///
109    /// The remaining space can be divided into three new sections.
110    ///
111    /// There are several ways to make this division.
112    ///
113    /// You could keep all of the space above the smaller box intact and split up the space
114    /// behind and to the right of it.
115    ///
116    /// But within that you have a choice between whether the overlapping space goes to right
117    /// or behind box.
118    ///
119    /// Or you could keep the space to the right and split the top and behind space.
120    ///
121    /// etc.
122    ///
123    /// There are six possible configurations of newly created sections. The configuration to use
124    /// is decided on based on a a function provided by the consumer.
125    ///
126    ///
127    /// ```text
128    ///             ┌┬───────────────────┬┐
129    ///           ┌─┘│                 ┌─┘│
130    ///         ┌─┘  │               ┌─┘  │
131    ///       ┌─┘    │             ┌─┘    │
132    ///     ┌─┘      │           ┌─┘      │
133    ///   ┌─┘        │         ┌─┘        │
134    /// ┌─┴──────────┼───────┬─┘          │
135    /// │            │       │            │
136    /// │            │       │            │
137    /// │       ┌┬───┴────┬─┐│            │
138    /// │     ┌─┘│      ┌─┘ ││            │
139    /// │   ┌─┘  │    ┌─┘   ││            │
140    /// │ ┌─┘    │  ┌─┘     ├┼───────────┬┘
141    /// ├─┴──────┤ ─┘       ││         ┌─┘
142    /// │       ┌┴─┬───────┬┘│       ┌─┘   
143    /// │     ┌─┘  │     ┌─┘ │     ┌─┘     
144    /// │   ┌─┘    │   ┌─┘   │   ┌─┘       
145    /// │ ┌─┘      │ ┌─┘     │ ┌─┘         
146    /// └─┴────────┴─┴───────┴─┘           
147    /// ```
148    ///
149    /// # Note
150    ///
151    /// Written to be readable/maintainable, not to minimize conditional logic, under the
152    /// (unverified) assumption that a release compilation will inline and dedupe the function
153    /// calls and conditionals.
154    pub fn try_place(
155        &self,
156        incoming: &RectToInsert,
157        container_comparison_fn: &ComparePotentialContainersFn,
158        heuristic_fn: &BoxSizeHeuristicFn,
159    ) -> Result<(PackedLocation, [BinSection; 3]), BinSectionError> {
160        self.incoming_can_fit(incoming)?;
161
162        let mut all_combinations = [
163            self.depth_largest_height_second_largest_width_smallest(incoming),
164            self.depth_largest_width_second_largest_height_smallest(incoming),
165            self.height_largest_depth_second_largest_width_smallest(incoming),
166            self.height_largest_width_second_largest_depth_smallest(incoming),
167            self.width_largest_depth_second_largest_height_smallest(incoming),
168            self.width_largest_height_second_largest_depth_smallest(incoming),
169        ];
170
171        all_combinations.sort_by(|a, b| {
172            container_comparison_fn(
173                [a[0].whd, a[1].whd, a[2].whd],
174                [b[0].whd, b[1].whd, b[2].whd],
175                heuristic_fn,
176            )
177        });
178
179        let packed_location = PackedLocation {
180            x: self.x,
181            y: self.y,
182            z: self.z,
183            whd: WidthHeightDepth {
184                width: incoming.width(),
185                height: incoming.height(),
186                depth: incoming.depth(),
187            },
188            x_axis_rotation: RotatedBy::ZeroDegrees,
189            y_axis_rotation: RotatedBy::ZeroDegrees,
190            z_axis_rotation: RotatedBy::ZeroDegrees,
191        };
192
193        Ok((packed_location, all_combinations[5]))
194    }
195
196    fn incoming_can_fit(&self, incoming: &RectToInsert) -> Result<(), BinSectionError> {
197        if incoming.width() > self.whd.width {
198            return Err(BinSectionError::PlacementWiderThanBinSection);
199        }
200        if incoming.height() > self.whd.height {
201            return Err(BinSectionError::PlacementTallerThanBinSection);
202        }
203
204        if incoming.depth() > self.whd.depth {
205            return Err(BinSectionError::PlacementDeeperThanBinSection);
206        }
207
208        Ok(())
209    }
210
211    fn width_largest_height_second_largest_depth_smallest(
212        &self,
213        incoming: &RectToInsert,
214    ) -> [BinSection; 3] {
215        [
216            self.empty_space_directly_right(incoming),
217            self.all_empty_space_above_excluding_behind(incoming),
218            self.all_empty_space_behind(incoming),
219        ]
220    }
221
222    fn width_largest_depth_second_largest_height_smallest(
223        &self,
224        incoming: &RectToInsert,
225    ) -> [BinSection; 3] {
226        [
227            self.empty_space_directly_right(incoming),
228            self.all_empty_space_above(incoming),
229            self.all_empty_space_behind_excluding_above(incoming),
230        ]
231    }
232
233    fn height_largest_width_second_largest_depth_smallest(
234        &self,
235        incoming: &RectToInsert,
236    ) -> [BinSection; 3] {
237        [
238            self.all_empty_space_right_excluding_behind(incoming),
239            self.empty_space_directly_above(incoming),
240            self.all_empty_space_behind(incoming),
241        ]
242    }
243
244    fn height_largest_depth_second_largest_width_smallest(
245        &self,
246        incoming: &RectToInsert,
247    ) -> [BinSection; 3] {
248        [
249            self.all_empty_space_right(incoming),
250            self.empty_space_directly_above(incoming),
251            self.all_empty_space_behind_excluding_right(incoming),
252        ]
253    }
254
255    fn depth_largest_width_second_largest_height_smallest(
256        &self,
257        incoming: &RectToInsert,
258    ) -> [BinSection; 3] {
259        [
260            self.all_empty_space_right_excluding_above(incoming),
261            self.all_empty_space_above(incoming),
262            self.empty_space_directly_behind(incoming),
263        ]
264    }
265
266    fn depth_largest_height_second_largest_width_smallest(
267        &self,
268        incoming: &RectToInsert,
269    ) -> [BinSection; 3] {
270        [
271            self.all_empty_space_right(incoming),
272            self.all_empty_space_above_excluding_right(incoming),
273            self.empty_space_directly_behind(incoming),
274        ]
275    }
276
277    fn all_empty_space_above(&self, incoming: &RectToInsert) -> BinSection {
278        BinSection::new_spread(
279            self.x,
280            self.y + incoming.height(),
281            self.z,
282            self.whd.width,
283            self.whd.height - incoming.height(),
284            self.whd.depth,
285        )
286    }
287
288    fn all_empty_space_right(&self, incoming: &RectToInsert) -> BinSection {
289        BinSection::new_spread(
290            self.x + incoming.width(),
291            self.y,
292            self.z,
293            self.whd.width - incoming.width(),
294            self.whd.height,
295            self.whd.depth,
296        )
297    }
298
299    fn all_empty_space_behind(&self, incoming: &RectToInsert) -> BinSection {
300        BinSection::new_spread(
301            self.x,
302            self.y,
303            self.z + incoming.depth(),
304            self.whd.width,
305            self.whd.height,
306            self.whd.depth - incoming.depth(),
307        )
308    }
309
310    fn empty_space_directly_above(&self, incoming: &RectToInsert) -> BinSection {
311        BinSection::new_spread(
312            self.x,
313            self.y + incoming.height(),
314            self.z,
315            incoming.width(),
316            self.whd.height - incoming.height(),
317            incoming.depth(),
318        )
319    }
320
321    fn empty_space_directly_right(&self, incoming: &RectToInsert) -> BinSection {
322        BinSection::new_spread(
323            self.x + incoming.width(),
324            self.y,
325            self.z,
326            self.whd.width - incoming.width(),
327            incoming.height(),
328            incoming.depth(),
329        )
330    }
331
332    fn empty_space_directly_behind(&self, incoming: &RectToInsert) -> BinSection {
333        BinSection::new(
334            self.x,
335            self.y,
336            self.z + incoming.depth(),
337            WidthHeightDepth {
338                width: incoming.width(),
339                height: incoming.height(),
340                depth: self.whd.depth - incoming.depth(),
341            },
342        )
343    }
344
345    fn all_empty_space_above_excluding_right(&self, incoming: &RectToInsert) -> BinSection {
346        BinSection::new(
347            self.x,
348            self.y + incoming.height(),
349            self.z,
350            WidthHeightDepth {
351                width: incoming.width(),
352                height: self.whd.height - incoming.height(),
353                depth: self.whd.depth,
354            },
355        )
356    }
357
358    fn all_empty_space_above_excluding_behind(&self, incoming: &RectToInsert) -> BinSection {
359        BinSection::new(
360            self.x,
361            self.y + incoming.height(),
362            self.z,
363            WidthHeightDepth {
364                width: self.whd.width,
365                height: self.whd.height - incoming.height(),
366                depth: incoming.depth(),
367            },
368        )
369    }
370
371    fn all_empty_space_right_excluding_above(&self, incoming: &RectToInsert) -> BinSection {
372        BinSection::new(
373            self.x + incoming.width(),
374            self.y,
375            self.z,
376            WidthHeightDepth {
377                width: self.whd.width - incoming.width(),
378                height: incoming.height(),
379                depth: self.whd.depth,
380            },
381        )
382    }
383
384    fn all_empty_space_right_excluding_behind(&self, incoming: &RectToInsert) -> BinSection {
385        BinSection::new(
386            self.x + incoming.width(),
387            self.y,
388            self.z,
389            WidthHeightDepth {
390                width: self.whd.width - incoming.width(),
391                height: self.whd.height,
392                depth: incoming.depth(),
393            },
394        )
395    }
396
397    fn all_empty_space_behind_excluding_above(&self, incoming: &RectToInsert) -> BinSection {
398        BinSection::new(
399            self.x,
400            self.y,
401            self.z + incoming.depth(),
402            WidthHeightDepth {
403                width: self.whd.width,
404                height: incoming.height(),
405                depth: self.whd.depth - incoming.depth(),
406            },
407        )
408    }
409
410    fn all_empty_space_behind_excluding_right(&self, incoming: &RectToInsert) -> BinSection {
411        BinSection::new(
412            self.x,
413            self.y,
414            self.z + incoming.depth(),
415            WidthHeightDepth {
416                width: incoming.width(),
417                height: self.whd.height,
418                depth: self.whd.depth - incoming.depth(),
419            },
420        )
421    }
422}
423
424#[cfg(test)]
425mod tests {
426    use super::*;
427    use crate::{volume_heuristic, RectToInsert};
428
429    const BIGGEST: u32 = 50;
430    const MIDDLE: u32 = 25;
431    const SMALLEST: u32 = 10;
432
433    const FULL: u32 = 100;
434
435    /// If we're trying to place a rectangle that is wider than the container we return an error
436    #[test]
437    fn error_if_placement_is_wider_than_bin_section() {
438        let bin_section = bin_section_width_height_depth(5, 20, 1);
439        let placement = RectToInsert::new(6, 20, 1);
440
441        assert_eq!(
442            bin_section
443                .try_place(&placement, &contains_smallest_box, &volume_heuristic)
444                .unwrap_err(),
445            BinSectionError::PlacementWiderThanBinSection
446        );
447    }
448
449    /// If we're trying to place a rectangle that is taller than the container we return an error
450    #[test]
451    fn error_if_placement_is_taller_than_bin_section() {
452        let bin_section = bin_section_width_height_depth(5, 20, 1);
453        let placement = RectToInsert::new(5, 21, 1);
454
455        assert_eq!(
456            bin_section
457                .try_place(&placement, &contains_smallest_box, &volume_heuristic)
458                .unwrap_err(),
459            BinSectionError::PlacementTallerThanBinSection
460        );
461    }
462
463    /// If we're trying to place a rectangle that is deeper than the container we return an error
464    #[test]
465    fn error_if_placement_is_deeper_than_bin_section() {
466        let bin_section = bin_section_width_height_depth(5, 20, 1);
467        let placement = RectToInsert::new(5, 20, 2);
468
469        assert_eq!(
470            bin_section
471                .try_place(&placement, &contains_smallest_box, &volume_heuristic)
472                .unwrap_err(),
473            BinSectionError::PlacementDeeperThanBinSection
474        );
475    }
476
477    fn test_splits(
478        container_dimensions: u32,
479        rect_to_place: WidthHeightDepth,
480        mut expected: [BinSection; 3],
481    ) {
482        let dim = container_dimensions;
483        let bin_section = bin_section_width_height_depth(dim, dim, dim);
484
485        let whd = rect_to_place;
486
487        let placement = RectToInsert::new(whd.width, whd.height, whd.depth);
488
489        let mut packed = bin_section
490            .try_place(&placement, &contains_smallest_box, &volume_heuristic)
491            .unwrap();
492
493        packed.1.sort();
494        expected.sort();
495
496        assert_eq!(packed.1, expected);
497    }
498
499    /// Verify that we choose the correct splits when the placed rectangle is width > height > depth
500    #[test]
501    fn width_largest_height_second_largest_depth_smallest() {
502        let whd = WidthHeightDepth {
503            width: BIGGEST,
504            height: MIDDLE,
505            depth: SMALLEST,
506        };
507
508        test_splits(
509            FULL,
510            whd,
511            [
512                BinSection::new_spread(whd.width, 0, 0, FULL - whd.width, whd.height, whd.depth),
513                BinSection::new_spread(0, whd.height, 0, FULL, FULL - whd.height, whd.depth),
514                BinSection::new_spread(0, 0, whd.depth, FULL, FULL, FULL - whd.depth),
515            ],
516        );
517    }
518
519    /// Verify that we choose the correct splits when the placed rectangle is width > depth > height
520    #[test]
521    fn width_largest_depth_second_largest_height_smallest() {
522        let whd = WidthHeightDepth {
523            width: BIGGEST,
524            height: SMALLEST,
525            depth: MIDDLE,
526        };
527
528        test_splits(
529            FULL,
530            whd,
531            [
532                BinSection::new_spread(whd.width, 0, 0, FULL - whd.width, whd.height, whd.depth),
533                BinSection::new_spread(0, whd.height, 0, FULL, FULL - whd.height, FULL),
534                BinSection::new_spread(0, 0, whd.depth, FULL, whd.height, FULL - whd.depth),
535            ],
536        );
537    }
538
539    /// Verify that we choose the correct splits when the placed rectangle is height > width > depth
540    #[test]
541    fn height_largest_width_second_largest_depth_smallest() {
542        let whd = WidthHeightDepth {
543            width: MIDDLE,
544            height: BIGGEST,
545            depth: SMALLEST,
546        };
547
548        test_splits(
549            FULL,
550            whd,
551            [
552                BinSection::new_spread(whd.width, 0, 0, FULL - whd.width, FULL, whd.depth),
553                BinSection::new_spread(0, whd.height, 0, whd.width, FULL - whd.height, whd.depth),
554                BinSection::new_spread(0, 0, whd.depth, FULL, FULL, FULL - whd.depth),
555            ],
556        );
557    }
558
559    /// Verify that we choose the correct splits when the placed rectangle is height > depth > width
560    #[test]
561    fn height_largest_depth_second_largest_width_smallest() {
562        let whd = WidthHeightDepth {
563            width: SMALLEST,
564            height: BIGGEST,
565            depth: MIDDLE,
566        };
567
568        test_splits(
569            FULL,
570            whd,
571            [
572                BinSection::new_spread(whd.width, 0, 0, FULL - whd.width, FULL, FULL),
573                BinSection::new_spread(0, whd.height, 0, whd.width, FULL - whd.height, whd.depth),
574                BinSection::new_spread(0, 0, whd.depth, whd.width, FULL, FULL - whd.depth),
575            ],
576        );
577    }
578
579    /// Verify that we choose the correct splits when the placed rectangle is depth > width > height
580    #[test]
581    fn depth_largest_width_second_largest_height_smallest() {
582        let whd = WidthHeightDepth {
583            width: MIDDLE,
584            height: SMALLEST,
585            depth: BIGGEST,
586        };
587
588        test_splits(
589            FULL,
590            whd,
591            [
592                BinSection::new_spread(whd.width, 0, 0, FULL - whd.width, whd.height, FULL),
593                BinSection::new_spread(0, whd.height, 0, FULL, FULL - whd.height, FULL),
594                BinSection::new_spread(0, 0, whd.depth, whd.width, whd.height, FULL - whd.depth),
595            ],
596        );
597    }
598
599    /// Verify that we choose the correct splits when the placed rectangle is depth > height > width
600    #[test]
601    fn depth_largest_height_second_largest_width_smallest() {
602        let whd = WidthHeightDepth {
603            width: SMALLEST,
604            height: MIDDLE,
605            depth: BIGGEST,
606        };
607
608        test_splits(
609            FULL,
610            whd,
611            [
612                BinSection::new_spread(whd.width, 0, 0, FULL - whd.width, FULL, FULL),
613                BinSection::new_spread(0, whd.height, 0, whd.width, FULL - whd.height, FULL),
614                BinSection::new_spread(0, 0, whd.depth, whd.width, whd.height, FULL - whd.depth),
615            ],
616        );
617    }
618
619    // #[test]
620    // fn todo() {
621    //    unimplemented!("Add tests for supporting rotation");
622    // }
623
624    fn bin_section_width_height_depth(width: u32, height: u32, depth: u32) -> BinSection {
625        BinSection::new(
626            0,
627            0,
628            0,
629            WidthHeightDepth {
630                width,
631                height,
632                depth,
633            },
634        )
635    }
636}
rectangle_pack/bin_section.rs

rectangle_pack/
bin_section.rs
