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

use image::{DynamicImage, RgbaImage};

use crate::{format, Color, Point, Rect, Size};

/// Binary bin packer
#[derive(Debug)]
pub struct Packer {
    image: RgbaImage,
    bins: Bin,
}

#[derive(Debug)]
struct Bin {
    occupied: Option<Size>,
    area: Rect,

    //                   (top, bottom)
    children: Option<Box<(Bin, Bin)>>,
}

impl Packer {
    /// Creates a new packer with given `size` and a transparent background
    pub fn new(size: Size) -> Self {
        let mut image = RgbaImage::new(size.width, size.height);
        image
            .pixels_mut()
            .for_each(|v| *v = Color::from([255, 0, 255, 0]));

        Self {
            image,
            bins: Bin {
                occupied: None,
                children: None,
                area: Rect::new(Point::new(0, 0), size),
            },
        }
    }

    /// Packs a new `image` with a given `gap` and if successful returns the region it was packed
    /// in
    pub fn pack(&mut self, image: &DynamicImage, gap: u32) -> Option<Rect> {
        let size = Size::new(image.width(), image.height());
        let gapped_size = Size::new(image.width() + gap * 2, image.height() + gap * 2);

        match self.bins.insert(gapped_size) {
            Some(rect) => {
                let rect = Rect::new(Point::new(rect.min_x() + gap, rect.min_y() + gap), size);

                let image = image.to_rgba8();
                image.enumerate_pixels().for_each(|(x, y, p)| {
                    self.image.put_pixel(x + rect.min_x(), y + rect.min_y(), *p)
                });

                Some(rect)
            }
            None => None,
        }
    }

    /// Saves this packer's image to a file with given `name` and `img` format
    pub fn save(&self, name: &str, img: format::ImageFormat) -> anyhow::Result<()> {
        self.image
            .save_with_format(format!("{}.{}", name, img.ext()), img.as_image_format())?;
        Ok(())
    }
}

impl Bin {
    pub fn fits(&self, size: Size) -> bool {
        if self.area.width() < size.width || self.area.height() < size.height {
            return false;
        }

        if let Some(children) = self.children.as_ref() {
            return children.0.fits(size) || children.1.fits(size);
        }

        true
    }

    pub fn insert(&mut self, size: Size) -> Option<Rect> {
        if !self.fits(size) {
            return None;
        }

        if let Some(ref mut children) = self.children {
            if let Some(rect) = children.0.insert(size) {
                return Some(rect);
            }

            if let Some(rect) = children.1.insert(size) {
                return Some(rect);
            }

            return None;
        }

        self.occupied = Some(size);
        self.children = Some(Box::new((
            Bin {
                occupied: None,
                area: Rect::new(
                    Point::new(self.area.min_x() + size.width, self.area.min_y()),
                    Size::new(self.area.width() - size.width, size.height),
                ),
                children: None,
            },
            Bin {
                occupied: None,
                area: Rect::new(
                    Point::new(self.area.min_x(), self.area.min_y() + size.height),
                    Size::new(self.area.width(), self.area.height() - size.height),
                ),
                children: None,
            },
        )));

        Some(Rect::new(self.area.origin, size))
    }
}