php - 二维装箱 : Why are my images overlapping?

Question

我移植了this从 JavaScript 到 PHP 的 2D bin-packing 算法，我正在使用它在 Sprite 图中布置一些图像。

它适用于规则形状的图像(例如，所有正方形)，但对于更大、更复杂的数据集，它会产生略微损坏的结果。

您可以看到 16 是一个细长的图像，而 118 紧贴其下方。然后 57 高一点，但是 121 和 126 与 118/16 的下方与 57 重叠。不知道为什么要这样做。

有人知道我可能哪里出错了吗？

<?php

class Block {
    /** @var int */
    public $width;
    /** @var int */
    public $height;

    public function __construct($width, $height) {
        $this->width = $width;
        $this->height = $height;
    }
}

class Sprite extends Block {
    /** @var int */
    public $x;
    /** @var int */
    public $y;
    /** @var bool */
    public $used ;
    /** @var Sprite  */
    public $down;
    /** @var Sprite  */
    public $right;

    public function __construct($x, $y, $width, $height, $used=false, $down=null, $right=null) {
        $this->x = $x;
        $this->y = $y;
        $this->width = $width;
        $this->height = $height;
        $this->used = $used;
        $this->down = $down;
        $this->right = $right;
    }

    public function __toString() {
        return "$this->x $this->y $this->width $this->height";
    }
}

class Image extends Block {
    /** @var string */
    public $filePath;
    /** @var Sprite */
    public $fit;

    public function __construct($filePath, $width, $height) {
        $this->filePath = $filePath;
        $this->width = $width;
        $this->height = $height;
    }
}

class Packer {
    /** @var Sprite */
    public $root;

    /**
     * @param Image[] $images
     */
    public function fit($images) {
        $len = count($images);
        $w = $len > 0 ? $images[0]->width : 0;
        $h = $len > 0 ? $images[0]->height : 0;
        $this->root = new Sprite(0,0,$w,$h);
        foreach($images as $img) {
            if($node = $this->findNode($this->root, $img->width, $img->height)) {
                $img->fit = $this->splitNode($node, $img->width, $img->height);
            } else {
                $img->fit = $this->growNode($img->width, $img->height);
            }
        }
    }

    /**
     * @param Sprite $node
     * @param int $w
     * @param int $h
     *
     * @return Sprite
     */
    private function findNode($node, $w, $h) {
        if($node->used) {
            return $this->findNode($node->right, $w, $h) ?: $this->findNode($node->down, $w, $h);
        } elseif($w <= $node->width && $h <= $node->height) {
            return $node;
        }
        return null;
    }

    /**
     * @param Sprite $node
     * @param int $w
     * @param int $h
     *
     * @return Sprite
     */
    private function splitNode($node, $w, $h) {
        $node->used = true;
        $node->down = new Sprite($node->x, $node->y + $h, $node->width, $node->height - $h);
        $node->right = new Sprite($node->x + $w, $node->y, $node->width - $w, $node->height);
        return $node;
    }

    private function growNode($w, $h) {
        $canGrowDown = $w <= $this->root->width;
        $canGrowRight = $h <= $this->root->height;

        $shouldGrowDown = $canGrowDown && $this->root->width >= ($this->root->height + $h);
        $shouldGrowRight = $canGrowRight && $this->root->height >= ($this->root->width + $w);

        if($shouldGrowRight) {
            return $this->growRight($w, $h);
        } elseif($shouldGrowDown) {
            return $this->growDown($w, $h);
        } elseif($canGrowRight) {
            return $this->growRight($w, $h);
        } elseif($canGrowDown) {
            return $this->growDown($w, $h);
        }
        throw new Exception("Could not grow");
    }

    /**
     * @param int $w
     * @param int $h
     *
     * @throws Exception
     * @return Sprite
     */
    private function growRight($w, $h) {
        $node = new Sprite($this->root->width, 0, $w, $this->root->height);
        $this->root = new Sprite(0, 0, $this->root->width + $w, $this->root->height, true, $this->root, $node);
        return $this->splitNode($node, $w, $h);
    }

    /**
     * @param int $w
     * @param int $h
     *
     * @throws Exception
     * @return Sprite
     */
    private function growDown($w, $h){
        $node = new Sprite(0, $this->root->height, $this->root->width, $h);
        $this->root = new Sprite(0, 0, $this->root->width, $this->root->height + $h, true, $node, $this->root);
        return $this->splitNode($node, $w, $h);
    }
}

class Program {

    private static function imageCreateFromAny($filename) {
        return imagecreatefromstring(file_get_contents($filename));
    }

    private static function imageCreateTrueColorTransparent($width, $height) {
        $im = imagecreatetruecolor($width, $height);
        imagesavealpha($im, true);
        $transColor = imagecolorallocatealpha($im, 0, 0, 0, 127);
        imagefill($im, 0, 0, $transColor);
        return $im;
    }

    public static function main() {
        /** @var Image[] $images */
        $images = array();
        $di = new DirectoryIterator('test/7');
        foreach($di as $f) {
            /** @var $f DirectoryIterator */
            if(!$f->isFile()) continue;
            $filePath = $f->getPathname();
            list($w, $h) = getimagesize($filePath);
            if(!$w || !$h) {
                echo "could not get width/height for $filePath -- skipping\n";
                continue;
            }
            $images[] = new Image($filePath, $w, $h);
        }
        usort($images, function($a, $b) {
//            return max($a->width, $a->height) < max($b->width, $b->height) ? 1 : -1;
            if($a->width > $a->height) {
                $aMax = $a->width;
                $aMin = $a->height;
            } else {
                $aMin = $a->width;
                $aMax = $a->height;
            }
            if($b->width > $b->height) {
                $bMax = $b->width;
                $bMin = $b->height;
            } else {
                $bMin = $b->width;
                $bMax = $b->height;
            }
            if($aMax > $bMax) return -1;
            if($aMax < $bMax) return 1;
            if($aMin > $bMin) return -1;
            if($aMin < $bMin) return 1;
            return strcmp($a->filePath, $b->filePath);
        });
        $packer = new Packer();
        $packer->fit($images);
        $spritesheet = self::imageCreateTrueColorTransparent($packer->root->width, $packer->root->height);
        $black = imagecolorallocate($spritesheet, 0, 0, 0);
        foreach($images as $i=>$img) {
            $r = mt_rand(0, 255);
            $g = mt_rand(0, 255);
            $b = mt_rand(0, 255);
            imagefilledrectangle($spritesheet, $img->fit->x, $img->fit->y, $img->fit->x+$img->width, $img->fit->y+$img->height, imagecolorallocatealpha($spritesheet, $r, $g, $b, 64));
            imagerectangle($spritesheet, $img->fit->x, $img->fit->y, $img->fit->x+$img->width, $img->fit->y+$img->height, imagecolorallocate($spritesheet, $r, $g, $b));
            imagestring($spritesheet, 5, $img->fit->x + 2, $img->fit->y + 2, $i, $black);
//            imagecopy($spritesheet, self::imageCreateFromAny($img->filePath), $img->fit->x, $img->fit->y, 0, 0, $img->width, $img->height);
        }
        imagepng($spritesheet, 'spritesheet.png');
        echo "done!\n";
    }
}


if(php_sapi_name() === 'cli' && __FILE__ == realpath($argv[0])) {
    Program::main();
}

更新:注意到代码永远无法命中的几个地方，而是抛出异常；意识到 findNode 总是会找到新创建的节点，搜索我们已有的节点是没有意义的。清理了一下，但它仍然表现出完全相同的行为。开始认为这个算法不可行。

Answer 1

问题出在 splitNode 函数中:

private function splitNode($node, $w, $h) {
        $node->used = true;
        $node->down = new Sprite($node->x, $node->y + $h, $node->width, $node->height - $h);
        $node->right = new Sprite($node->x + $w, $node->y, $node->width - $w, $node->height);
        return $node;
}

特别是 node->right 上新节点的高度应该是新 block 的高度不是节点的高度，所以这一行是错误的:

$node->right = new Sprite($node->x + $w, $node->y, $node->width - $w, $node->height);

这是更正:

$node->right = new Sprite($node->x + $w, $node->y, $node->width - $w, $h);

否则新节点会比它实际拥有的空间更大，最终会与其他节点重叠。

这里有一些关于这个算法和原始 javascript 实现的信息:http://codeincomplete.com/posts/bin-packing/

这是我的 php 实现(在开始算法之前还在 block 上使用 sort maxside)。

class Node {
    public $x;
    public $y;
    public $w;
    public $h;
    public $used;
    public $right;
    public $down;

    public function __construct($x, $y, $w, $h, $used=false, $right=null, $down=null) {
        $this->x = $x;
        $this->y = $y;
        $this->w = $w;
        $this->h = $h;
        $this->used = $used;
        $this->right = $right;
        $this->down = $down;        
    }
}


class BinTreePacking {
    public $root;

    public function __construct($w, $h) {
        $this->init($w, $h);
    }

    public function init($w, $h) {        
        $this->root = new Node(0, 0, $w, $h);        
    }

    public function fit($blocks) {

        $blocks = $this->sortMaxside($blocks);

        foreach($blocks as &$block) {

            $block['fit'] = null;

            if($node = $this->findNode($this->root, $block['w'], $block['h'])) {
                $block['fit'] = $this->splitNode($node, $block['w'], $block['h']);
            } 
        }

        return $blocks;        
    }

    public function findNode($node, $w, $h) {
        if($node->used) {
            return $this->findNode($node->right, $w, $h) ?: $this->findNode($node->down, $w, $h);            
        }
        else if($w <= $node->w && $h <= $node->h) {       
            return $node;
        }
        return null;        
    }

    public function splitNode($node, $w, $h) {  
        $node->used = true;      
        $node->down = new Node($node->x, $node->y + $h, $node->w, $node->h - $h);
        $node->right = new Node($node->x + $w, $node->y, $node->w - $w, $h);
        return $node;
    }

    public function sortMaxside($blocks) {
        usort($blocks, function($a, $b) {
            $a_maxside = max($a['w'], $a['h']);
            $b_maxside = max($b['w'], $b['h']);
            return $a_maxside < $b_maxside;
        });
        return $blocks;
    }
}