A 3D bin packing algorithm in Rust

packit.rs

pub type V3 = [usize; 3];

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct PositionedVolume {
    dimensions: V3,
    position: V3,
}

// mutable stack of sub-containers, initialized with input container
// mutable vec of remaining items, initialized with all input items
// mutable vec of positioned items, initialized empty
// loop until eaither stack or vec is empty:
//  * take top sub-container of stack
//  * find item with minimum room_to_spare for current sub-container
//  * if item not found:
//      * discard current sub-container and continue to next one
//  * if item found:
//      * remove item from remaining items
//      * position item in sub-container and add to positioned items vec
//      * calculate 3 sub-containers carved out by item and add to stack
pub fn pack(items: &[V3], container: &V3) -> (Vec<PositionedVolume>, Vec<V3>) {
    let mut stack: Vec<PositionedVolume> = Vec::with_capacity(items.len() * 2 + 1);
    stack.push(PositionedVolume {
        dimensions: *container,
        position: [0, 0, 0],
    });

    let mut todo: Vec<Option<V3>> = items.into_iter().map(|&item| Option::Some(item)).collect();

    let mut positioned: Vec<PositionedVolume> = Vec::with_capacity(items.len());

    while let (Some(current), true) = (stack.pop(), positioned.len() < items.len()) {
        let item_opt = (&mut todo)
            .into_iter()
            .filter_map(|item_opt| {
                (&item_opt)
                    .and_then(|item| room_to_spare(&item, &current.dimensions))
                    .map(|rts| (item_opt, rts))
            })
            .min_by_key(|&(_, rts)| rts)
            .map(|(item_opt, _)| item_opt)
            .and_then(Option::take);
        if let Some(item) = item_opt {
            let p = place(&item, &current);
            for sub_container in remaining_spaces(&p, &current) {
                stack.push(sub_container);
            }
            positioned.push(p);
        }
    }

    let remaining = todo.into_iter().filter_map(|x| x).collect::<Vec<_>>();
    (positioned, remaining)
}

fn remaining_spaces(
    item: &PositionedVolume,
    container: &PositionedVolume,
) -> Vec<PositionedVolume> {
    // future optimization: split in descending order of axis' room to spare
    let (bottom, top) = split(container, 2, item.dimensions[2]);
    let (front, back) = split(&bottom, 1, item.dimensions[1]);
    let (_left, right) = split(&front, 0, item.dimensions[0]);

    vec![top, back, right]
}

fn split(
    pv: &PositionedVolume,
    axis_index: usize,
    at: usize,
) -> (PositionedVolume, PositionedVolume) {
    let mut first = *pv;
    first.dimensions[axis_index] = at;
    let mut second = *pv;
    second.dimensions[axis_index] -= at;
    second.position[axis_index] += at;
    (first, second)
}

fn place(item: &V3, sub_container: &PositionedVolume) -> PositionedVolume {
    PositionedVolume {
        dimensions: align(item, &sub_container.dimensions),
        position: sub_container.position,
    }
}

fn align(item: &V3, container: &V3) -> V3 {
    rotate(item, &rotation_indexes(container))
}

fn room_to_spare(item: &V3, container: &V3) -> Option<usize> {
    let mut i = *item;
    i.sort_unstable();
    let mut c = *container;
    c.sort_unstable();
    if (c[0] < i[0]) || (c[1] < i[1]) || (c[2] < i[2]) {
        Option::None
    } else {
        Option::Some((c[0] - i[0]).min(c[1] - i[1]).min(c[2] - i[2]))
    }
}

fn rotation_indexes(v: &V3) -> V3 {
    let mut ret = v.iter().enumerate().collect::<Vec<_>>();
    ret.sort_unstable_by_key(|&(_, x)| x);
    let mut ret = ret.into_iter().enumerate().collect::<Vec<_>>();
    ret.sort_unstable_by_key(|&(_, (i, _))| i);
    [ret[0].0, ret[1].0, ret[2].0]
}

fn rotate(item: &V3, rotation_index: &V3) -> V3 {
    [
        item[rotation_index[0]],
        item[rotation_index[1]],
        item[rotation_index[2]],
    ]
}

#[cfg(test)]
mod tests {
    use crate::{pack, rotation_indexes, V3};

    fn volume(v: &V3) -> usize {
        v[0] * v[1] * v[2]
    }

    #[test]
    fn test_pack() {
        let container = [16, 12, 8];
        let items = [
            [8, 8, 8],
            [4, 8, 8],
            [4, 8, 8],
            [4, 4, 4],
            [4, 4, 4],
            [4, 4, 4],
            [4, 4, 4],
            [4, 4, 4],
            [4, 4, 4],
            [4, 4, 4],
            [2, 2, 2],
            [2, 2, 2],
            [2, 2, 2],
            [2, 2, 2],
            [2, 2, 2],
            [2, 2, 2],
            [2, 2, 2],
            [2, 2, 2],
        ];

        let (packed, remaining) = pack(&items, &container);

        assert_eq!(volume(&container), items.iter().map(volume).sum());
        assert_eq!(packed.len(), items.len());
        assert!(remaining.is_empty());
    }

    #[test]
    fn test_rotation() {
        assert_eq!(rotation_indexes(&[1, 2, 3]), [0, 1, 2]);
        assert_eq!(rotation_indexes(&[3, 2, 1]), [2, 1, 0]);
        assert_eq!(rotation_indexes(&[3, 1, 2]), [2, 0, 1]);
        assert_eq!(rotation_indexes(&[2, 3, 1]), [1, 2, 0]);
    }
}