#![deny(missing_docs)]
use std::collections::{BTreeMap, HashMap};
use std::fmt::{Debug, Display, Formatter};
use std::hash::Hash;
pub use crate::bin_section::contains_smallest_box;
use crate::bin_section::BinSection;
pub use crate::bin_section::ComparePotentialContainersFn;
use crate::grouped_rects_to_place::Group;
pub use crate::grouped_rects_to_place::GroupedRectsToPlace;
pub use crate::target_bin::TargetBin;
use crate::width_height_depth::WidthHeightDepth;
pub use self::box_size_heuristics::{volume_heuristic, BoxSizeHeuristicFn};
pub use self::rect_to_insert::RectToInsert;
pub use crate::packed_location::PackedLocation;
mod bin_section;
mod grouped_rects_to_place;
mod packed_location;
mod rect_to_insert;
mod target_bin;
mod width_height_depth;
mod box_size_heuristics;
pub fn pack_rects<
RectToPlaceId: Debug + Hash + PartialEq + Eq + Clone + Ord + PartialOrd,
BinId: Debug + Hash + PartialEq + Eq + Clone + Ord + PartialOrd,
GroupId: Debug + Hash + PartialEq + Eq + Clone + Ord + PartialOrd,
>(
rects_to_place: &GroupedRectsToPlace<RectToPlaceId, GroupId>,
target_bins: BTreeMap<BinId, TargetBin>,
box_size_heuristic: &BoxSizeHeuristicFn,
more_suitable_containers_fn: &ComparePotentialContainersFn,
) -> Result<RectanglePackOk<RectToPlaceId, BinId>, RectanglePackError> {
let mut packed_locations = HashMap::new();
let mut target_bins: Vec<(BinId, TargetBin)> = target_bins.into_iter().collect();
sort_bins_smallest_to_largest(&mut target_bins, box_size_heuristic);
let mut group_id_to_inbound_ids: Vec<(&Group<GroupId, RectToPlaceId>, &Vec<RectToPlaceId>)> =
rects_to_place.group_id_to_inbound_ids.iter().collect();
sort_groups_largest_to_smallest(
&mut group_id_to_inbound_ids,
rects_to_place,
box_size_heuristic,
);
'group: for (_group_id, rects_to_place_ids) in group_id_to_inbound_ids {
for (bin_id, bin) in target_bins.iter_mut() {
if !can_fit_entire_group_into_bin(
bin.clone(),
&rects_to_place_ids[..],
rects_to_place,
box_size_heuristic,
more_suitable_containers_fn,
) {
continue;
}
'incoming: for rect_to_place_id in rects_to_place_ids.iter() {
if bin.remaining_sections.len() == 0 {
continue;
}
let _bin_clone = bin.clone();
let mut bin_sections = bin.remaining_sections.clone();
let last_section_idx = bin_sections.len() - 1;
let mut sections_tried = 0;
'section: while let Some(remaining_section) = bin_sections.pop() {
let rect_to_place = rects_to_place.rects[&rect_to_place_id];
let placement = remaining_section.try_place(
&rect_to_place,
more_suitable_containers_fn,
box_size_heuristic,
);
if placement.is_err() {
sections_tried += 1;
continue 'section;
}
let (placement, mut new_sections) = placement.unwrap();
sort_by_size_largest_to_smallest(&mut new_sections, box_size_heuristic);
bin.remove_filled_section(last_section_idx - sections_tried);
bin.add_new_sections(new_sections);
packed_locations.insert(rect_to_place_id.clone(), (bin_id.clone(), placement));
continue 'incoming;
}
}
continue 'group;
}
return Err(RectanglePackError::NotEnoughBinSpace);
}
Ok(RectanglePackOk { packed_locations })
}
fn can_fit_entire_group_into_bin<RectToPlaceId, GroupId>(
mut bin: TargetBin,
group: &[RectToPlaceId],
rects_to_place: &GroupedRectsToPlace<RectToPlaceId, GroupId>,
box_size_heuristic: &BoxSizeHeuristicFn,
more_suitable_containers_fn: &ComparePotentialContainersFn,
) -> bool
where
RectToPlaceId: Debug + Hash + PartialEq + Eq + Clone + Ord + PartialOrd,
GroupId: Debug + Hash + PartialEq + Eq + Clone + Ord + PartialOrd,
{
'incoming: for rect_to_place_id in group.iter() {
if bin.remaining_sections.len() == 0 {
return false;
}
let mut bin_sections = bin.remaining_sections.clone();
let last_section_idx = bin_sections.len() - 1;
let mut sections_tried = 0;
'section: while let Some(remaining_section) = bin_sections.pop() {
let rect_to_place = rects_to_place.rects[&rect_to_place_id];
let placement = remaining_section.try_place(
&rect_to_place,
more_suitable_containers_fn,
box_size_heuristic,
);
if placement.is_err() {
sections_tried += 1;
continue 'section;
}
let (_placement, mut new_sections) = placement.unwrap();
sort_by_size_largest_to_smallest(&mut new_sections, box_size_heuristic);
bin.remove_filled_section(last_section_idx - sections_tried);
bin.add_new_sections(new_sections);
continue 'incoming;
}
return false;
}
true
}
#[derive(Debug, PartialEq)]
pub struct RectanglePackOk<RectToPlaceId: PartialEq + Eq + Hash, BinId: PartialEq + Eq + Hash> {
packed_locations: HashMap<RectToPlaceId, (BinId, PackedLocation)>,
}
impl<RectToPlaceId: PartialEq + Eq + Hash, BinId: PartialEq + Eq + Hash>
RectanglePackOk<RectToPlaceId, BinId>
{
pub fn packed_locations(&self) -> &HashMap<RectToPlaceId, (BinId, PackedLocation)> {
&self.packed_locations
}
}
#[derive(Debug, PartialEq)]
pub enum RectanglePackError {
NotEnoughBinSpace,
}
impl Display for RectanglePackError {
fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), std::fmt::Error> {
match self {
RectanglePackError::NotEnoughBinSpace => {
f.write_str("Not enough space to place all of the rectangles.")
}
}
}
}
impl std::error::Error for RectanglePackError {}
fn sort_bins_smallest_to_largest<BinId>(
bins: &mut Vec<(BinId, TargetBin)>,
box_size_heuristic: &BoxSizeHeuristicFn,
) where
BinId: Debug + Hash + PartialEq + Eq + Clone,
{
bins.sort_by(|a, b| {
box_size_heuristic(WidthHeightDepth {
width: a.1.max_width,
height: a.1.max_height,
depth: a.1.max_depth,
})
.cmp(&box_size_heuristic(WidthHeightDepth {
width: b.1.max_width,
height: b.1.max_height,
depth: b.1.max_depth,
}))
});
}
fn sort_by_size_largest_to_smallest(
items: &mut [BinSection; 3],
box_size_heuristic: &BoxSizeHeuristicFn,
) {
items.sort_by(|a, b| box_size_heuristic(b.whd).cmp(&box_size_heuristic(a.whd)));
}
fn sort_groups_largest_to_smallest<GroupId, RectToPlaceId>(
group_id_to_inbound_ids: &mut Vec<(&Group<GroupId, RectToPlaceId>, &Vec<RectToPlaceId>)>,
incoming_groups: &GroupedRectsToPlace<RectToPlaceId, GroupId>,
box_size_heuristic: &BoxSizeHeuristicFn,
) where
RectToPlaceId: Debug + Hash + PartialEq + Eq + Clone + Ord + PartialOrd,
GroupId: Debug + Hash + PartialEq + Eq + Clone + Ord + PartialOrd,
{
group_id_to_inbound_ids.sort_by(|a, b| {
let a_heuristic =
a.1.iter()
.map(|inbound| {
let rect = incoming_groups.rects[inbound];
box_size_heuristic(rect.whd)
})
.sum();
let b_heuristic: u128 =
b.1.iter()
.map(|inbound| {
let rect = incoming_groups.rects[inbound];
box_size_heuristic(rect.whd)
})
.sum();
b_heuristic.cmp(&a_heuristic)
});
}
#[cfg(test)]
mod tests {
use crate::{pack_rects, volume_heuristic, RectToInsert, RectanglePackError, TargetBin};
use super::*;
use crate::packed_location::RotatedBy;
use std::path::PathBuf;
#[test]
fn error_if_the_rectangles_cannot_fit_into_target_bins() {
let mut targets = BTreeMap::new();
targets.insert(BinId::Three, TargetBin::new(2, 100, 1));
let mut groups: GroupedRectsToPlace<_, ()> = GroupedRectsToPlace::new();
groups.push_rect(RectToPlaceId::One, None, RectToInsert::new(3, 1, 1));
match pack_rects(&groups, targets, &volume_heuristic, &contains_smallest_box).unwrap_err() {
RectanglePackError::NotEnoughBinSpace => {}
};
}
#[test]
fn error_if_cannot_fit_group() {
let mut targets = BTreeMap::new();
targets.insert(BinId::Three, TargetBin::new(100, 100, 1));
targets.insert(BinId::Four, TargetBin::new(100, 100, 1));
let mut groups = GroupedRectsToPlace::new();
groups.push_rect(
RectToPlaceId::One,
Some(vec!["A Group"]),
RectToInsert::new(100, 100, 1),
);
groups.push_rect(
RectToPlaceId::Two,
Some(vec!["A Group"]),
RectToInsert::new(100, 100, 1),
);
match pack_rects(&groups, targets, &volume_heuristic, &contains_smallest_box).unwrap_err() {
RectanglePackError::NotEnoughBinSpace => {}
};
}
#[test]
fn one_inbound_rect_one_bin() {
let mut groups: GroupedRectsToPlace<_, ()> = GroupedRectsToPlace::new();
groups.push_rect(RectToPlaceId::One, None, RectToInsert::new(1, 2, 1));
let mut targets = BTreeMap::new();
targets.insert(BinId::Three, TargetBin::new(5, 5, 1));
let packed =
pack_rects(&groups, targets, &volume_heuristic, &contains_smallest_box).unwrap();
let locations = packed.packed_locations;
assert_eq!(locations.len(), 1);
assert_eq!(locations[&RectToPlaceId::One].0, BinId::Three,);
assert_eq!(
locations[&RectToPlaceId::One].1,
PackedLocation {
x: 0,
y: 0,
z: 0,
whd: WidthHeightDepth {
width: 1,
height: 2,
depth: 1
},
x_axis_rotation: RotatedBy::ZeroDegrees,
y_axis_rotation: RotatedBy::ZeroDegrees,
z_axis_rotation: RotatedBy::ZeroDegrees,
}
)
}
#[test]
fn one_inbound_rect_two_bins() {
let mut groups: GroupedRectsToPlace<_, ()> = GroupedRectsToPlace::new();
groups.push_rect(RectToPlaceId::One, None, RectToInsert::new(2, 2, 1));
let mut targets = BTreeMap::new();
targets.insert(BinId::Three, TargetBin::new(5, 5, 1));
targets.insert(BinId::Four, TargetBin::new(5, 5, 2));
let packed =
pack_rects(&groups, targets, &volume_heuristic, &contains_smallest_box).unwrap();
let locations = packed.packed_locations;
assert_eq!(locations[&RectToPlaceId::One].0, BinId::Three,);
assert_eq!(locations.len(), 1);
assert_eq!(
locations[&RectToPlaceId::One].1,
PackedLocation {
x: 0,
y: 0,
z: 0,
whd: WidthHeightDepth {
width: 2,
height: 2,
depth: 1
},
x_axis_rotation: RotatedBy::ZeroDegrees,
y_axis_rotation: RotatedBy::ZeroDegrees,
z_axis_rotation: RotatedBy::ZeroDegrees,
}
)
}
#[test]
fn places_largest_rectangles_first() {
let mut groups: GroupedRectsToPlace<_, ()> = GroupedRectsToPlace::new();
groups.push_rect(RectToPlaceId::One, None, RectToInsert::new(10, 10, 1));
groups.push_rect(RectToPlaceId::Two, None, RectToInsert::new(5, 5, 1));
let mut targets = BTreeMap::new();
targets.insert(BinId::Three, TargetBin::new(20, 20, 2));
let packed =
pack_rects(&groups, targets, &volume_heuristic, &contains_smallest_box).unwrap();
let locations = packed.packed_locations;
assert_eq!(locations.len(), 2);
assert_eq!(locations[&RectToPlaceId::One].0, BinId::Three,);
assert_eq!(locations[&RectToPlaceId::Two].0, BinId::Three,);
assert_eq!(
locations[&RectToPlaceId::One].1,
PackedLocation {
x: 0,
y: 0,
z: 0,
whd: WidthHeightDepth {
width: 10,
height: 10,
depth: 1
},
x_axis_rotation: RotatedBy::ZeroDegrees,
y_axis_rotation: RotatedBy::ZeroDegrees,
z_axis_rotation: RotatedBy::ZeroDegrees,
}
);
assert_eq!(
locations[&RectToPlaceId::Two].1,
PackedLocation {
x: 10,
y: 0,
z: 0,
whd: WidthHeightDepth {
width: 5,
height: 5,
depth: 1
},
x_axis_rotation: RotatedBy::ZeroDegrees,
y_axis_rotation: RotatedBy::ZeroDegrees,
z_axis_rotation: RotatedBy::ZeroDegrees,
}
)
}
#[test]
fn two_rects_two_bins() {
let mut groups: GroupedRectsToPlace<_, ()> = GroupedRectsToPlace::new();
groups.push_rect(RectToPlaceId::One, None, RectToInsert::new(15, 15, 1));
groups.push_rect(RectToPlaceId::Two, None, RectToInsert::new(20, 20, 1));
let mut targets = BTreeMap::new();
targets.insert(BinId::Three, TargetBin::new(20, 20, 1));
targets.insert(BinId::Four, TargetBin::new(50, 50, 1));
let packed =
pack_rects(&groups, targets, &volume_heuristic, &contains_smallest_box).unwrap();
let locations = packed.packed_locations;
assert_eq!(locations.len(), 2);
assert_eq!(locations[&RectToPlaceId::One].0, BinId::Four,);
assert_eq!(locations[&RectToPlaceId::Two].0, BinId::Three,);
assert_eq!(
locations[&RectToPlaceId::One].1,
PackedLocation {
x: 0,
y: 0,
z: 0,
whd: WidthHeightDepth {
width: 15,
height: 15,
depth: 1
},
x_axis_rotation: RotatedBy::ZeroDegrees,
y_axis_rotation: RotatedBy::ZeroDegrees,
z_axis_rotation: RotatedBy::ZeroDegrees,
}
);
assert_eq!(
locations[&RectToPlaceId::Two].1,
PackedLocation {
x: 0,
y: 0,
z: 0,
whd: WidthHeightDepth {
width: 20,
height: 20,
depth: 1
},
x_axis_rotation: RotatedBy::ZeroDegrees,
y_axis_rotation: RotatedBy::ZeroDegrees,
z_axis_rotation: RotatedBy::ZeroDegrees,
}
)
}
#[test]
fn fills_small_sections_before_large_ones() {
let mut targets = BTreeMap::new();
targets.insert(BinId::Three, TargetBin::new(100, 100, 1));
let mut groups: GroupedRectsToPlace<_, ()> = GroupedRectsToPlace::new();
groups.push_rect(RectToPlaceId::One, None, RectToInsert::new(50, 90, 1));
groups.push_rect(RectToPlaceId::Two, None, RectToInsert::new(1, 1, 1));
let packed =
pack_rects(&groups, targets, &volume_heuristic, &contains_smallest_box).unwrap();
let locations = packed.packed_locations;
assert_eq!(locations.len(), 2);
assert_eq!(locations[&RectToPlaceId::One].0, BinId::Three,);
assert_eq!(locations[&RectToPlaceId::Two].0, BinId::Three,);
assert_eq!(
locations[&RectToPlaceId::One].1,
PackedLocation {
x: 0,
y: 0,
z: 0,
whd: WidthHeightDepth {
width: 50,
height: 90,
depth: 1
},
x_axis_rotation: RotatedBy::ZeroDegrees,
y_axis_rotation: RotatedBy::ZeroDegrees,
z_axis_rotation: RotatedBy::ZeroDegrees,
}
);
assert_eq!(
locations[&RectToPlaceId::Two].1,
PackedLocation {
x: 0,
y: 90,
z: 0,
whd: WidthHeightDepth {
width: 1,
height: 1,
depth: 1
},
x_axis_rotation: RotatedBy::ZeroDegrees,
y_axis_rotation: RotatedBy::ZeroDegrees,
z_axis_rotation: RotatedBy::ZeroDegrees,
}
);
}
#[test]
fn saves_bin_sections_for_future_use() {
let mut targets = BTreeMap::new();
targets.insert(BinId::Three, TargetBin::new(100, 100, 1));
let mut groups: GroupedRectsToPlace<_, ()> = GroupedRectsToPlace::new();
groups.push_rect(RectToPlaceId::One, None, RectToInsert::new(60, 95, 1));
groups.push_rect(RectToPlaceId::Two, None, RectToInsert::new(40, 10, 1));
groups.push_rect(RectToPlaceId::Three, None, RectToInsert::new(60, 3, 1));
let packed =
pack_rects(&groups, targets, &volume_heuristic, &contains_smallest_box).unwrap();
let locations = packed.packed_locations;
assert_eq!(
locations[&RectToPlaceId::One].1,
PackedLocation {
x: 0,
y: 0,
z: 0,
whd: WidthHeightDepth {
width: 60,
height: 95,
depth: 1
},
x_axis_rotation: RotatedBy::ZeroDegrees,
y_axis_rotation: RotatedBy::ZeroDegrees,
z_axis_rotation: RotatedBy::ZeroDegrees,
}
);
assert_eq!(
locations[&RectToPlaceId::Two].1,
PackedLocation {
x: 60,
y: 0,
z: 0,
whd: WidthHeightDepth {
width: 40,
height: 10,
depth: 1
},
x_axis_rotation: RotatedBy::ZeroDegrees,
y_axis_rotation: RotatedBy::ZeroDegrees,
z_axis_rotation: RotatedBy::ZeroDegrees,
}
);
assert_eq!(
locations[&RectToPlaceId::Three].1,
PackedLocation {
x: 0,
y: 95,
z: 0,
whd: WidthHeightDepth {
width: 60,
height: 3,
depth: 1
},
x_axis_rotation: RotatedBy::ZeroDegrees,
y_axis_rotation: RotatedBy::ZeroDegrees,
z_axis_rotation: RotatedBy::ZeroDegrees,
}
);
}
#[test]
fn deterministic_packing() {
let mut previous_packed = None;
for _ in 0..5 {
let mut rects_to_place: GroupedRectsToPlace<PathBuf, &str> = GroupedRectsToPlace::new();
let mut target_bins = BTreeMap::new();
for bin_id in 0..5 {
target_bins.insert(bin_id, TargetBin::new(8, 8, 1));
}
let rectangles = vec![
"some-rectangle-0",
"some-rectangle-1",
"some-rectangle-2",
"some-rectangle-3",
"some-rectangle-4",
];
for rect_id in rectangles.iter() {
rects_to_place.push_rect(PathBuf::from(rect_id), None, RectToInsert::new(4, 4, 1));
}
let packed = pack_rects(
&rects_to_place,
target_bins.clone(),
&volume_heuristic,
&contains_smallest_box,
)
.unwrap();
if let Some(previous_packed) = previous_packed.as_ref() {
assert_eq!(&packed, previous_packed);
}
previous_packed = Some(packed);
}
}
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
enum RectToPlaceId {
One,
Two,
Three,
}
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
enum BinId {
Three,
Four,
}
}