二维装箱包装：为什么我的图像重叠？

Question

我移植了this从JavaScript到PHP的二维装箱算法，我正在使用它来在精灵图中绘制一些图像。

它适用于规则形状的图像（例如，所有方块），但对较大，更复杂的数据集产生轻微破坏的结果。

你可以看到，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新节点的高度应该是新块 不是节点的高度的高度

，所以这条线是错误：

$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实现（使用还排序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; 
    } 
} 

Answer 2

更好的垃圾箱来自blackpawn：http://www.blackpawn.com/texts/lightmaps/。它不使用增长功能。 JS中还有另一个例子：http://incise.org/2d-bin-packing-with-javascript-and-canvas.html和存储库：https://github.com/mackstann/binpack。