Created
April 4, 2020 01:03
-
-
Save ForeverZer0/076a63bbc7f3ce24be75066535353e27 to your computer and use it in GitHub Desktop.
High-efficiency bin-packer implementation for 2D rectangles.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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