C#二叉树二维打包算法旋转

Question

我正在使用 Binary-Tree-2D-Packing 这个算法在容器中打包矩形。它工作正常，但如果节点不适合根节点，我想旋转该节点。它应该在正确的节点尝试宽度和高度，如果它不合适，它应该旋转它并使 width = height 和 height = width 然后再试一次。我怎样才能做到这一点？

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;
        }
    }
}

Answer 1

除非我误会了什么，否则它不会只是两个测试而不是一个吗？即

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

            box.position = GrowNode(box.width, box.height);
        }

请注意 GrowNode 总是按宽高顺序增长。

如果树是不可变的，您也可以尝试每个替代方案并比较结果节点。:

       Node whNode, hwNode;

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

        node = FindNode(rootNode, box.height, box.width);
        if (node != null)
        {
            hwNode= SplitNode(node, box.height, box.width);
        }
        else
        {
            hwNode= GrowNode(box.height, box.width);
        }
        box.Position = GetBestNode(whNode, hwNode);

Answer 2

我将旋转变量添加到 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;
    }

并为FindNode方法添加了旋转条件

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;
        }
    }

最后检查旋转变量是否为真，

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);
            }
        }
    }

C#二叉树二维打包算法旋转

C# Binary Tree 2D Packing Algorithm Rotation

c#

bin-packing