From: Andreas Widen Date: Fri, 12 Jun 2026 13:27:22 +0000 (+0200) Subject: Initial commit. X-Git-Tag: v0.1.0^0 X-Git-Url: https://luflow.net/git-repos/flow-rbp.git/commitdiff_plain/875514b229ce65d660651ace58d2b5188e12f334 Initial commit. Signed-off-by: Andreas Widen --- 875514b229ce65d660651ace58d2b5188e12f334 diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..fa9706e --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +CHANGELOG.md +.vscode +/target diff --git a/AUTHORS b/AUTHORS new file mode 100644 index 0000000..68493a7 --- /dev/null +++ b/AUTHORS @@ -0,0 +1,9 @@ +flow-rbp: A library for packing rectangles into two-dimensional finite bins. +Maintainer: Andreas Widen +License: zlib +URL: https://www.luflow.net + +Authors +======= + +Andreas Widen diff --git a/Cargo.lock b/Cargo.lock new file mode 100644 index 0000000..e28eb6a --- /dev/null +++ b/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "flow-rbp" +version = "0.1.0" diff --git a/Cargo.toml b/Cargo.toml new file mode 100644 index 0000000..a20d867 --- /dev/null +++ b/Cargo.toml @@ -0,0 +1,14 @@ +[package] +name = "flow-rbp" +version = "0.1.0" +edition = "2024" +authors = ["Andreas Widen "] +description = "flow-rbp is a library for packing rectangles into two-dimensional finite bins." +license = "Zlib" +repository = "https://luflow.net/git/flow-rbp.git" +readme = "README.md" +documentation = "https://luflow.net/git/flow-rbp.git" +keywords = ["rectangles", "rect", "bin", "packing"] +exclude = [".github", "/ci/*"] + +[dependencies] diff --git a/LICENSE b/LICENSE new file mode 100644 index 0000000..ccca46c --- /dev/null +++ b/LICENSE @@ -0,0 +1,18 @@ +flow-rbp: A library for packing rectangles into two-dimensional finite bins. +Copyright (C) 2026-2026 Andreas Widen + +This software is provided 'as-is', without any express or implied +warranty. In no event will the authors be held liable for any damages +arising from the use of this software. + +Permission is granted to anyone to use this software for any purpose, +including commercial applications, and to alter it and redistribute it +freely, subject to the following restrictions: + +1. The origin of this software must not be misrepresented; you must not + claim that you wrote the original software. If you use this software + in a product, an acknowledgment in the product documentation would be + appreciated but is not required. +2. Altered source versions must be plainly marked as such, and must not be + misrepresented as being the original software. +3. This notice may not be removed or altered from any source distribution. diff --git a/README.md b/README.md new file mode 100644 index 0000000..96a16e3 --- /dev/null +++ b/README.md @@ -0,0 +1,51 @@ +# flow-rbp + +`flow-rbp` is a library for packing rectangles into two-dimensional finite bins +using different heuristic methods for placement. + +The two-dimensional rectangle bin packing is a classical problem in +combinatorial optimization. In this problem, one is given a sequence of +rectangles `(R1, R2, ... Rn), Ri = (wi, hi)` and the task is to find a packing +of these items into a minimum number of bins of size `(W, H)`. No two +rectangles may intersect or be contained inside one another. This library uses +an algorithm sometimes referred as `The Maximal Rectangles ALgorithm`. This +algorithm stores a list of free rectangles that represents the free area of the +bin. + +## Usage + +Add this to your `Cargo.toml`: + +``` +[dependencies] +flow-rbp = { git = "https://luflow.net/git/flow-rbp.git", tag = "v0.1.0" } +``` + +Then: + +```rust +use flow_rbp::FreeRectHeuristic; +use flow_rbp::RectsBinPack; + +// create a new bin of size 32x32 which allows rotation: +let mut rbp = RectsBinPack::new(32, 32, true).unwrap(); + +// make sure occupancy is zero: +assert_eq!(rbp.get_occupancy(), 0.0); + +// add a few rects that should fit: +assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); +assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); +assert_eq!(rbp.get_occupancy(), 0.5); +assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); +assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); +assert_eq!(rbp.get_occupancy(), 1.0); + +// this rect will not fit and therefore returns None: +assert_eq!(rbp.insert(1, 1, FreeRectHeuristic::BottomLeft).is_none(), true); + +``` + +## LICENSE + +See the file 'LICENSE' for license information. diff --git a/cliff.toml b/cliff.toml new file mode 100644 index 0000000..29b5b65 --- /dev/null +++ b/cliff.toml @@ -0,0 +1,81 @@ +# git-cliff ~ configuration file +# https://git-cliff.org/docs/configuration + +[changelog] +# A Tera template to be rendered as the changelog's header. +# See https://keats.github.io/tera/docs/#introduction +header = """ +# Changelog\n +All notable changes to this project will be documented in this file. + +The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), +and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html).\n +""" +# A Tera template to be rendered for each release in the changelog. +# See https://keats.github.io/tera/docs/#introduction +body = """ +{% if version -%} + ## [{{ version | trim_start_matches(pat="v") }}] - {{ timestamp | date(format="%Y-%m-%d") }} +{% else -%} + ## [Unreleased] +{% endif -%} +{% for group, commits in commits | group_by(attribute="group") %} + ### {{ group | upper_first }} + {% for commit in commits %} + - {{ commit.message | split(pat="\n") | first | upper_first | trim }}\ + {% endfor %} +{% endfor %}\n +""" +# A Tera template to be rendered as the changelog's footer. +# See https://keats.github.io/tera/docs/#introduction +footer = """ +{% for release in releases -%} + {% if release.version -%} + {% if release.previous.version -%} + [{{ release.version | trim_start_matches(pat="v") }}]: \ + https://luflow.net/git-repos/flow-rbp.git\ + /compare/{{ release.previous.version }}..{{ release.version }} + {% else -%} + [{{ release.version | trim_start_matches(pat="v") }}]: \ + https://luflow.net/git-repos/flow-rbp.git\ + /tree/{{ release.version }} + {% endif -%} + {% else -%} + [unreleased]: https://luflow.net/git-repos/flow-rbp.git\ + /compare/{{ release.previous.version }}..HEAD + {% endif -%} +{% endfor %} + +""" +# Remove leading and trailing whitespaces from the changelog's body. +trim = true + +[git] +# Parse commits according to the conventional commits specification. +# See https://www.conventionalcommits.org +conventional_commits = true +# Exclude commits that do not match the conventional commits specification. +filter_unconventional = false +# An array of regex based parsers for extracting data from the commit message. +# Assigns commits to groups. +# Optionally sets the commit's scope and can decide to exclude commits from further processing. +commit_parsers = [ + { message = "^[a|A]dd", group = "Added" }, + { message = "^[s|S]upport", group = "Added" }, + { message = "^[r|R]emove", group = "Removed" }, + { message = "^.*: add", group = "Added" }, + { message = "^.*: support", group = "Added" }, + { message = "^.*: remove", group = "Removed" }, + { message = "^.*: delete", group = "Removed" }, + { message = "^test", group = "Fixed" }, + { message = "^fix", group = "Fixed" }, + { message = "^.*: fix", group = "Fixed" }, + { message = "^.*", group = "Changed" }, +] +# Prevent commits that are breaking from being excluded by commit parsers. +filter_commits = false +# Order releases topologically instead of chronologically. +topo_order = false +# Order of commits in each group/release within the changelog. +# Allowed values: newest, oldest +sort_commits = "oldest" diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..76f6878 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,55 @@ +// flow-rbp: A library for packing rectangles into two-dimensional finite bins. +// zlib License (see LICENSE) + +#![warn(missing_docs)] + +//! This crates provides a library for packing rectangles into two-dimensional finite bins using +//! different heuristic methods for placement. +//! +//! The two-dimensional rectangle bin packing is a classical problem in combinatorial optimization. +//! In this problem, one is given a sequence of rectangles `(R1, R2, ... Rn), Ri = (wi, hi)` and +//! the task is to find a packing of these items into a minimum number of bins of size `(W, H)`. No two +//! rectangles may intersect or be contained inside one another. This library uses an algorithm +//! sometimes referred as `The Maximal Rectangles ALgorithm`. This algorithm stores a list of free +//! rectangles that represents the free area of the bin. +//! +//! Placement can be tweaked by using different heuristic methods such as +//! [`ShortSideFit`](crate::rbp::FreeRectHeuristic::ShortSideFit), +//! [`LongSideFit`](crate::rbp::FreeRectHeuristic::LongSideFit), +//! [`AreaFit`](crate::rbp::FreeRectHeuristic::AreaFit), +//! [`BottomLeft`](crate::rbp::FreeRectHeuristic::BottomLeft) and +//! [`ContactPoint`](crate::rbp::FreeRectHeuristic::ContactPoint). +//! +//! # Examples +//! +//! ``` +//! use flow_rbp::FreeRectHeuristic; +//! use flow_rbp::RectsBinPack; +//! +//! // create a new bin of size 32x32 which allows rotation: +//! let mut rbp = RectsBinPack::new(32, 32, true).unwrap(); +//! +//! // make sure occupancy is zero: +//! assert_eq!(rbp.get_occupancy(), 0.0); +//! +//! // add a few rects that should fit: +//! assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); +//! assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); +//! assert_eq!(rbp.get_occupancy(), 0.5); +//! assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); +//! assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); +//! assert_eq!(rbp.get_occupancy(), 1.0); +//! +//! // this rect will not fit and therefore returns None: +//! assert_eq!(rbp.insert(1, 1, FreeRectHeuristic::BottomLeft).is_none(), true); +//! +//! ``` + +#[doc(hidden)] +pub mod rbp; + +// re-export types: +pub use crate::rbp::FreeRectHeuristic; +pub use crate::rbp::Rect2D; +pub use crate::rbp::RectsBinPack; +pub use crate::rbp::RectsBinPackError; diff --git a/src/rbp.rs b/src/rbp.rs new file mode 100644 index 0000000..1b896ef --- /dev/null +++ b/src/rbp.rs @@ -0,0 +1,786 @@ +// flow-rbp: A library for packing rectangles into two-dimensional finite bins. +// zlib License (see LICENSE) + +/// Specifies the different heuristic rules that can be used when deciding where to place a new +/// rectangle. +#[derive(Clone, Debug)] +pub enum FreeRectHeuristic { + /// Choose to pack `R` into such `Fi` that `min(wf - w, hf - h)` is the smallest. In other words, we + /// minimize the length of the shorter leftover side. + ShortSideFit, + + /// Pack `R` into an `Fi` such that `max(wf - w, hf - h)` is the smallest. That is, we minimize + /// the length of the longer leftover side. + LongSideFit, + + /// Pick the `Fi ∈ F` that is smallest in area to place the next rectangle `R` into. If there is a + /// tie, we use the [`ShortSideFit`](crate::rbp::FreeRectHeuristic::ShortSideFit) rule to break it. + AreaFit, + + /// Orient and place each rectangle to the position where the y-coordinate of the top side of the + /// rectangle is the smallest and if there are several such valid positions, pick the one that has + /// the smallest x-coordinate value. + BottomLeft, + + /// Place `R` into a position where the length of the perimeter of `R` that is touched by the bin + /// edge or by a previously packed rectangle is maximized. + ContactPoint, +} + +/// Specifies the different error types that can occur. +#[derive(PartialEq, Clone, Debug)] +pub enum RectsBinPackError { + /// Invalid argument + InvalidArg, +} + +/// Specifies the properties of a 2D rectangle. +#[derive(Clone, Debug)] +pub struct Rect2D { + /// is the x offset + pub x: i32, + + /// is the y offset + pub y: i32, + + /// is the width + pub width: i32, + + /// is the height + pub height: i32, +} + +impl Rect2D { + /// Instantiates a 2D rectangle of size (0, 0, 0, 0). + /// + /// # Examples + /// + /// ``` + /// use flow_rbp::Rect2D; + /// + /// let rect = Rect2D::new(); + /// assert_eq!(rect.x, 0); + /// assert_eq!(rect.y, 0); + /// assert_eq!(rect.width, 0); + /// assert_eq!(rect.height, 0); + /// ``` + pub fn new() -> Self { + Self { + x: 0, + y: 0, + width: 0, + height: 0, + } + } + + /// Instantiates a 2D rectangle with given size properties. + /// + /// # Arguments + /// + /// * `x` - is the x offset. + /// * `y` - is the y offset. + /// * `width` - is the width. + /// * `height` - is the height. + /// + /// # Errors + /// + /// [`InvalidArg`](crate::rbp::RectsBinPackError::InvalidArg) + /// is returned if `x < 0 || y < 0 || width <= 0 || height <= 0`. + /// + /// # Examples + /// + /// ``` + /// use flow_rbp::Rect2D; + /// + /// let rect = Rect2D::with_details(0, 0, 32, 16).unwrap(); + /// assert_eq!(rect.x, 0); + /// assert_eq!(rect.y, 0); + /// assert_eq!(rect.width, 32); + /// assert_eq!(rect.height, 16); + /// + /// // this should fail: + /// assert_eq!(Rect2D::with_details(0, 0, 0, 0).is_err(), true); + /// ``` + pub fn with_details( + x: i32, + y: i32, + width: i32, + height: i32, + ) -> Result { + if x >= 0 && y >= 0 && width > 0 && height > 0 { + Ok(Self { + x, + y, + width, + height, + }) + } else { + Err(RectsBinPackError::InvalidArg) + } + } +} + +/// Specifies the properties of a rectangle bin. +#[derive(Clone, Debug)] +pub struct RectsBinPack { + /// is the width of the bin + width: i32, + + /// is the height of the bin + height: i32, + + /// is the flag indicating whether rotation is allowed or not + allow_flip: bool, + + /// is the vector holding the used rects + used_rects: Vec, + + /// is the vector holding the free rects + free_rects: Vec, +} + +impl RectsBinPack { + /// Instantiates a empty bin of given size. + /// + /// # Arguments + /// + /// * `width` - is the width of the bin + /// * `height` - is the height of the bin + /// * `allow_flip` - is the flag indicating whether the packing algorithm is allowed to rotate + /// the input rectangle 90 degrees clockwise to consider a better placement. + /// + /// # Errors + /// + /// [`RectsBinPackError::InvalidArg`](crate::rbp::RectsBinPackError) + /// is returned if `width <= 0 || height <= 0`. + /// + /// # Examples + /// + /// ``` + /// use flow_rbp::RectsBinPack; + /// use flow_rbp::FreeRectHeuristic; + /// + /// let mut rbp = RectsBinPack::new(32, 32, false).unwrap(); + /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); + /// assert_eq!(rbp.insert(33, 33, FreeRectHeuristic::BottomLeft).is_none(), true); + /// ``` + pub fn new(width: i32, height: i32, allow_flip: bool) -> Result { + if width > 0 && height > 0 { + Ok(Self { + width, + height, + allow_flip, + used_rects: Vec::new(), + free_rects: vec![Rect2D::with_details(0, 0, width, height).unwrap()], + }) + } else { + Err(RectsBinPackError::InvalidArg) + } + } + + /// Insert a single rectangle into the bin, possibly rotated. + /// + /// # Arguments + /// + /// * `width` - is the rectangle width + /// * `height` - is the rectangle height + /// * `heuristic` - is the heuristic method to use when packing + /// + /// # Examples + /// + /// ``` + /// use flow_rbp::RectsBinPack; + /// use flow_rbp::FreeRectHeuristic; + /// + /// let mut rbp = RectsBinPack::new(32, 32, false).unwrap(); + /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); + /// assert_eq!(rbp.insert(33, 33, FreeRectHeuristic::BottomLeft).is_none(), true); + /// ``` + pub fn insert( + &mut self, + width: i32, + height: i32, + heuristic: FreeRectHeuristic, + ) -> Option { + let output = match heuristic { + FreeRectHeuristic::ShortSideFit => self.get_rect_for_best_short_side_fit(width, height), + FreeRectHeuristic::BottomLeft => self.get_rect_for_bottom_left(width, height), + FreeRectHeuristic::ContactPoint => self.get_rect_for_contact_point(width, height), + FreeRectHeuristic::LongSideFit => self.get_rect_for_best_long_side_fit(width, height), + FreeRectHeuristic::AreaFit => self.get_rect_for_best_area_fit(width, height), + }; + + if let Some(new_rect) = output { + let mut i: usize = 0; + while i < self.free_rects.len() { + if let Some(free_rect) = self.free_rects.get(i) { + if self.is_split_free_node(&free_rect.clone(), &new_rect) { + self.free_rects.remove(i); + continue; + } + } + + i += 1; + } + + self.prune_free_list(); + self.used_rects.push(new_rect.clone()); + + return Some(new_rect); + } else { + return None; + } + } + + /// Computes the ratio of used surface area to the total bin area. + /// + /// # Examples + /// + /// ``` + /// use flow_rbp::RectsBinPack; + /// use flow_rbp::FreeRectHeuristic; + /// + /// let mut rbp = RectsBinPack::new(32, 32, false).unwrap(); + /// + /// // occupancy should be 0.0 initially: + /// assert_eq!(rbp.get_occupancy(), 0.0); + /// + /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); + /// assert_eq!(rbp.get_occupancy(), 0.25); + /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); + /// assert_eq!(rbp.get_occupancy(), 0.5); + /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); + /// assert_eq!(rbp.get_occupancy(), 0.75); + /// assert_eq!(rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), true); + /// + /// // occupancy should now be full as in 1.0: + /// assert_eq!(rbp.get_occupancy(), 1.0); + /// ``` + pub fn get_occupancy(&self) -> f32 { + let mut used_surface_area: i32 = 0; + + for i in 0..self.used_rects.len() { + if let Some(rect) = self.used_rects.get(i) { + used_surface_area += rect.width * rect.height; + } + } + + // return occupancy: + return used_surface_area as f32 / (self.width * self.height) as f32; + } + + /// Computes the placement score for the contact point variant. + fn get_score_for_contact_point(&self, x: i32, y: i32, width: i32, height: i32) -> i32 { + let mut score: i32 = 0; + + if x == 0 || x + width == self.width { + score += height; + } + + if y == 0 || y + height == self.height { + score += width; + } + + for i in 0..self.used_rects.len() { + if let Some(used_rect) = self.used_rects.get(i) { + if used_rect.x == x + width || used_rect.x + used_rect.width == x { + score += self.get_common_interval_len( + used_rect.y, + used_rect.y + used_rect.height, + y, + y + height, + ); + } + + if used_rect.y == y + height || used_rect.y + used_rect.height == y { + score += self.get_common_interval_len( + used_rect.x, + used_rect.x + used_rect.width, + x, + x + width, + ); + } + } + } + + return score; + } + + /// Computes the rect for bottom left placement variant. + fn get_rect_for_bottom_left(&self, width: i32, height: i32) -> Option { + let mut new_rect = Rect2D::new(); + + let mut best_x = std::i32::MAX; + let mut best_y = std::i32::MAX; + + for i in 0..self.free_rects.len() { + if let Some(free_rect) = self.free_rects.get(i) { + // true to place the rect in upright (non-flipped) orientation: + if free_rect.width >= width && free_rect.height >= height { + let top_side_y = free_rect.y + height; + + if top_side_y < best_y || (top_side_y == best_y && free_rect.x < best_x) { + new_rect.x = free_rect.x; + new_rect.y = free_rect.y; + new_rect.width = width; + new_rect.height = height; + best_x = free_rect.x; + best_y = top_side_y; + } + } + + if self.allow_flip && free_rect.width >= height && free_rect.height >= width { + let top_side_y = free_rect.y + width; + + if top_side_y < best_y || (top_side_y == best_y && free_rect.x < best_x) { + new_rect.x = free_rect.x; + new_rect.y = free_rect.y; + new_rect.width = height; + new_rect.height = width; + best_x = free_rect.x; + best_y = top_side_y; + } + } + } else { + return None; + } + } + + if new_rect.height == 0 || new_rect.width == 0 { + return None; + } + + return Some(new_rect); + } + + /// Computes the rect for short side fit variant. + fn get_rect_for_best_short_side_fit(&self, width: i32, height: i32) -> Option { + let mut new_rect = Rect2D::new(); + + let mut best_short_side_fit = std::i32::MAX; + let mut best_long_side_fit = std::i32::MAX; + + for i in 0..self.free_rects.len() { + if let Some(free_rect) = self.free_rects.get(i) { + // try to place the rect in upright (non-flipped) orientation: + if free_rect.width >= width && free_rect.height >= height { + let left_over_horiz = free_rect.width - width; + let left_over_vert = free_rect.height - height; + let short_side_fit = std::cmp::min(left_over_horiz, left_over_vert); + let long_side_fit = std::cmp::max(left_over_horiz, left_over_vert); + + if short_side_fit < best_short_side_fit + || (short_side_fit == best_short_side_fit + && long_side_fit < best_long_side_fit) + { + new_rect.x = free_rect.x; + new_rect.y = free_rect.y; + new_rect.width = width; + new_rect.height = height; + best_short_side_fit = short_side_fit; + best_long_side_fit = long_side_fit; + } + } + + if self.allow_flip && free_rect.width >= height && free_rect.height >= width { + let flipped_left_over_horiz = free_rect.width - height; + let flipped_left_over_vert = free_rect.height - width; + let flipped_short_side_fit = + std::cmp::min(flipped_left_over_horiz, flipped_left_over_vert); + let flipped_long_side_fit = + std::cmp::max(flipped_left_over_horiz, flipped_left_over_vert); + + if flipped_short_side_fit < best_short_side_fit + || (flipped_short_side_fit == best_short_side_fit + && flipped_long_side_fit < best_long_side_fit) + { + new_rect.x = free_rect.x; + new_rect.y = free_rect.y; + new_rect.width = height; + new_rect.height = width; + best_short_side_fit = flipped_short_side_fit; + best_long_side_fit = flipped_long_side_fit; + } + } + } else { + return None; + } + } + + if new_rect.height == 0 || new_rect.width == 0 { + return None; + } + + return Some(new_rect); + } + + /// Computes the rect for long side fit variant. + fn get_rect_for_best_long_side_fit(&self, width: i32, height: i32) -> Option { + let mut new_rect = Rect2D::new(); + + let mut best_short_side_fit = std::i32::MAX; + let mut best_long_side_fit = std::i32::MAX; + + for i in 0..self.free_rects.len() { + if let Some(free_rect) = self.free_rects.get(i) { + // try to place the rect in upright (non-flipped) orientation: + if free_rect.width >= width && free_rect.height >= height { + let left_over_horiz = free_rect.width - width; + let left_over_vert = free_rect.height - height; + let short_side_fit = std::cmp::min(left_over_horiz, left_over_vert); + let long_side_fit = std::cmp::max(left_over_horiz, left_over_vert); + + if long_side_fit < best_long_side_fit + || (long_side_fit == best_long_side_fit + && short_side_fit < best_short_side_fit) + { + new_rect.x = free_rect.x; + new_rect.y = free_rect.y; + new_rect.width = width; + new_rect.height = height; + best_short_side_fit = short_side_fit; + best_long_side_fit = long_side_fit; + } + } + + if self.allow_flip && free_rect.width >= height && free_rect.height >= width { + let left_over_horiz = free_rect.width - height; + let left_over_vert = free_rect.height - width; + let short_side_fit = std::cmp::min(left_over_horiz, left_over_vert); + let long_side_fit = std::cmp::max(left_over_horiz, left_over_vert); + + if long_side_fit < best_long_side_fit + || (long_side_fit == best_long_side_fit + && short_side_fit < best_short_side_fit) + { + new_rect.x = free_rect.x; + new_rect.y = free_rect.y; + new_rect.width = height; + new_rect.height = width; + best_short_side_fit = short_side_fit; + best_long_side_fit = long_side_fit; + } + } + } else { + return None; + } + } + + if new_rect.height == 0 || new_rect.width == 0 { + return None; + } + + return Some(new_rect); + } + + /// Computes the rect for best area fit variant. + fn get_rect_for_best_area_fit(&self, width: i32, height: i32) -> Option { + let mut new_rect = Rect2D::new(); + + let mut best_area_fit = std::i32::MAX; + let mut best_short_side_fit = std::i32::MAX; + + for i in 0..self.free_rects.len() { + if let Some(free_rect) = self.free_rects.get(i) { + let area_fit = free_rect.width * free_rect.height - width * height; + + // try to place rect in upright (non-flipped) orientation: + if free_rect.width >= width && free_rect.height >= height { + let left_over_horiz = free_rect.width - width; + let left_over_vert = free_rect.height - height; + let short_side_fit = std::cmp::min(left_over_horiz, left_over_vert); + + if area_fit < best_area_fit + || (area_fit == best_area_fit && short_side_fit < best_short_side_fit) + { + new_rect.x = free_rect.x; + new_rect.y = free_rect.y; + new_rect.width = width; + new_rect.height = height; + best_short_side_fit = short_side_fit; + best_area_fit = area_fit; + } + } + + if self.allow_flip && free_rect.width >= height && free_rect.height >= width { + let left_over_horiz = free_rect.width - height; + let left_over_vert = free_rect.height - width; + let short_side_fit = std::cmp::min(left_over_horiz, left_over_vert); + + if area_fit < best_area_fit + || (area_fit == best_area_fit && short_side_fit < best_short_side_fit) + { + new_rect.x = free_rect.x; + new_rect.y = free_rect.y; + new_rect.width = height; + new_rect.height = width; + best_short_side_fit = short_side_fit; + best_area_fit = area_fit; + } + } + } else { + return None; + } + } + + if new_rect.height == 0 || new_rect.width == 0 { + return None; + } + + return Some(new_rect); + } + + /// Computes the rect for contact point variant. + fn get_rect_for_contact_point(&self, width: i32, height: i32) -> Option { + let mut new_rect = Rect2D::new(); + let mut best_contact_score = -1; + + for i in 0..self.free_rects.len() { + if let Some(free_rect) = self.free_rects.get(i) { + // try to place the rect in upright (non-flipped) orientation: + if free_rect.width >= width && free_rect.height >= height { + let contact_score = + self.get_score_for_contact_point(free_rect.x, free_rect.y, width, height); + + if contact_score > best_contact_score { + new_rect.x = free_rect.x; + new_rect.y = free_rect.y; + new_rect.width = width; + new_rect.height = height; + best_contact_score = contact_score; + } + } + + if self.allow_flip && free_rect.width >= height && free_rect.height >= width { + let contact_score = + self.get_score_for_contact_point(free_rect.x, free_rect.y, height, width); + + if contact_score > best_contact_score { + new_rect.x = free_rect.x; + new_rect.y = free_rect.y; + new_rect.width = height; + new_rect.height = width; + best_contact_score = contact_score; + } + } + } else { + return None; + } + } + + if new_rect.height == 0 || new_rect.width == 0 { + return None; + } + + return Some(new_rect); + } + + /// returns true if the free rect was split + fn is_split_free_node(&mut self, free_rect: &Rect2D, used_rect: &Rect2D) -> bool { + // test with SAT if the rects even intersect: + if used_rect.x >= free_rect.x + free_rect.width + || used_rect.x + used_rect.width <= free_rect.x + || used_rect.y >= free_rect.y + free_rect.height + || used_rect.y + used_rect.height <= free_rect.y + { + return false; + } + + if used_rect.x < free_rect.x + free_rect.width + && used_rect.x + used_rect.width > free_rect.x + { + // new node at the top side of the used node: + if used_rect.y > free_rect.y && used_rect.y < free_rect.y + free_rect.height { + let mut new_rect = free_rect.clone(); + new_rect.height = used_rect.y - new_rect.y; + self.free_rects.push(new_rect); + } + + // new node at the bottom side of the used node: + if used_rect.y + used_rect.height < free_rect.y + free_rect.height { + let mut new_rect = free_rect.clone(); + new_rect.y = used_rect.y + used_rect.height; + new_rect.height = free_rect.y + free_rect.height - (used_rect.y + used_rect.height); + self.free_rects.push(new_rect); + } + } + + if used_rect.y < free_rect.y + free_rect.height + && used_rect.y + used_rect.height > free_rect.y + { + // new node at the left side of the used node: + if used_rect.x > free_rect.x && used_rect.x < free_rect.x + free_rect.width { + let mut new_rect = free_rect.clone(); + new_rect.width = used_rect.x - new_rect.x; + self.free_rects.push(new_rect); + } + + // new node at the right side of the used node: + if used_rect.x + used_rect.width < free_rect.x + free_rect.width { + let mut new_rect = free_rect.clone(); + new_rect.x = used_rect.x + used_rect.width; + new_rect.width = free_rect.x + free_rect.width - (used_rect.x + used_rect.width); + self.free_rects.push(new_rect); + } + } + + return true; + } + + /// goes through the free rect list and removes any redundant entries + fn prune_free_list(&mut self) { + // go through each pair and remove any rects that are redundant: + let mut keep: Vec = vec![true; self.free_rects.len()]; + for i in 0..self.free_rects.len() { + for j in i + 1..self.free_rects.len() { + if let Some(free_rect_i) = self.free_rects.get(i) + && let Some(free_rect_j) = self.free_rects.get(j) + { + if self.is_contained_on(free_rect_i, free_rect_j) { + if let Some(value) = keep.get_mut(i) { + *value = false; + } + break; + } + + if self.is_contained_on(free_rect_j, free_rect_i) { + if let Some(value) = keep.get_mut(j) { + *value = false; + } + } + } + } + } + + // remove all items marked false: + let mut iter = keep.iter(); + self.free_rects.retain(|_| *iter.next().unwrap()); + } + + /// determine whether rect A is contained on rect B + fn is_contained_on(&self, a: &Rect2D, b: &Rect2D) -> bool { + return a.x >= b.x + && a.y >= b.y + && a.x + a.width <= b.x + b.width + && a.y + a.height <= b.y + b.height; + } + + /// returns 0 if the two intervals i1 and i2 are disjoint, or the length of their + /// overlap otherwise. + fn get_common_interval_len( + &self, + i1_start: i32, + i1_end: i32, + i2_start: i32, + i2_end: i32, + ) -> i32 { + if i1_end < i2_start || i2_end < i1_start { + return 0; + } + + return std::cmp::min(i1_end, i2_end) - std::cmp::max(i1_start, i2_start); + } +} // impl RectsBinPack + +// unit tests: +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn rect2d_basics() { + let rect = Rect2D::new(); + + assert_eq!(rect.x, 0); + assert_eq!(rect.y, 0); + assert_eq!(rect.width, 0); + assert_eq!(rect.height, 0); + + let rect = Rect2D::with_details(2, 4, 16, 32).unwrap(); + + assert_eq!(rect.x, 2); + assert_eq!(rect.y, 4); + assert_eq!(rect.width, 16); + assert_eq!(rect.height, 32); + + assert_eq!( + Rect2D::with_details(-1, 4, 16, 32).unwrap_err(), + RectsBinPackError::InvalidArg + ); + assert_eq!( + Rect2D::with_details(0, -1, 16, 32).unwrap_err(), + RectsBinPackError::InvalidArg + ); + assert_eq!( + Rect2D::with_details(0, 0, 0, 32).unwrap_err(), + RectsBinPackError::InvalidArg + ); + assert_eq!( + Rect2D::with_details(2, 4, 16, 0).unwrap_err(), + RectsBinPackError::InvalidArg + ); + assert_eq!( + Rect2D::with_details(-1, -1, 0, 0).unwrap_err(), + RectsBinPackError::InvalidArg + ); + } + + #[test] + fn rbp_invalid_arg() { + assert_eq!( + RectsBinPack::new(0, 0, false).unwrap_err(), + RectsBinPackError::InvalidArg + ); + assert_eq!( + RectsBinPack::new(32, 0, false).unwrap_err(), + RectsBinPackError::InvalidArg + ); + assert_eq!( + RectsBinPack::new(0, 32, false).unwrap_err(), + RectsBinPackError::InvalidArg + ); + + assert_eq!( + RectsBinPack::new(0, 0, true).unwrap_err(), + RectsBinPackError::InvalidArg + ); + assert_eq!( + RectsBinPack::new(32, 0, true).unwrap_err(), + RectsBinPackError::InvalidArg + ); + assert_eq!( + RectsBinPack::new(0, 32, true).unwrap_err(), + RectsBinPackError::InvalidArg + ); + } + + #[test] + fn rbp_basics() { + let mut rbp = RectsBinPack::new(32, 32, false).unwrap(); + assert_eq!(rbp.get_occupancy(), 0.0); + + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::ShortSideFit) + .is_some(), + true + ); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::LongSideFit).is_some(), + true + ); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::AreaFit).is_some(), + true + ); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 1.0); + + assert_eq!( + rbp.insert(1, 1, FreeRectHeuristic::ContactPoint).is_none(), + true + ); + } +} diff --git a/tests/insert.rs b/tests/insert.rs new file mode 100644 index 0000000..148508a --- /dev/null +++ b/tests/insert.rs @@ -0,0 +1,254 @@ +// flow-rbp: A library for packing rectangles into two-dimensional finite bins. +// public domain License + +use flow_rbp::FreeRectHeuristic; +use flow_rbp::RectsBinPack; + +#[test] +fn insert_short_side_fit() { + let mut rbp = RectsBinPack::new(32, 32, false).unwrap(); + assert_eq!(rbp.get_occupancy(), 0.0); + + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::ShortSideFit) + .is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.25); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::ShortSideFit) + .is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.5); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::ShortSideFit) + .is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.75); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::ShortSideFit) + .is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 1.0); + + assert_eq!( + rbp.insert(1, 1, FreeRectHeuristic::ShortSideFit).is_none(), + true + ); +} + +#[test] +fn insert_short_side_fit_rotated() { + let mut rbp = RectsBinPack::new(32, 16, true).unwrap(); + assert_eq!(rbp.get_occupancy(), 0.0); + + assert_eq!( + rbp.insert(16, 32, FreeRectHeuristic::ShortSideFit) + .is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 1.0); + + assert_eq!( + rbp.insert(1, 1, FreeRectHeuristic::ShortSideFit).is_none(), + true + ); +} + +#[test] +fn insert_long_side_fit() { + let mut rbp = RectsBinPack::new(32, 32, false).unwrap(); + assert_eq!(rbp.get_occupancy(), 0.0); + + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::LongSideFit).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.25); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::LongSideFit).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.5); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::LongSideFit).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.75); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::LongSideFit).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 1.0); + + assert_eq!( + rbp.insert(1, 1, FreeRectHeuristic::LongSideFit).is_none(), + true + ); +} + +#[test] +fn insert_long_side_fit_rotated() { + let mut rbp = RectsBinPack::new(32, 16, true).unwrap(); + assert_eq!(rbp.get_occupancy(), 0.0); + + assert_eq!( + rbp.insert(16, 32, FreeRectHeuristic::LongSideFit).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 1.0); + + assert_eq!( + rbp.insert(1, 1, FreeRectHeuristic::LongSideFit).is_none(), + true + ); +} + +#[test] +fn insert_area_fit() { + let mut rbp = RectsBinPack::new(32, 32, false).unwrap(); + assert_eq!(rbp.get_occupancy(), 0.0); + + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::AreaFit).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.25); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::AreaFit).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.5); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::AreaFit).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.75); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::AreaFit).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 1.0); + + assert_eq!(rbp.insert(1, 1, FreeRectHeuristic::AreaFit).is_none(), true); +} + +#[test] +fn insert_area_fit_rotated() { + let mut rbp = RectsBinPack::new(32, 16, true).unwrap(); + assert_eq!(rbp.get_occupancy(), 0.0); + + assert_eq!( + rbp.insert(16, 32, FreeRectHeuristic::AreaFit).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 1.0); + + assert_eq!(rbp.insert(1, 1, FreeRectHeuristic::AreaFit).is_none(), true); +} + +#[test] +fn insert_bottom_left() { + let mut rbp = RectsBinPack::new(32, 32, false).unwrap(); + assert_eq!(rbp.get_occupancy(), 0.0); + + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.25); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.5); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.75); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::BottomLeft).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 1.0); + + assert_eq!( + rbp.insert(1, 1, FreeRectHeuristic::BottomLeft).is_none(), + true + ); +} + +#[test] +fn insert_bottom_left_rotated() { + let mut rbp = RectsBinPack::new(32, 16, true).unwrap(); + assert_eq!(rbp.get_occupancy(), 0.0); + + assert_eq!( + rbp.insert(16, 32, FreeRectHeuristic::BottomLeft).is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 1.0); + + assert_eq!( + rbp.insert(1, 1, FreeRectHeuristic::BottomLeft).is_none(), + true + ); +} + +#[test] +fn insert_contact_point() { + let mut rbp = RectsBinPack::new(32, 32, false).unwrap(); + assert_eq!(rbp.get_occupancy(), 0.0); + + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::ContactPoint) + .is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.25); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::ContactPoint) + .is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.5); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::ContactPoint) + .is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 0.75); + assert_eq!( + rbp.insert(16, 16, FreeRectHeuristic::ContactPoint) + .is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 1.0); + + assert_eq!( + rbp.insert(1, 1, FreeRectHeuristic::ContactPoint).is_none(), + true + ); +} + +#[test] +fn insert_contact_point_rotated() { + let mut rbp = RectsBinPack::new(32, 16, true).unwrap(); + assert_eq!(rbp.get_occupancy(), 0.0); + + assert_eq!( + rbp.insert(16, 32, FreeRectHeuristic::ContactPoint) + .is_some(), + true + ); + assert_eq!(rbp.get_occupancy(), 1.0); + + assert_eq!( + rbp.insert(1, 1, FreeRectHeuristic::ContactPoint).is_none(), + true + ); +}