binpack_3d/
second_algorithmen.rs

1use std::mem;
2
3use hashbrown::HashSet;
4use rayon::iter::{
5    IntoParallelIterator,
6    IntoParallelRefIterator,
7    ParallelIterator,
8};
9use serde::{
10    Deserialize,
11    Serialize,
12};
13
14use crate::{
15    aabb::{
16        AABBVersion1,
17        AABBVersion1CheckedItem,
18    },
19    algorithmen::Algorithmen3DBinPackaging,
20    bin::{
21        Bin,
22        SpaceLeftBin,
23    },
24    corners::Corners,
25    items::{
26        Item,
27        ItemsPlaced,
28    },
29    sortedbin::SortedBin,
30};
31
32/// Second algorithmen
33#[derive(Debug, Clone, Serialize, Deserialize)]
34pub struct SecondAlgorithmen {
35    bin: Bin,
36    items: Vec<Item>,
37    aabb: AABBVersion1,
38    /// Volume left in the bin
39    volume_left: u32,
40    corners: HashSet<Corners>,
41}
42impl SecondAlgorithmen {
43    fn is_support_under_it(items_placed: &Vec<ItemsPlaced>, item: &Item, point: &Corners) -> bool {
44        // on the ground
45        if point.position.y == 0 {
46            return true;
47        }
48        // Candidate footprint (half-open [min, max))
49        let min_x = point.position.x;
50        let max_x = point.position.x + item.size_cube.x;
51        let min_z = point.position.z;
52        let max_z = point.position.z + item.size_cube.z;
53
54        items_placed.iter().any(|p| {
55            // Must sit exactly on top of this item
56            let top_y = p.position.y + p.item.size_cube.y;
57            if top_y != point.position.y {
58                return false;
59            }
60
61            // Support item's footprint
62            let p_min_x = p.position.x;
63            let p_max_x = p.position.x + p.item.size_cube.x;
64            let p_min_z = p.position.z;
65            let p_max_z = p.position.z + p.item.size_cube.z;
66
67            let overlap_x = min_x < p_max_x && p_min_x < max_x;
68            let overlap_z = min_z < p_max_z && p_min_z < max_z;
69
70            overlap_x && overlap_z
71        })
72    }
73    /// if it fits in the bin
74    fn fits_in_bin(bin: &Bin, corner: &Corners, item: &Item) -> bool {
75        corner.position.x + item.size_cube.x <= bin.position.x
76            && corner.position.y + item.size_cube.y <= bin.position.y
77            && corner.position.z + item.size_cube.z <= bin.position.z
78    }
79    /// Minimum is better
80    fn score(bin: &Bin, item: &Item, point: &Corners) -> f32 {
81        // without + 1 NaN can be possible
82        let x =
83            ((point.position.x + item.size_cube.x) as f32 + 1.0) / (bin.position.x as f32) + 1.0;
84        let y =
85            ((point.position.y + item.size_cube.y) as f32 + 1.0) / (bin.position.y as f32) + 1.0;
86        let z =
87            ((point.position.z + item.size_cube.z) as f32 + 1.0) / (bin.position.z as f32) + 1.0;
88        let maximise_space_on_floor = (item.size_cube.x * item.size_cube.z) as f32;
89
90        ((x) + (y * 100.0) + (10.0 * z) - maximise_space_on_floor).clamp(f32::MIN, f32::MAX)
91    }
92    /// Find best point to place
93    fn find_best_point_to_place<F>(
94        points: &HashSet<Corners>,
95        item: Item,
96        aabb: &AABBVersion1,
97        bin: &Bin,
98        placed_items: &Vec<ItemsPlaced>,
99        custom_score_function: Option<F>,
100    ) -> Option<(AABBVersion1CheckedItem, f32, Corners)>
101    where
102        F: Fn(&Bin, &Item, &Corners) -> f32 + Send + Sync,
103    {
104        let all_items_rotated = item.rotation_v2();
105        all_items_rotated
106            .into_iter()
107            .filter_map(|x_item| {
108                // rayon removed for the second iterator check later
109                points
110                    .par_iter()
111                    .cloned()
112                    .filter_map(|x_corner| {
113                        // if outer bounds ignore
114                        if !Self::fits_in_bin(bin, &x_corner, &x_item)
115                            || !Self::is_support_under_it(placed_items, &x_item, &x_corner)
116                        {
117                            return None;
118                        }
119                        let check = aabb.check_item_v2(x_item.clone(), &x_corner)?;
120                        let score = match custom_score_function.as_ref() {
121                            None => Self::score(bin, &x_item, &x_corner),
122                            Some(x) => x(bin, &x_item, &x_corner),
123                        };
124                        Some((check, score, x_corner))
125                    })
126                    .min_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal))
127            })
128            .min_by(|a, b| {
129                a.1.partial_cmp(&b.1)
130                    .unwrap_or_else(|| std::cmp::Ordering::Equal)
131            })
132    }
133    /// place item in bin
134    fn place_item_in_bin(
135        &mut self,
136        point: Corners,
137        item: crate::aabb::AABBVersion1CheckedItem,
138        aabb: &mut AABBVersion1,
139    ) -> anyhow::Result<(ItemsPlaced, Vec<Corners>)> {
140        let _ = aabb.add_v2(item.clone(), &point);
141        let _ = self.corners.remove(&point);
142        let one_corner = Corners::new(
143            point.position.x + item.0.size_cube.x,
144            point.position.y,
145            point.position.z,
146        );
147        let second_pointer = Corners::new(
148            point.position.x,
149            item.0.size_cube.y + point.position.y,
150            point.position.z,
151        );
152        let three_pointer = Corners::new(
153            point.position.x,
154            point.position.y,
155            item.0.size_cube.z + point.position.z,
156        );
157        // Check if they improve acrousy, if not delete
158        let four_point = Corners::new(
159            point.position.x + item.0.size_cube.x,
160            point.position.y + item.0.size_cube.y,
161            point.position.z,
162        );
163        let five_point = Corners::new(
164            point.position.x + item.0.size_cube.x,
165            point.position.y,
166            point.position.z + item.0.size_cube.z,
167        );
168        let sichs_point = Corners::new(
169            point.position.x,
170            point.position.y + item.0.size_cube.y,
171            point.position.z + item.0.size_cube.z,
172        );
173        let seven_point = Corners::new(
174            point.position.x + item.0.size_cube.x,
175            point.position.y + item.0.size_cube.y,
176            point.position.z + item.0.size_cube.z,
177        );
178        let new_corners = vec![
179            one_corner,
180            second_pointer,
181            three_pointer,
182            four_point,
183            five_point,
184            sichs_point,
185            seven_point,
186        ];
187        // Checks if a corner is in the bin
188        let new_corners = new_corners
189            .into_iter()
190            .filter_map(|x| aabb.point_is_free(&x).then(|| x))
191            .collect();
192        let new_item = ItemsPlaced::new(point.position, item.0);
193        Ok((new_item, new_corners))
194    }
195}
196impl Algorithmen3DBinPackaging for SecondAlgorithmen {
197    fn create_algorithmen(
198        input: Vec<Item>,
199        bin: Bin,
200    ) -> Result<Self, crate::algorithmen::AlgorithmenError> {
201        let volume = bin
202            .position
203            .x
204            .saturating_mul(bin.position.y)
205            .saturating_mul(bin.position.z);
206        let length = input.len();
207        let mut hashset: HashSet<Corners> = HashSet::with_capacity(length);
208        // ignore
209        let _ = hashset.insert(Corners::new(0, 0, 0));
210        Ok(Self {
211            bin,
212            items: input,
213            aabb: AABBVersion1::new(length),
214            volume_left: volume,
215            corners: hashset,
216        })
217    }
218
219    /// Add item to the list
220    fn add_item(&mut self, input: Vec<Item>) -> Result<(), crate::algorithmen::AlgorithmenError> {
221        self.items.extend(input);
222        Ok(())
223    }
224
225    /// Removes items from the list no size check
226    fn remove_item(&mut self, input: Vec<Item>) -> Result<(), Vec<Item>> {
227        self.items.retain(|x| !input.contains(x));
228        Ok(())
229    }
230
231    fn space_left(&self) -> u32 {
232        self.volume_left
233    }
234
235    fn check_fit_quick(input: &[Item], bin: &Bin) -> (bool, crate::bin::SpaceLeftBin) {
236        let bin_volume =
237            (bin.position.x * bin.position.y * bin.position.z).clamp(u32::MIN, u32::MAX);
238        let item_total_volume: u32 = input
239            .iter()
240            .map(|x| x.size_cube.x * x.size_cube.y * x.size_cube.z)
241            .sum();
242
243        let item_total_volume = item_total_volume.clamp(u32::MIN, u32::MAX);
244        let result = bin_volume
245            .saturating_sub(item_total_volume)
246            .clamp(u32::MIN, u32::MAX);
247        let result = SpaceLeftBin(result);
248        let check = result.0 > 0;
249        (check, result)
250    }
251
252    fn calculate_custom<F>(
253        mut self,
254        custom_score_function: Option<F>,
255    ) -> Result<crate::sortedbin::SortedBin, crate::algorithmen::AlgorithmenError>
256    where
257        F: Fn(&Bin, &Item, &Corners) -> f32 + Send + Sync,
258    {
259        let item = mem::take(&mut self.items);
260        let (mut keep, remove): (Vec<Item>, Vec<Item>) = item.into_par_iter().partition(|x| {
261            x.size_cube.x <= self.bin.position.x
262                && x.size_cube.y <= self.bin.position.y
263                && x.size_cube.z <= self.bin.position.z
264        });
265        keep.sort_unstable_by(|a, b| a.order.cmp(&b.order).then_with(|| a.weight.cmp(&b.weight)));
266        // takes item
267        let item: Vec<Item> = keep;
268        let mut removed_items: Vec<Item> = Vec::with_capacity(item.len());
269        removed_items.extend(remove);
270        let mut placed_item: Vec<ItemsPlaced> = Vec::with_capacity(item.len());
271
272        // Takes checker
273        let mut aabb = mem::take(&mut self.aabb);
274        item.into_iter().for_each(|x| {
275            let result = Self::find_best_point_to_place(
276                &self.corners,
277                x.clone(),
278                &aabb,
279                &self.bin,
280                &placed_item,
281                custom_score_function.as_ref(),
282            );
283            if let Some(checked_result) = result {
284                if let Ok((item_finished, new_corners)) = Self::place_item_in_bin(
285                    &mut self,
286                    checked_result.2,
287                    checked_result.0,
288                    &mut aabb,
289                ) {
290                    self.volume_left = self
291                        .volume_left
292                        .saturating_sub(item_finished.item.volume_item());
293                    placed_item.push(item_finished);
294                    self.corners.extend(new_corners);
295                } else {
296                    removed_items.push(x);
297                }
298            } else {
299                removed_items.push(x);
300            }
301        });
302        Ok(SortedBin::new(self.bin, placed_item, removed_items))
303    }
304
305    fn calculate(self) -> Result<SortedBin, crate::algorithmen::AlgorithmenError> {
306        Self::calculate_custom(self, None::<fn(&Bin, &Item, &Corners) -> f32>)
307    }
308}
309#[cfg(test)]
310mod tests {
311    use proptest::prelude::*;
312
313    use crate::{
314        bin::Bin,
315        corners::Corners,
316        items::Item,
317        second_algorithmen::SecondAlgorithmen,
318        vector::Vector3,
319    };
320
321    proptest! {
322        #[test]
323        fn second_algorithmen_score(x in 0u32..100,y in 0u32..100,z in 0u32..100) {
324            let result = SecondAlgorithmen::score(&Bin::new(1,Vector3::new(x + 100, y + 100, z + 100), 1000, 0), &Item::new(1,Vector3::new(x, y, z), 10, 1), &Corners::new(0,0,0));
325            dbg!(&result);
326            prop_assert!(result.is_normal());
327            prop_assert!(!result.is_nan());
328            }
329    }
330}
binpack_3d/second_algorithmen.rs

binpack_3d/
second_algorithmen.rs
