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

//! Rectangle packer is used to pack set of smaller rectangles into one big, it
//! used in texture atlas packer.

use crate::{
    math::Rect,
    num_traits::Zero,
    pool::{Handle, Pool},
};
use nalgebra::Scalar;
use num_traits::NumAssign;

struct RectPackNode<T>
where
    T: NumAssign + Scalar + PartialOrd + Copy,
{
    filled: bool,
    split: bool,
    bounds: Rect<T>,
    left: Handle<RectPackNode<T>>,
    right: Handle<RectPackNode<T>>,
}

impl<T> RectPackNode<T>
where
    T: NumAssign + Scalar + PartialOrd + Copy,
{
    fn new(bounds: Rect<T>) -> Self {
        Self {
            bounds,
            filled: false,
            split: false,
            left: Handle::NONE,
            right: Handle::NONE,
        }
    }
}

/// See module docs.
pub struct RectPacker<T>
where
    T: NumAssign + Scalar + PartialOrd + Copy,
{
    nodes: Pool<RectPackNode<T>>,
    root: Handle<RectPackNode<T>>,
    width: T,
    height: T,
    unvisited: Vec<Handle<RectPackNode<T>>>,
}

impl<T> RectPacker<T>
where
    T: NumAssign + Scalar + PartialOrd + Copy,
{
    /// Creates new instance of rectangle packer with given bounds.
    ///
    /// # How to choose bounds
    ///
    /// If you have a set of rectangles and you need to calculate average side length of a square,
    /// then calculate total area of your triangles by sum of width*height and then take square
    /// root out of area. You'll get side length of a square which can be used as width and height
    /// parameters.
    pub fn new(w: T, h: T) -> Self {
        let mut nodes = Pool::new();
        let root = nodes.spawn(RectPackNode::new(Rect::new(
            Zero::zero(),
            Zero::zero(),
            w,
            h,
        )));
        Self {
            nodes,
            root,
            width: w,
            height: h,
            unvisited: Default::default(),
        }
    }

    /// Clears packer and prepares it for another run. It is much cheaper than create new packer,
    /// because it reuses previously allocated memory.
    pub fn clear(&mut self) {
        self.nodes.clear();
        self.unvisited.clear();
        self.root = self.nodes.spawn(RectPackNode::new(Rect::new(
            Zero::zero(),
            Zero::zero(),
            self.width,
            self.height,
        )));
    }

    /// Tries to find free place to put rectangle with given size. Returns None if there insufficient
    /// space.
    pub fn find_free(&mut self, w: T, h: T) -> Option<Rect<T>> {
        if self.unvisited.is_empty() {
            self.unvisited.push(self.root);
        }

        while let Some(node_handle) = self.unvisited.pop() {
            let node = self.nodes.borrow_mut(node_handle);
            if node.split {
                self.unvisited.push(node.right);
                self.unvisited.push(node.left);
            } else if !node.filled && node.bounds.w() >= w && node.bounds.h() >= h {
                if node.bounds.w() == w && node.bounds.h() == h {
                    node.filled = true;
                    return Some(node.bounds);
                }

                // Split and continue
                node.split = true;

                let (left_bounds, right_bounds) = if node.bounds.w() - w > node.bounds.h() - h {
                    (
                        Rect::new(node.bounds.x(), node.bounds.y(), w, node.bounds.h()),
                        Rect::new(
                            node.bounds.x() + w,
                            node.bounds.y(),
                            node.bounds.w() - w,
                            node.bounds.h(),
                        ),
                    )
                } else {
                    (
                        Rect::new(node.bounds.x(), node.bounds.y(), node.bounds.w(), h),
                        Rect::new(
                            node.bounds.x(),
                            node.bounds.y() + h,
                            node.bounds.w(),
                            node.bounds.h() - h,
                        ),
                    )
                };

                let left = self.nodes.spawn(RectPackNode::new(left_bounds));
                let right = self.nodes.spawn(RectPackNode::new(right_bounds));

                let node = self.nodes.borrow_mut(node_handle);
                node.left = left;
                node.right = right;

                self.unvisited.push(left);
            }
        }

        None
    }
}