Search code examples
c#bin-packing

C# Binary Tree 2D Packing Algorithm Rotation


I'm using Binary-Tree-2D-Packing this algorithm to pack rectangles in a container. It works fine but I want to rotate the node if it's not fitting right of the root node. It should try width and height at the right node and if it's not fitting it should rotate it and make width = height and height = width then try again. How can I accomplish that?

public class Packer
        {
            public Packer()
            {
                boxes = new List<Box>();
            }
    public class Node
    {
        public Node right;
        public Node down;
        public double x;
        public double y;
        public double w;
        public double h;
        public bool used;
    }

    public class Box
    {
        public double height;
        public double width;
        public double area;
        public Node position;
    }

    public List<Box> boxes;
    private Node rootNode;

    public void AddBox(Box box)
    {
        box.area = box.width * box.height;
        boxes.Add(box);
    }

    public void Pack(double containerWidth, double containerHeight)
    {
        boxes = boxes.OrderByDescending(x => x.area).ToList();
        rootNode = new Node { w = containerWidth, h = containerHeight };

        foreach (var box in boxes)
        {
            var node = FindNode(rootNode, box.width, box.height);
            if (node != null)
            {
                box.position = SplitNode(node, box.width, box.height);
            }
            else
            {
                box.position = GrowNode(box.width, box.height);
            }
        }
    }

    private Node FindNode(Node rootNode, double w, double h)
    {
        if (rootNode.used)
        {
            var nextNode = FindNode(rootNode.right, w, h);

            if (nextNode == null)
            {
                nextNode = FindNode(rootNode.down, w, h);
            }

            return nextNode;
        }
        else if (w <= rootNode.w && h <= rootNode.h)
        {
            return rootNode;
        }
        else
        {
            return null;
        }
    }

    private Node SplitNode(Node node, double w, double h)
    {
        
        node.used = true;
        node.down = new Node { x = node.x, y = node.y + h, w = node.w, h = node.h - h };
        node.right = new Node { x = node.x + w, y = node.y, w = node.w - w, h = h };
        return node;
    }

    private Node GrowNode(double w, double h)
    {
        bool canGrowDown = (w <= rootNode.w);
        bool canGrowRight = (h <= rootNode.h);

        bool shouldGrowRight = canGrowRight && (rootNode.h >= (rootNode.w + w));
        bool shouldGrowDown = canGrowDown && (rootNode.w >= (rootNode.h + h));

        if (shouldGrowRight)
        {

            return growRight(w, h);
        }
        else if (shouldGrowDown)
        {

            return growDown(w, h);
        }
        else if (canGrowRight)
        {

            return growRight(w, h);
        }
        else if (canGrowDown)
        {

            return growDown(w, h);
        }
        else
        {

            return null;
        }
    }

    private Node growRight(double w, double h)
    {
        rootNode = new Node()
        {
            used = true,
            x = 0,
            y = 0,
            w = rootNode.w + w,
            h = rootNode.h,
            down = rootNode,
            right = new Node() { x = rootNode.w, y = 0, w = w, h = rootNode.h }
        };

        Node node = FindNode(rootNode, w, h);
        if (node != null)
        {
            return SplitNode(node, w, h);
        }
        else
        {
            return null;
        }
    }

    private Node growDown(double w, double h)
    {
        rootNode = new Node()
        {
            used = true,
            x = 0,
            y = 0,
            w = rootNode.w,
            h = rootNode.h + h,
            down = new Node() { x = 0, y = rootNode.h, w = rootNode.w, h = h },
            right = rootNode
        };
        Node node = FindNode(rootNode, w, h);
        if (node != null)
        {
            return SplitNode(node, w, h);
        }
        else
        {
            return null;
        }
    }
}

Solution

  • I added rotated variable to Node

    public class Node
        {
            public Node right;
            public Node down;
            public double x;
            public double y;
            public double w;
            public double h;
            public bool used;
            public bool rotated;
        }
    

    And added rotation condition to FindNode method

    private Node FindNode(Node rootNode, double w, double h)
        {
            if (rootNode.used)
            {
    
                var nextNode = FindNode(rootNode.right, w, h);
    
                if (nextNode == null)
                {
    
                    nextNode = FindNode(rootNode.right, h, w);
                    if (nextNode!=null) { nextNode.rotated = true; }
                    
                    if (nextNode == null)
                    {
                        nextNode = FindNode(rootNode.down, w, h);
                    }
    
                }
    
                return nextNode;
            }
            else if (w <= rootNode.w && h <= rootNode.h)
            {
                return rootNode;
            }
            else
            {
                return null;
            }
        }
    

    At last checked for the rotated variable if true,

    public void Pack(double containerWidth, double containerHeight)
        {
            boxes = boxes.OrderByDescending(x => x.area).ToList();
            rootNode = new Node { w = containerWidth, h = containerHeight };
    
            foreach (var box in boxes)
            {
                var node = FindNode(rootNode, box.width, box.height);
                if (node != null)
                {
    
                
                if (node.rotated)
                {
                    double tmp = 0;
                    tmp = box.width;
                    box.width = box.height;
                    box.height = tmp;
                }
                }
                if (node != null)
                {
                    box.position = SplitNode(node, box.width, box.height);
                }
                else
                {
                    box.position = GrowNode(box.width, box.height);
                }
            }
        }