rectangle packing in PHP for Metin Gür

index.php

<?php

define('NL', PHP_SAPI == 'cli' ? "\n" : "<br/>");


$blocks = array(
    array('w' => 161, 'h' => 199),
    array('w' => 299, 'h' => 197),
    array('w' => 147, 'h' => 200),
    array('w' => 133, 'h' => 200),
    array('w' => 128, 'h' => 200),
    array('w' => 130, 'h' => 200),
    array('w' => 500, 'h' => 300)
); 
        
// Packer must be initialized outside the loop
require_once("RectanglePacking.php");
$packer = new RectanglePacking(600, 600);

foreach ($blocks as $block) {

    echo "Trying to fit {$block['w']}x{$block['h']}... ";

    // Try to find a suitable gap in the configured rectangle
    $coords = $packer->findCoords($block['w'], $block['h']);
    
    if ($coords) {
        echo "Found a viable position at {$coords['x']}x{$coords['y']}" . NL;
    } else {
        echo "Block does not fit" . NL;
    }
}   

RectanglePacking.php

<?php

class RectanglePacking {

    private $root = array();
    private $usedHeight = 0;
    private $usedWidth = 0;
   
   
    function __construct($width, $height) {
        $this->reset($width, $height);
    }
   
    function reset($width, $height) {
        $this->root['x'] = 0;
        $this->root['y'] = 0;
        $this->root['w'] = $width;
        $this->root['h'] = $height;
        $this->root['lft'] = null;
        $this->root['rgt'] = null;
       
        $this->usedWidth = 0;
        $this->usedHeight = 0;
    }
   
    function getDimensions() {
        return array(
            'w' => $this->usedWidth,
            'h' => $this->usedHeight
        );
    }
   
    function cloneNode($node) {
        return array(
            'x' => $node['x'],
            'y' => $node['y'],
            'w' => $node['w'],
            'h' => $node['h']
        );
    }              
   
    function recursiveFindCoords(&$node, $w, $h) {
        if (isset($node['lft']) && is_array($node['lft'])) {
            $coords = $this->recursiveFindCoords($node['lft'], $w, $h);
            if (!$coords && isset($node['rgt']) && is_array($node['rgt'])) {
                $coords = $this->recursiveFindCoords($node['rgt'], $w, $h);
            }
            return $coords;
        }
        else
        {
            if (isset($node['used']) && $node['used'] || $w > $node['w'] || $h > $node['h'])
                return null;
                   
            if ( $w == $node['w'] && $h == $node['h'] ) {
                $node['used'] = true;
                return array(
                    'x' => $node['x'],
                    'y' => $node['y']
                );
            }
           
            $node['lft'] = $this->cloneNode($node);
            $node['rgt'] = $this->cloneNode($node);
           
            if ( $node['w'] - $w > $node['h'] - $h ) {
                $node['lft']['w'] = $w;
                $node['rgt']['x'] = $node['x'] + $w;
                $node['rgt']['w'] = $node['w'] - $w;   
            } else {
                $node['lft']['h'] = $h;
                $node['rgt']['y'] = $node['y'] + $h;
                $node['rgt']['h'] = $node['h'] - $h;                                                   
            }
           
            return $this->recursiveFindCoords($node['lft'], $w, $h);
        }
    }
   
    function findCoords($w, $h) {
        $coords = $this->recursiveFindCoords($this->root, $w, $h);
        // var_dump($this->root);

        if ($coords) {
            if ( $this->usedWidth < $coords['x'] + $w )
                $this->usedWidth = $coords['x'] + $w;
            if ( $this->usedHeight < $coords['y'] + $h )
                $this->usedHeight = $coords['y'] + $h;
        }

        return $coords;
    }
}