hyperpack 0.2.0

Exact-aware packing carriers and feasibility replay for the Hyper ecosystem
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

//! Exact containment and no-overlap feasibility replay.

use std::collections::BTreeMap;

use hyperreal::{Real, RealSign};

use crate::{Bin3, Item3, ItemId, PackError, PackResult, Placement3};

/// Replay status for a proposed packing.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum FeasibilityStatus {
    /// All exact checks passed.
    Feasible,
    /// An exact containment or overlap check failed.
    Infeasible,
    /// A comparison could not be certified.
    Unknown,
}

/// Report from exact feasibility replay.
#[derive(Clone, Debug, PartialEq)]
pub struct FeasibilityReplay3 {
    /// Overall status.
    pub status: FeasibilityStatus,
    /// Number of containment checks.
    pub containment_checks: usize,
    /// Number of pairwise no-overlap checks.
    pub no_overlap_checks: usize,
    /// Human-readable facts.
    pub facts: Vec<String>,
}

impl FeasibilityReplay3 {
    /// Replays placements against exact bin containment and pairwise no-overlap.
    pub fn replay(bin: &Bin3, items: &[Item3], placements: &[Placement3]) -> PackResult<Self> {
        let item_map = items
            .iter()
            .map(|item| (item.id.clone(), item))
            .collect::<BTreeMap<ItemId, &Item3>>();
        let mut facts = Vec::new();
        let mut containment_checks = 0;
        let mut no_overlap_checks = 0;

        for placement in placements {
            let item = item_map
                .get(&placement.item)
                .ok_or(PackError::MissingItem)?;
            containment_checks += 1;
            match contains(bin, item, placement) {
                Some(true) => {}
                Some(false) => {
                    facts.push(format!("{} outside bin", placement.item.as_str()));
                    return Ok(Self {
                        status: FeasibilityStatus::Infeasible,
                        containment_checks,
                        no_overlap_checks,
                        facts,
                    });
                }
                None => {
                    return Ok(Self {
                        status: FeasibilityStatus::Unknown,
                        containment_checks,
                        no_overlap_checks,
                        facts,
                    });
                }
            }
        }

        for left_index in 0..placements.len() {
            for right_index in (left_index + 1)..placements.len() {
                let left = &placements[left_index];
                let right = &placements[right_index];
                let left_item = item_map.get(&left.item).ok_or(PackError::MissingItem)?;
                let right_item = item_map.get(&right.item).ok_or(PackError::MissingItem)?;
                no_overlap_checks += 1;
                match disjoint(left_item, left, right_item, right) {
                    Some(true) => {}
                    Some(false) => {
                        facts.push(format!(
                            "{} overlaps {}",
                            left.item.as_str(),
                            right.item.as_str()
                        ));
                        return Ok(Self {
                            status: FeasibilityStatus::Infeasible,
                            containment_checks,
                            no_overlap_checks,
                            facts,
                        });
                    }
                    None => {
                        return Ok(Self {
                            status: FeasibilityStatus::Unknown,
                            containment_checks,
                            no_overlap_checks,
                            facts,
                        });
                    }
                }
            }
        }

        Ok(Self {
            status: FeasibilityStatus::Feasible,
            containment_checks,
            no_overlap_checks,
            facts,
        })
    }
}

fn contains(bin: &Bin3, item: &Item3, placement: &Placement3) -> Option<bool> {
    Some(
        nonnegative(&placement.x)?
            && nonnegative(&placement.y)?
            && nonnegative(&placement.z)?
            && leq(&(placement.x.clone() + item.size.x.clone()), &bin.size.x)?
            && leq(&(placement.y.clone() + item.size.y.clone()), &bin.size.y)?
            && leq(&(placement.z.clone() + item.size.z.clone()), &bin.size.z)?,
    )
}

fn disjoint(
    left_item: &Item3,
    left: &Placement3,
    right_item: &Item3,
    right: &Placement3,
) -> Option<bool> {
    Some(
        leq(&(left.x.clone() + left_item.size.x.clone()), &right.x)?
            || leq(&(right.x.clone() + right_item.size.x.clone()), &left.x)?
            || leq(&(left.y.clone() + left_item.size.y.clone()), &right.y)?
            || leq(&(right.y.clone() + right_item.size.y.clone()), &left.y)?
            || leq(&(left.z.clone() + left_item.size.z.clone()), &right.z)?
            || leq(&(right.z.clone() + right_item.size.z.clone()), &left.z)?,
    )
}

fn nonnegative(value: &Real) -> Option<bool> {
    match value.refine_sign_until(-64)? {
        RealSign::Negative => Some(false),
        RealSign::Zero | RealSign::Positive => Some(true),
    }
}

fn leq(left: &Real, right: &Real) -> Option<bool> {
    match (left - right).refine_sign_until(-64)? {
        RealSign::Negative | RealSign::Zero => Some(true),
        RealSign::Positive => Some(false),
    }
}