5 releases (1 stable)
2.0.0beta1  Jan 16, 2021 

1.0.0  Jul 14, 2020 
0.1.2  Jun 20, 2020 
0.1.1  Jun 20, 2020 
0.1.0  Jun 20, 2020 
28KB
419 lines
bin_packer_3d
This crate solves the problem of "fitting smaller boxes inside of a larger box" using a three dimensional fitting algorithm.
The algorithm orthogonally packs the all the items into a minimum number of bins by leveraging a First Fit Decreasing greedy strategy, along with rotational optimizations.
Usage:
use bin_packer_3d::bin::Bin;
use bin_packer_3d::item::Item;
use bin_packer_3d::packing_algorithm::packing_algorithm;
let deck = Item::new("deck", [2, 8, 12]);
let die = Item::new("die", [8, 8, 8]);
let items = vec![deck, deck, die, deck, deck];
let packed_items = packing_algorithm(Bin::new([8, 8, 12]), &items);
assert_eq!(packed_items, Ok(vec![vec!["deck", "deck", "deck", "deck"], vec!["die"]]));
Limitations:
This algorithm solves a constrained version of the 3D bin packing problem. As such, we have the following limitations:

The items we are packing, and the bins that we are packing them into, are limited to cuboid shapes.

The items we are packing can be rotated in any direction, with the limitation that each edge must be parallel to the corresponding bin edge.

As an NPHard problem, this algorithm does not attempt to find the optimal solution, but instead uses an approximation that runs with a time complexity of O(n^2)
Acknowledgements:
The algorithm leverages a rotational optimization when packing items which are less than half the length of a bin's side, as proposed in the paper titled "The ThreeDimensional Bin Packing Problem" (Martello, 1997), page 257: https://www.jstor.org/stable/pdf/223143.pdf
Dependencies
~270–720KB
~17K SLoC