rectutils/
pack.rs

1//! Rectangle packer packs small rectangles into a bigger one.
2
3use crate::{Number, Rect};
4use num_traits::Zero;
5
6#[derive(Clone)]
7struct RectPackNode<T>
8where
9    T: Number,
10{
11    filled: bool,
12    split: bool,
13    bounds: Rect<T>,
14    left: usize,
15    right: usize,
16}
17
18impl<T> RectPackNode<T>
19where
20    T: Number,
21{
22    fn new(bounds: Rect<T>) -> Self {
23        Self {
24            bounds,
25            filled: false,
26            split: false,
27            left: usize::MAX,
28            right: usize::MAX,
29        }
30    }
31}
32
33/// Rectangle packer packs small rectangles into a bigger one.
34#[derive(Clone)]
35pub struct RectPacker<T>
36where
37    T: Number,
38{
39    nodes: Vec<RectPackNode<T>>,
40    root: usize,
41    width: T,
42    height: T,
43    unvisited: Vec<usize>,
44}
45
46impl<T> RectPacker<T>
47where
48    T: Number,
49{
50    /// Creates new instance of the rectangle packer with given bounds.
51    ///
52    /// # How to choose initial bounds
53    ///
54    /// If you have a set of rectangles and you need to calculate average side length of a square,
55    /// then calculate total area of your triangles by sum of width*height and then take square
56    /// root out of area. You'll get side length of a square which can be used as width and height
57    /// parameters.
58    pub fn new(w: T, h: T) -> Self {
59        Self {
60            nodes: vec![RectPackNode::new(Rect::new(
61                Zero::zero(),
62                Zero::zero(),
63                w,
64                h,
65            ))],
66            root: 0,
67            width: w,
68            height: h,
69            unvisited: Default::default(),
70        }
71    }
72
73    /// Clears packer and prepares it for another run. It is much cheaper than create new packer,
74    /// because it reuses previously allocated memory.
75    pub fn clear(&mut self) {
76        self.nodes.clear();
77        self.unvisited.clear();
78        self.nodes.push(RectPackNode::new(Rect::new(
79            Zero::zero(),
80            Zero::zero(),
81            self.width,
82            self.height,
83        )));
84        self.root = 0;
85    }
86
87    /// Tries to find free place to put rectangle with given size. Returns None if there insufficient
88    /// space.
89    pub fn find_free(&mut self, w: T, h: T) -> Option<Rect<T>> {
90        if self.unvisited.is_empty() {
91            self.unvisited.push(self.root);
92        }
93
94        while let Some(node_index) = self.unvisited.pop() {
95            let node = &mut self.nodes[node_index];
96            if node.split {
97                self.unvisited.push(node.right);
98                self.unvisited.push(node.left);
99            } else if !node.filled && node.bounds.w() >= w && node.bounds.h() >= h {
100                if node.bounds.w() == w && node.bounds.h() == h {
101                    node.filled = true;
102                    return Some(node.bounds);
103                }
104
105                // Split and continue
106                node.split = true;
107
108                let (left_bounds, right_bounds) = if node.bounds.w() - w > node.bounds.h() - h {
109                    (
110                        Rect::new(node.bounds.x(), node.bounds.y(), w, node.bounds.h()),
111                        Rect::new(
112                            node.bounds.x() + w,
113                            node.bounds.y(),
114                            node.bounds.w() - w,
115                            node.bounds.h(),
116                        ),
117                    )
118                } else {
119                    (
120                        Rect::new(node.bounds.x(), node.bounds.y(), node.bounds.w(), h),
121                        Rect::new(
122                            node.bounds.x(),
123                            node.bounds.y() + h,
124                            node.bounds.w(),
125                            node.bounds.h() - h,
126                        ),
127                    )
128                };
129
130                let left = self.nodes.len();
131                self.nodes.push(RectPackNode::new(left_bounds));
132                let right = self.nodes.len();
133                self.nodes.push(RectPackNode::new(right_bounds));
134
135                let node = &mut self.nodes[node_index];
136                node.left = left;
137                node.right = right;
138
139                self.unvisited.push(left);
140            }
141        }
142
143        None
144    }
145}
146
147#[cfg(test)]
148mod test {
149    use super::{RectPackNode, RectPacker};
150    use crate::Rect;
151
152    #[test]
153    fn rect_pack_node_new() {
154        let rect = Rect::new(0.0, 0.0, 1.0, 1.0);
155        let node = RectPackNode::new(rect);
156
157        assert!(!node.filled);
158        assert!(!node.split);
159        assert_eq!(node.bounds, rect);
160        assert_eq!(node.left, usize::MAX);
161        assert_eq!(node.right, usize::MAX);
162    }
163
164    #[test]
165    fn rect_packer_new() {
166        let rp = RectPacker::new(1.0, 1.0);
167
168        assert_eq!(rp.width, 1.0);
169        assert_eq!(rp.height, 1.0);
170        assert_eq!(rp.unvisited, vec![]);
171    }
172
173    #[test]
174    fn rect_packer_find_free() {
175        let mut rp = RectPacker::new(10.0, 10.0);
176
177        assert_eq!(rp.find_free(20.0, 20.0), None);
178        assert_eq!(rp.find_free(1.0, 1.0), Some(Rect::new(0.0, 0.0, 1.0, 1.0)));
179        assert_eq!(rp.find_free(9.0, 9.0), Some(Rect::new(0.0, 1.0, 9.0, 9.0)));
180    }
181
182    #[test]
183    fn rect_packer_clear() {
184        let mut rp = RectPacker::new(10.0, 10.0);
185
186        rp.find_free(1.0, 1.0);
187        rp.find_free(9.0, 9.0);
188        assert_eq!(rp.nodes.len(), 7);
189
190        rp.clear();
191        assert_eq!(rp.nodes.len(), 1);
192    }
193}
rectutils/pack.rs

rectutils/
pack.rs
