Skip to content

Instantly share code, notes, and snippets.

@ForeverZer0
Created April 4, 2020 01:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ForeverZer0/076a63bbc7f3ce24be75066535353e27 to your computer and use it in GitHub Desktop.
Save ForeverZer0/076a63bbc7f3ce24be75066535353e27 to your computer and use it in GitHub Desktop.
High-efficiency bin-packer implementation for 2D rectangles.
using System.Drawing;
using System.Collections.Generic;
using System.Linq;
using JetBrains.Annotations;
namespace MyNamespace
{
/// <summary>
/// Represents a rectangular box shape.
/// </summary>
public sealed class Box
{
/// <summary>
/// Gets the size of the <see cref="Box"/> on the x-axis.
/// </summary>
public int Width { get; }
/// <summary>
/// Gets the size of the <see cref="Box"/> on the y-axis.
/// </summary>
public int Height { get; }
/// <summary>
/// Gets the total area of the <see cref="Box"/>.
/// </summary>
internal int Area => Width * Height;
/// <summary>
/// Internal node, used for packing algorithm.
/// </summary>
internal Node Node;
/// <summary>
/// Creates a new instance of the <see cref="Box"/> class.
/// </summary>
/// <param name="width">The size of the <see cref="Box"/> on the x-axis.</param>
/// <param name="height">The size of the <see cref="Box"/> on the y-axis.</param>
public Box(int width, int height)
{
Width = width;
Height = height;
}
/// <summary>
/// Creates a new instance of the <see cref="Box"/> class.
/// </summary>
/// <param name="size">The size of the <see cref="Box"/>.</param>
public Box(Size size) : this(size.Width, size.Height)
{
}
/// <summary>
/// Gets a <see cref="Rectangle"/> describing the box.
/// <remarks>The location is initially empty until it has been packed.</remarks>
/// </summary>
public Rectangle Rectangle => new Rectangle(Node?.X ?? 0, Node?.Y ?? 0, Width, Height);
/// <inheritdoc />
public override string ToString() => Rectangle.ToString();
}
/// <summary>
/// A node type used internally by the <see cref="RectPacker"/> class.
/// </summary>
internal class Node
{
/// <summary>
/// The <see cref="Node"/> to the right of this <see cref="Node"/>.
/// </summary>
public Node Right;
/// <summary>
/// The <see cref="Node"/> to the bottom of this <see cref="Node"/>.
/// </summary>
public Node Down;
/// <summary>
/// The location of this node on the x-axis.
/// </summary>
public int X;
/// <summary>
/// The location of this node on the y-axis.
/// </summary>
public int Y;
/// <summary>
/// The size of this node on the x-axis.
/// </summary>
public int Width;
/// <summary>
/// The size of this node on the y-axis.
/// </summary>
public int Height;
/// <summary>
/// Indicates if this node has been used.
/// </summary>
public bool IsUsed;
/// <summary>
/// Creates a new instance of the <see cref="Node"/> class.
/// </summary>
public Node()
{
}
/// <summary>
/// Creates a new instance of the <see cref="Node"/> class.
/// </summary>
/// <param name="x">The location of the node on the x-axis.</param>
/// <param name="y">The location of the node on the y-axis.</param>
/// <param name="width">The size of the node on the x-axis.</param>
/// <param name="height">The size of the node on the y-axis.</param>
public Node(int x, int y, int width, int height)
{
X = x;
Y = y;
Width = width;
Height = height;
}
}
/// <summary>
/// Implements a high-efficiency bin-packer for 2D rectangles.
/// </summary>
public static class RectPacker
{
private static Node rootNode;
/// <summary>
/// Efficiently packs a collection of <see cref="Box"/> objects to fit into the minimum amount of space.
/// <para>The location of the <see cref="Box"/> objects are modified in-place without altering the order of the collection.</para>
/// </summary>
/// <param name="boxes">A collection of objects defining the sizes to pack.</param>
/// <param name="startWidth">An initial starting width, ideally equal to the maximum width of the child <paramref name="boxes"/>.</param>
/// <param name="startHeight">An initial starting width, ideally equal to the maximum height of the child <paramref name="boxes"/>.</param>
/// <returns>The allotted size that all the child <paramref name="boxes"/> require to be fit into.</returns>
public static Size Pack([NotNull] IEnumerable<Box> boxes, int startWidth, int startHeight)
{
rootNode = new Node { Width = startWidth, Height = startHeight };
foreach (var box in boxes.OrderByDescending(x => x.Area))
{
var node = FindNode(rootNode, box.Width, box.Height);
box.Node = node != null
? SplitNode(node, box.Width, box.Height)
: GrowNode(box.Width, box.Height);
}
return new Size(rootNode.Width, rootNode.Height);
}
private static Node FindNode(Node root, int width, int height)
{
while (true)
{
if (!root.IsUsed)
return width <= root.Width && height <= root.Height ? root : null;
var node = FindNode(root.Right, width, height);
if (node != null)
return node;
root = root.Down;
}
}
private static Node SplitNode(Node node, int width, int height)
{
node.IsUsed = true;
node.Down = new Node(node.X, node.Y + height, node.Width, node.Height - height);
node.Right = new Node(node.X + width, node.Y, node.Width - width, height);
return node;
}
private static Node GrowNode(int width, int height)
{
var down = width <= rootNode.Width;
var right = height <= rootNode.Height;
if (right && rootNode.Height >= rootNode.Width + width)
return GrowRight(width, height);
if (down && rootNode.Width >= rootNode.Height + height)
return GrowDown(width, height);
if (right)
return GrowRight(width, height);
return down ? GrowDown(width, height) : null;
}
private static Node GrowRight(int width, int height)
{
rootNode = new Node
{
IsUsed = true,
X = 0,
Y = 0,
Width = rootNode.Width + width,
Height = rootNode.Height,
Down = rootNode,
Right = new Node(rootNode.Width, 0, width, rootNode.Height)
};
var node = FindNode(rootNode, width, height);
return node != null ? SplitNode(node, width, height) : null;
}
private static Node GrowDown(int width, int height)
{
rootNode = new Node()
{
IsUsed = true,
X = 0,
Y = 0,
Width = rootNode.Width,
Height = rootNode.Height + height,
Down = new Node() { X = 0, Y = rootNode.Height, Width = rootNode.Width, Height = height },
Right = rootNode
};
var node = FindNode(rootNode, width, height);
return node != null ? SplitNode(node, width, height) : null;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment