二維裝箱包裝：爲什麼我的圖像重疊？

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。