Image tilemapper

tableoptimizer.cc

• The background image (filename)
• X and Y coordinates inside the image from where the background image for this cell can be found
• The background color (optional). A non-empty background color implies that the background image will be ignored.

• tilexsize and tileysize: The pixel dimensions of each cell (i.e. tile)
• xsize and ysize: The number of tiles horizontally and vertically in the table.
• The cells.

• removed: Zero if this cell should be rendered, nonzero if it should be ignored when rendering.
• colspan, rowspan: The colspan & rowspan attributes for this cell.

#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>

/*

This program reads a description of a table,
and outputs a plan of which cells can be merged using
a combination of colspan&rowspan, still such that no
two cell-spans overlap.

Copyright (C) 1992,2008 Joel Yliluoma - http://iki.fi/bisqwit/
*/

#include "tableoptimizer.hh"

struct Cell: public TableOptimizer::CellBase
{
    std::string blobfile, bgcolor;
    unsigned xpos, ypos;
    
public:
    Cell(const std::string& bf,
         const std::string& bg,
         unsigned xp, unsigned yp)
     : CellBase(),
       blobfile(bf),
       bgcolor(bg),
       xpos(xp), ypos(yp)
    {
    }

    bool CanExtend(const Cell& b,
        unsigned x,unsigned y,
        unsigned tx,unsigned ty) const
    {
        if(blobfile != b.blobfile) return false;
        if(bgcolor  != b.bgcolor)  return false;
        if(ty && bgcolor.empty())
        {
            if(xpos != b.xpos + x*tx) return false;
            if(ypos != b.ypos + y*ty) return false;
        }
        return true;
    }
};

static const Cell ReadCell(const char* arg)
{
    const char* cp = std::strchr(arg, ':');
    std::string blobfile(arg, cp);
    arg = cp+1;
    int xp=0, yp=0, chars_ate = 0;
    std::sscanf(arg, "%d:%d:%n", &xp, &yp, &chars_ate);
    arg += chars_ate;
    
    /*std::fprintf(stderr, "Created cell[%d,%d]: (%d,%d)\n",
        (unsigned)cells.size()%width,
        (unsigned)cells.size()/width,
        xp,yp);*/
    
    return Cell(blobfile, arg, xp, yp);
}

int main(int argc, const char* const* argv)
{
    if(argc < 5)
    {
        std::fprintf(stderr,
            "Usage: tableoptimizer <xsize> <ysize> <tilexsize> <tileysize> {<cell>}\n"
            "\n"
            "       Where <cell> is <blobfile>:<xpos>:<ypos>:<bgcolor>\n"
            "\n"
            "       Output consists of lines of <masked>:<colspan>:<rowspan>\n"
            "       Where <masked> is 0 if the cell should be rendered, 1 if skipped\n"
            "\n"
            "Copyright (C) 1992,2008 Joel Yliluoma - http://iki.fi/bisqwit/\n"
            "\n");
        return -1;
    }
    
    unsigned width = std::atoi(argv[1]);
    unsigned height = std::atoi(argv[2]);
    
    TableOptimizer::Table<Cell> table(
        width,
        height,
        std::atoi(argv[3]),
        std::atoi(argv[4])
    );
    
    for(unsigned p=0; p<width*height; ++p)
    {
        table.AddCell(ReadCell(argv[5+p]));
    }
    
    table.Optimize();
    
    table.Dump();
}

tableoptimizer.hh

#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>

namespace TableOptimizer
{

    /* The core of tableoptimizer.cc ...
     * Here because also binpack2d.cc uses it
     */
     
    struct CellBase
    {
        unsigned colspan, rowspan;
        bool     masked;
        bool     tried_1x1;
        bool     decided;
        
        CellBase()
          : colspan(1), rowspan(1),
            masked(false),
            tried_1x1(false),
            decided(false)
        {
        }
        
        bool CanExtend(const CellBase& /*b*/,
            unsigned /*x*/,unsigned /*y*/,
            unsigned /*tx*/,unsigned /*ty*/) const { return false; }
    };

    template<typename CellType>
    struct Table
    {
        unsigned width, height;
        unsigned tilewidth, tileheight;
        std::vector<CellType> cells;
        
    public:
        Table(unsigned w,unsigned h, unsigned tw,unsigned th)
            : width(w), height(h),
              tilewidth(tw), tileheight(th),
              cells()
        {
            cells.reserve(w*h);
        }
        
        void AddCell(const CellType& cell)
        {
            cells.push_back(cell);
        }
        
        void Optimize()
        {
            unsigned bestw = 0, besth = 0, bestx = 0, besty = 0;
            
            for(unsigned x=0; x<width; ++x)
                for(unsigned y=0; y<height; ++y)
                {
                    // Find out what kind of rowspan/colspan would be possible at this slot
                    CellType& cell = cells[cp(x,y)];
                    if(cell.masked) continue;    // part of another span-cell
                    if(cell.tried_1x1) continue; // already found to be simply 1x1
                    if(cell.decided) continue;   // already decided to be a span-cell
                    
                    unsigned maxcol = width, maxw = 1, maxh = 1;
                    for(unsigned y2=y; y2<height; ++y2)
                    {
                        unsigned w=0, h=y2-y;
                        for(unsigned x2=x; x2<maxcol; ++x2)
                        {
                            const CellType& cell2 = cells[cp(x2,y2)];
                            if(cell2.masked || cell2.decided) break;
                            
                            if(!cell2.CanExtend(cell, w,h, tilewidth,tileheight)) break;
                            ++w;
                        }
                        if(w < 1) break;
                        ++h;
                        unsigned size = h*w;
                        if(size >= maxw*maxh) { maxw=w; maxh=h; }
                        w += x;
                        if(w < maxcol) maxcol = w;
                    }
                    //fprintf(stderr, "Suggest(%d,%d): %d,%d\n", x,y, maxw,maxh);
                    if(maxw*maxh > bestw*besth)
                    {
                        bestw = maxw;
                        besth = maxh;
                        bestx = x;
                        besty = y;
                    }
                    if(maxw == 1 && maxh == 1)
                    {
                        cell.tried_1x1 = true;
                    }
                }
            
            if(bestw > 1 || besth > 1)
            {
                //fprintf(stderr, "yay, %dx%d at %d,%d\n", bestw,besty, bestx,besty);
                MarkRectangle(bestx,besty, bestw,besth);
                Optimize(); // tail call, find more spans
            }
        }
        
        void MarkRectangle(unsigned xpos,unsigned ypos, unsigned width,unsigned height)
        {
            for(unsigned y=ypos; y<ypos+height; ++y)
                for(unsigned x=xpos; x<xpos+width; ++x)
                {
                    CellType& cell = cells[cp(x,y)];
                    if(x == xpos && y == ypos)
                    {
                        cell.colspan = width;
                        cell.rowspan = height;
                        cell.decided = true;
                        cell.masked = false;
                    }
                    else
                        cell.masked = true;
                }
        }
        
        void Dump()
        {
            unsigned ncells = width*height;
            for(unsigned cellno=0; cellno<ncells; ++cellno)
            {
                std::printf("%d:%d:%d\n",
                    cells[cellno].masked,
                    cells[cellno].colspan,
                    cells[cellno].rowspan);
            }
        }
        
        unsigned cp(unsigned x,unsigned y) const { return x + y*width; }
    };
}

image_tilemapper_fun.php

<?php

function TilemapImage($im, &$sections)
{
  $alltiles = Array(); // crc32 => (xs,ys, xpos,ypos, doneflag)
  
  foreach($sections as $sectname => &$sectcoords) // xs,ys, xpos,ypos, sizex,sizey,tilelist
  {
    $width  = $sectcoords[0];
    $height = $sectcoords[1];
    $xpos = $sectcoords[2];
    $ypos = $sectcoords[3];
    $sizex = $sectcoords[4];
    $sizey = $sectcoords[5];
    
    if(!$sizex || !$sizey)
    {
      CalculateOptimalTilesize($width,$height, $sizex,$sizey);
    }
    
    #print "Chose $sizex,$sizey for $width,$height\n";
    
    $tilelist = Array();
    
    for($y=0; $y<$height; $y+=$sizey)
      for($x=0; $x<$width; $x+=$sizex)
      {
        $sx = min($sizex,$width-$x);
        $sy = min($sizey,$height-$y);
        $crc32 = Crc32Image($im, $xpos+$x,$ypos+$y, $sx,$sy);
        if(!isset($alltiles[$crc32]))
          $alltiles[$crc32] = Array($sx,$sy, $xpos+$x,$ypos+$y, false);
        $tilelist[] = Array($x,$y, $crc32);
      }
    
    $sectcoords[4] = $sizex;
    $sectcoords[5] = $sizey;
    $sectcoords[6] = $tilelist;
  }
  
  $puzzle = Array();
  
  foreach($sections as $sectname => &$sectcoords)
  {
    $width  = $sectcoords[0]; $sizex = $sectcoords[4]; $xpos = $sectcoords[2];
    $height = $sectcoords[1]; $sizey = $sectcoords[5]; $ypos = $sectcoords[3];
    $tilelist = &$sectcoords[6]; // crc32, doneflag. doneflags: 0=not, 1=new, 2=irrelevant
    
    $localset = Array();
    $piece = Array();
    $wid = ceil($width/$sizex);
    $hei = ceil($height/$sizey);
    
    $p=0;
    for($y=0; $y<$hei; ++$y)
      for($x=0; $x<$wid; ++$x)
      {
        $crc32 = $tilelist[$p++][2];
        $piece[$y][$x] = (!(isset($localset[$crc32]) || $alltiles[$crc32][4]));
        //     ? $crc32
        //     : false;
        $localset[$crc32] = true;
      }
    unset($localset);
    
    PutMask($piece,        /* false/true map of which tiles need placing */
            $puzzle,       /* Currently organized blocks */
            $wid,$hei,     /* Geometry of this block */
            $sizex,$sizey  /* Geometry of the tiles */
           );

    $p=0;
    for($y=0; $y<$hei; ++$y)
      for($x=0; $x<$wid; ++$x)
      {
        $dx = $piece[$y][$x][0];
        $dy = $piece[$y][$x][1];

        $sx = min($sizex,$width -$x*$sizex);
        $sy = min($sizey,$height-$y*$sizey);
        
        $crc32 = $tilelist[$p][2];
        if(!$alltiles[$crc32][4])
        {
          $alltiles[$crc32][0] = $dx;
          $alltiles[$crc32][1] = $dy;
          $alltiles[$crc32][4] = true;
          $puzzle[$dy][$dx] = Array($sx,$sy,$crc32, "$sectname $x,$y");
        }
        else
        {
          $dx = $alltiles[$crc32][0];
          $dy = $alltiles[$crc32][1];
        }
        
        $tilelist[$p][0] = $dx;
        $tilelist[$p][1] = $dy;
        ++$p;
      }
    #print_r($puzzle);
    #print "$sectname:\n";
    #dump($tilelist);
  }
  unset($tilelist);
  
  #print "plan:\n";
  #print_r($puzzle);
  //dump($puzzle);

  /* Figure out the extents of the puzzle */
  $minx=0; $maxx=0;
  $miny=0; $maxy=0;
  foreach($puzzle as $y=>$row)
    foreach($row as $x=>$cell)
    {
      $maxx = max($maxx, $x+$cell[0]);
      $maxy = max($maxy, $y+$cell[1]);
      
      #print "{$cell[0]},{$cell[1]} at $x,$y\n";
    }
  
  //print_r($alltiles);
  
  $result = ImageCreateTrueColor($maxx,$maxy);
  ImageAlphaBlending($result, false);
  $tp = ImageColorAllocateAlpha($result, 0,0,0,127);
  ImageFilledRectangle($result, 0,0, $maxx,$maxy, $tp);
  ImageSaveAlpha($result, true);
  ImageAlphaBlending($result, true);
  foreach($puzzle as $y=>$row)
    foreach($row as $x=>$cell)
    {
      $crc32 = $cell[2];
      ImageCopy($result,$im,
        // target position
        $x,$y,
        // source position
        $alltiles[$crc32][2],
        $alltiles[$crc32][3],
        // width, height
        $cell[0],
        $cell[1]);
    }
  
  return $result;
}

function CalculateOptimalTilesize($width,$height, &$sizex,&$sizey)
{
  $sizex = CalculateOptimalDivisor($width);
  $sizey = CalculateOptimalDivisor($height);
}
function CalculateOptimalDivisor($value)
{
  //if($value % 2 == 0)  return 2;
  //if($value % 10 == 0)  return 10;
  //if($value % 4 == 0)  return 4;
  if($value >= 480)
  {
    if($value % 128 == 0)  return 128;
    if($value % 64 == 0)  return 64;
  }

  if($value >= 160)
  {
    if($value % 32 == 0)  return 32;
    if($value % 16 == 0)  return 16;
  }

  //if($value % 2 == 0) return $value / 2;

  //if($value % 8 == 0)  return 8;
  //if($value % 5 == 0)  return 5;
  //return 8;
  
  return $value;
}

function Crc32Image($tile, $xpos,$ypos, $sx,$sy)
{
  $result = '';
  for($y=0; $y<$sy; ++$y)
    for($x=0; $x<$sx; ++$x)
      $result .= pack('V', ImageColorAt($tile, $xpos+$x,$ypos+$y));
  return crc32($result);
}

/* piece: the image to put into the collection
 * (divided into tiles, tiles may be holes, holes indicated by false)
 * puzzle: the collection
 * wid,hei: the dimensions of the piece, in tiles
 * sizex,sizex: the dimensions of a tile, in pixels
 */
function PutMask(&$piece, $puzzle, $wid,$hei, $sizex,$sizey)
{
  $pack_cmd = "util/binpack2d -ci -sr -x$wid -y$hei -X$sizex -Y$sizey ";
  for($y=0; $y<$hei; ++$y)
    for($x=0; $x<$wid; ++$x)
      $pack_cmd .= ($piece[$y][$x] !== false) ? '1' : '0';

  foreach($puzzle as $y=>$row)
    foreach($row as $x=>$cell)
      $pack_cmd .= " $x,$y,{$cell[0]},{$cell[1]}";

  file_put_contents('php://stderr', "$pack_cmd\n");
  
  exec($pack_cmd, $pack_result);

  $i=0;
  for($y=0; $y<$hei; ++$y)
    for($x=0; $x<$wid; ++$x)
    {
      $line = $pack_result[$i++];
      sscanf($line, '%d %d', $xp,$yp);
      #print "Gets($xp)($yp)\n";
      $piece[$y][$x] = Array($xp,$yp);
    }
}

binpack2d.cc

#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

#include <getopt.h>

#include "tableoptimizer.hh"

enum PieceCompressionMethod
{
    PIECE_COMPRESSION_INTACT,
    PIECE_COMPRESSION_DELETE_EMPTY_COLUMNS_AND_ROWS,
    PIECE_COMPRESSION_MAKE_SQUARE,
    PIECE_COMPRESSION_MAKE_SQUARE_FROM_LARGE_RECTANGLES
};
enum PieceSplitMethod
{
    PIECE_SPLIT_INTACT,
    PIECE_SPLIT_EACH_TILE,
    PIECE_SPLIT_LARGE_RECTANGLES
};

struct XY
{
    unsigned x, y;

    bool operator< (const XY& b) const { if(y!=b.y) return y<b.y; return x<b.x; }
    bool operator==(const XY& b) const { return x==b.x && y==b.y; }

    XY(unsigned xx,unsigned yy) : x(xx), y(yy) { }
    XY() : x(),y() { }


    unsigned size() const { return std::max(x,y); }
};

struct Piece
{
    XY size;
    std::vector<bool> exists;
    std::vector<XY>   solution;
    
    Piece() : size(), exists(), solution() { }
    

    Piece(unsigned x,unsigned y, bool existsinit=false)
        : size(x,y), exists(x*y, existsinit), solution(x*y)
    {
    }
};

typedef std::map<XY/*where*/, XY/*tilesize*/> Puzzle; /* What areas are reserved? */

struct PieceCell: public TableOptimizer::CellBase
{
    bool exists;
    PieceCell(bool m) : exists(m) { }

    bool CanExtend(const PieceCell& b,
      unsigned,unsigned,unsigned,unsigned) const { return exists && b.exists; }
};

typedef std::vector<unsigned char> BitMaskType;

static int FitBitMask
    (const BitMaskType& puzzle_map, const XY& puzsize,
     const BitMaskType& piece_map, const XY& piesize,
     const XY& puzpos,
     const XY& piepos, const XY& slicesize)
{
    int result = 0;

    for(unsigned y=0; y<slicesize.y; ++y)
        for(unsigned x=0; x<slicesize.x; ++x)
        {
            XY piebitpos(x+piepos.x, y+piepos.y);
            unsigned piebit =
                (piebitpos.x < piesize.x && piebitpos.y < piesize.y)
                    ? piece_map[piebitpos.y * piesize.x + piebitpos.x]
                    : 2; // not-exist

            XY puzbitpos(x+puzpos.x, y+puzpos.y);
            unsigned puzbit =
                (puzbitpos.x < puzsize.x && puzbitpos.y < puzsize.y)
                    ? puzzle_map[puzbitpos.y * puzsize.x + puzbitpos.x]
                    : 0; // not-exist

            /*      &      piebit
             *   puzbit    1=exists 2=empty
             *   0=free       0       0
             *   1=resv       1       0
             *
             *      ^      piebit
             *   puzbit    1=exists 2=empty
             *   0=free       1       2
             *   1=resv       0       3
             */

            if( (piebit & puzbit) != 0)
                return -1; // collision

            result += (piebit ^ puzbit);
            // Score:
            //    Empty  -> free:  2
            //    Empty  -> resv:  3
            //    Exists -> free:  1
        }
    return result;
}

void PutPieceInPuzzle(
    Piece& piece,
    const Puzzle& puzzle,
    const XY& tilesize,
    PieceCompressionMethod compression = PIECE_COMPRESSION_INTACT,
    PieceSplitMethod split = PIECE_SPLIT_INTACT)
{
    /* Assign coordinates for each tile of the piece, relative
     * to the origin of the tile. These coordinates are stored
     * into piece.solution[]. It is not the final solution, but
     * just numbers that help the actual algorithm to know where
     * each tile is located.
     */

    // Check out which columns/rows of the piece are unused
    std::vector<bool> x_used(piece.size.x), y_used(piece.size.y);
    unsigned n_used=0;
    for(unsigned y=0; y<piece.size.y; ++y)
        for(unsigned x=0; x<piece.size.x; ++x)
            if(piece.exists[y*piece.size.x+x])
            {
                x_used[x]=true;
                y_used[y]=true;
                ++n_used;
            }

    switch(compression)
    {
        case PIECE_COMPRESSION_INTACT:
            for(unsigned y=0; y<piece.size.y; ++y)
                for(unsigned x=0; x<piece.size.x; ++x)
                {
                    piece.solution[y*piece.size.x+x].x = x*tilesize.x;
                    piece.solution[y*piece.size.x+x].y = y*tilesize.y;
                }
            break;
        case PIECE_COMPRESSION_DELETE_EMPTY_COLUMNS_AND_ROWS:
            for(unsigned yp=0, y=0; y<piece.size.y; ++y)
            {
                for(unsigned xp=0, x=0; x<piece.size.x; ++x)
                {
                    piece.solution[y*piece.size.x+x].x = xp;
                    piece.solution[y*piece.size.x+x].y = yp;
                    if(x_used[x]) xp += tilesize.x;
                }
                if(y_used[y]) yp += tilesize.y;
            }
            break;
        case PIECE_COMPRESSION_MAKE_SQUARE:
        {
            unsigned scramblewidth = (unsigned)(0.5+std::ceil(std::sqrt(n_used)));
            for(unsigned p=0, xp=0, yp=0, y=0; y<piece.size.y; ++y)
                for(unsigned x=0; x<piece.size.x; ++x)
                    if(piece.exists[y*piece.size.x+x])
                    {
                        piece.solution[y*piece.size.x+x].x = xp*tilesize.x;
                        piece.solution[y*piece.size.x+x].y = yp*tilesize.y;
                        ++p;
                        if(++xp >= scramblewidth) { ++yp; xp=0; }
                    }
            break;
        }
        case PIECE_COMPRESSION_MAKE_SQUARE_FROM_LARGE_RECTANGLES:
        {
            // Place each rectangle of this piece into a private puzzle,
            // and use that data for the placement of the tiles in the piece.

            PutPieceInPuzzle(piece, Puzzle(), tilesize,
                             PIECE_COMPRESSION_INTACT,
                             PIECE_SPLIT_LARGE_RECTANGLES);
            break;
        }
    }

    TableOptimizer::Table<PieceCell> table(piece.size.x, piece.size.y, 0,0);
    for(unsigned y=0; y<piece.size.y; ++y)
        for(unsigned x=0; x<piece.size.x; ++x)
        {
            PieceCell cell(piece.exists[y*piece.size.x+x]);
            if(!cell.exists) cell.masked = true;
            table.AddCell(cell);
        }

    switch(split)
    {
        case PIECE_SPLIT_INTACT:
        {
            /* The whole piece is a single cell */
            table.MarkRectangle(0,0, piece.size.x, piece.size.y);
            break;
        }
        case PIECE_SPLIT_EACH_TILE:
        {
            /* Every tile of the piece marks a separate cell */
            // Nothing to do, the cells in the table are configured like that by default.
            break;
        }
        case PIECE_SPLIT_LARGE_RECTANGLES:
        {
            /* Mark maximally large rectangles */
            table.Optimize();
            break;
        }
    }
    if(split != PIECE_SPLIT_INTACT)
    {
        /* The piece was split into multiple parts.
         * Our current algorithm cannot find the location
         * for multiple parts simultaneously, so we must
         * use recursion.
         */
        /* Get a read-write copy of the puzzle. We need it
         * because we will be calling ourselves multiple
         * times in a row, and we must have a way of marking
         * which locations have already been assigned.
         */
        Puzzle tmppuzzle = puzzle;

        for(unsigned y=0; y<piece.size.y; ++y)
            for(unsigned x=0; x<piece.size.x; ++x)
                if(piece.exists[y*piece.size.x+x])
                {
                    const PieceCell& cell = table.cells[y*piece.size.x+x];
                    if(cell.masked) continue;

                    unsigned w = cell.colspan, h = cell.rowspan;

                    // Create a solid rectangle and place it in tmppuzzle.
                    Piece tmppiece(w,h, true);

                    PutPieceInPuzzle(
                        tmppiece, tmppuzzle, tilesize,
                        PIECE_COMPRESSION_INTACT,
                        PIECE_SPLIT_INTACT);

                    // Update the actual piece's solution coordinates
                    // for this rectangle's area.
                    for(unsigned y2=0; y2<h; ++y2)
                        for(unsigned x2=0; x2<w; ++x2)
                        {
                            XY d = tmppiece.solution[y2*w+x2];
                            tmppuzzle[d] = tilesize;
                            piece.solution[(y+y2)*piece.size.x + (x+x2)] = d;
                        }
                }
        return;
    }
    else
    {
        /* We can discard "table" at this point,
         * because we won't be using it.
         */
    }

    /* Figure out the extents of the puzzle */
    XY puzmax(0,0);
    for(Puzzle::const_iterator i=puzzle.begin(); i!=puzzle.end(); ++i)
    {
        puzmax.x = std::max(puzmax.x, i->first.x + i->second.x);
        puzmax.y = std::max(puzmax.y, i->first.y + i->second.y);
    }

    /* Convert the puzzle into a bitmap */
    BitMaskType puzzle_map(puzmax.x * puzmax.y); // initialized to 0
    for(Puzzle::const_iterator i=puzzle.begin(); i!=puzzle.end(); ++i)
        for(unsigned y=0; y<i->second.y; ++y)
            for(unsigned x=0; x<i->second.x; ++x)
                puzzle_map[(x+i->first.x) + puzmax.x*(i->first.y+y)] = 1;

    /* Figure out the extents of the piece */
    XY piemax(piece.size.x * tilesize.x, piece.size.y * tilesize.y);

    /* Convert the piece into a bitmap */
    BitMaskType piece_map(piemax.x * piemax.y);
    int hole_sum = 0;
    for(unsigned y=0; y<piece.size.y; ++y)
        for(unsigned x=0; x<piece.size.x; ++x)
        {
            unsigned xp = piece.solution[y*piece.size.x+x].x;
            unsigned yp = piece.solution[y*piece.size.x+x].y;
            unsigned bit = piece.exists[y*piece.size.x+x] ? 1 : 2;
            for(unsigned py=0; py<tilesize.y; ++py)
                for(unsigned px=0; px<tilesize.x; ++px)
                    piece_map[(yp+py) * piemax.x + (xp+px)] = bit;
            if(bit != 1) ++hole_sum;
        }

    /* Decide the granularity for spots to test */
    XY step = tilesize;
    // XY step(1,1);

    /* Find the best spot. */
    int best=-1;
    XY bestpos;
    XY bestsize(puzmax.x + piece.size.x*tilesize.x, puzmax.y + piece.size.y*tilesize.y);
    XY origsize(puzmax.x, puzmax.y);

    // max{x,y} = puzmax rounded up to step increments
    unsigned maxx = ((puzmax.x + step.x-1) / step.x) * step.x;
    unsigned maxy = ((puzmax.y + step.y-1) / step.y) * step.y;
    for(unsigned y=0; y<=maxy; y+=step.y)
        for(unsigned x=0; x<=maxx; x+=step.x)
        {
            int good = FitBitMask(puzzle_map, puzmax,
                                  piece_map, piemax,
                                  XY(x,y),
                                  XY(0,0), piemax);
            if(good < 0) continue;

            XY newsize(std::max(puzmax.x, x + piece.size.x*tilesize.x),
                       std::max(puzmax.y, y + piece.size.y*tilesize.y));

            bool yay = best == -1;

            // Prefer a positioning that does not enlarge the picture very much.
            if(newsize.size() < bestsize.size())
                yay = true;

            if(newsize.size() == bestsize.size())
                yay = good > best;

            if(yay)
            {
                best = good;
                bestpos  = XY(x,y);
                bestsize = newsize;
                
                // Have we found a dream position?
                // A dream position is one where each hole of the piece
                // overlaps with material from the puzzle and the image
                // size is not incremented.
                if(bestsize == origsize && best == hole_sum) goto FoundBestSpot;
            }
        }
FoundBestSpot:;
    // Save the position.
    for(unsigned y=0; y<piece.size.y; ++y)
        for(unsigned x=0; x<piece.size.x; ++x)
        {
            piece.solution[y*piece.size.x+x].x += bestpos.x;
            piece.solution[y*piece.size.x+x].y += bestpos.y;
        }
}



int main(int argc, char** argv)
{
    /* Define the variables and the default options */
    Piece piece;
    Puzzle puzzle;
    XY tilesize(1,1);
    PieceCompressionMethod compression = PIECE_COMPRESSION_MAKE_SQUARE_FROM_LARGE_RECTANGLES;
    PieceSplitMethod       split       = PIECE_SPLIT_INTACT;
    
    unsigned piecesizex = 1;
    unsigned piecesizey = 1;

    for(;;)
    {
        int c = getopt(argc, argv, "c:s:x:y:X:Y:h");
        if(c == -1) break;
        switch(c)
        {
            case 'c':
                /***/if(strcmp(optarg, "i") == 0) compression = PIECE_COMPRESSION_INTACT;
                else if(strcmp(optarg, "i") == 0) compression = PIECE_COMPRESSION_DELETE_EMPTY_COLUMNS_AND_ROWS;
                else if(strcmp(optarg, "s") == 0) compression = PIECE_COMPRESSION_MAKE_SQUARE;
                else if(strcmp(optarg, "r") == 0) compression = PIECE_COMPRESSION_MAKE_SQUARE_FROM_LARGE_RECTANGLES;
                else goto ArgErr;
                break;
            case 's':
                /***/if(strcmp(optarg, "i") == 0) split = PIECE_SPLIT_INTACT;
                else if(strcmp(optarg, "e") == 0) split = PIECE_SPLIT_EACH_TILE;
                else if(strcmp(optarg, "r") == 0) split = PIECE_SPLIT_LARGE_RECTANGLES;
                else goto ArgErr;
                break;
            case 'x': piecesizex = std::atoi(optarg); break;
            case 'y': piecesizey = std::atoi(optarg); break;
            case 'X': tilesize.x = std::atoi(optarg); break;
            case 'Y': tilesize.y = std::atoi(optarg); break;
            case 'h'://thru
            default: goto ArgErr;
        }
    }
    
    piece = Piece(piecesizex,piecesizey);
    
    if(optind == argc)
    {
    ArgErr:
        std::fprintf(stderr,
            "Usage: binpack2d -x<piecesizex> -y<piecesizey>\n"
            "                 -X<tilesizex> -Y<tilesizey>\n"
            "                 [-c<compressionmethod>]\n"
            "                 [-s<splitmethod>]\n"
            "                 <piecedesc> [<puzzledesc> [...]]\n"
            "\n"
            "       Where piecedesc is a string of 0 or 1\n"
            "             Length of the string must be piecesizex*piecesizey\n"
            "             0=hole, 1=exists\n"
            "       And puzzledesc is xpos,ypos,xsize,ysize (all units are pixels)\n"
            "             Each entry describes a reserved section\n"
            "       Unit of piecesize is tiles\n"
            "       Unit of tilesize is pixels\n"
            "\n"
            "       Compressionmethods:\n"
            "           i = keep the shape of the piece intact\n"
            "           d = delete empty columns and rows\n"
            "           s = reshape the piece into a square\n"
            "           r = reshape the piece into a square of optimal rectangles (default)\n"
            "       Splitmethods:\n"
            "           i = intact, arrange the piece as whole (default)\n"
            "           e = each tile of the piece is arranged separately\n"
            "           r = each optimal rectangle of the piece is arranged separately\n"
            "\n"
            "       Output is lines of: <xpos> <ypos>\n"
            "       Units of position are pixels\n"
            "       Each line tells the positioning for one part of the piece\n"
            "\n");
        return -1;
    }
    
    for(unsigned a=0; a<piecesizex*piecesizey; ++a)
        piece.exists[a] = argv[optind][a] != '0';
    
    for(int a=optind+1; a<argc; ++a)
    {
        int xpos=0,ypos=0, xsize=0,ysize=0;
        std::sscanf(argv[a], "%d,%d,%d,%d", &xpos,&ypos,&xsize,&ysize);
        if(xsize && ysize)
            puzzle[XY(xpos,ypos)] = XY(xsize,ysize);
    }
    
    /* Do the bulk of the work */
    PutPieceInPuzzle(piece, puzzle, tilesize, compression, split);
    
    /* Output the solution */
    for(unsigned y=0; y<piece.size.y; ++y)
        for(unsigned x=0; x<piece.size.x; ++x)
            printf("%u %u\n",
                piece.solution[y*piece.size.x+x].x,
                piece.solution[y*piece.size.x+x].y);
}

Example use of image_tilemapper_fun.php

<?php

require 'image_tilemapper_fun.php';

error_reporting(E_ERROR);

$im = ImageCreateFromPng('../css/ratingbg.png');
ImageAlphaBlending($im, false);

$sections = Array(
  'tasvideos'    => Array(76,15, 50,36),
  'stuff'        => Array(52,10, 51,51),
  'background'   => Array(300,20, 0,0,    5,5),
  'xkeeper'      => Array(54,8, 50,60),
  'megaman'      => Array(25,13, 103,51, 5,13),
  'cursor_c'     => Array(20,20, 0,40, 5,5),
  'cursor_i'     => Array(5,20, 38,40, 5,5),
  'indicator_c'  => Array(20,20, 0,20, 5,5),
  'indicator_i'  => Array(5,20, 38,20, 5,5),
  'petA0' => Array(16,24,128+16*0,20,   8,8),
  'petA1' => Array(16,24,128+16*1,20,   8,8),
  'petA2' => Array(16,24,128+16*2,20,   8,8),
  'petA3' => Array(16,24,128+16*3,20,   8,8),
  'petA4' => Array(16,24,128+16*4,20,   8,8),
  'petA5' => Array(16,24,128+16*5,20,   8,8),
  'petA6' => Array(16,24,128+16*6,20,   8,8),
  'petA7' => Array(16,24,128+16*7,20,   8,8),
  'petB0' => Array(16,24,128+16*0,44,   8,8),
  'petB1' => Array(16,24,128+16*1,44,   8,8),
  'petB2' => Array(16,24,128+16*2,44,   8,8),
  'petB3' => Array(16,24,128+16*3,44,   8,8),
  'petB4' => Array(16,24,128+16*4,44,   8,8),
  'petB5' => Array(16,24,128+16*5,44,   8,8),
  'petB6' => Array(16,24,128+16*6,44,   8,8),
  'petB7' => Array(16,24,128+16*7,44,   8,8),
  'fb0g' => Array(8,8, 56+8*0,20),
  'fb1g' => Array(8,8, 56+8*1,20),
  'fb2g' => Array(8,8, 56+8*2,20),
  'fb3g' => Array(8,8, 56+8*3,20),
  'fb4g' => Array(8,8, 56+8*4,20),
  'fb5g' => Array(8,8, 56+8*5,20),
  'fb6g' => Array(8,8, 56+8*6,20),
  'fb7g' => Array(8,8, 56+8*7,20),
  'fb8g' => Array(8,8, 56+8*8,20),
  'fb0r' => Array(8,8, 56+8*0,28),
  'fb1r' => Array(8,8, 56+8*1,28),
  'fb2r' => Array(8,8, 56+8*2,28),
  'fb3r' => Array(8,8, 56+8*3,28),
  'fb4r' => Array(8,8, 56+8*4,28),
  'fb5r' => Array(8,8, 56+8*5,28),
  'fb6r' => Array(8,8, 56+8*6,28),
  'fb7r' => Array(8,8, 56+8*7,28),
  'fb8r' => Array(8,8, 56+8*8,28)
);

$result = TilemapImage($im, $sections);

ImagePng($result, '/WWW/imagemergetest.png');

echo '<img src="/imagemergetest.png">';

$gdata = Array();
foreach($sections as $sectname => &$sectcoords)
{
  $width  = $sectcoords[0]; $sizex = $sectcoords[4]; $xpos = $sectcoords[2];
  $height = $sectcoords[1]; $sizey = $sectcoords[5]; $ypos = $sectcoords[3];
  $tilelist = $sectcoords[6]; // crc32, doneflag. doneflags: 0=not, 1=new, 2=irrelevant
  $wid = $width /$sizex;
  $hei = $height/$sizey;
  
  $data = '';
  for($y=$p=0; $y<$hei; ++$y)
    for($x=0; $x<$wid; ++$x)
      $data .= chr(65+$tilelist[$p++][0] / $sizex);
  for($y=$p=0; $y<$hei; ++$y)
    for($x=0; $x<$wid; ++$x)
      $data .= chr(65+$tilelist[$p++][1] / $sizey);
  $data = Array('x'=>$sizex,'y'=>$sizey, $data);
  $gdata[$sectname] = $data;
  
  echo "<h3>$sectname</h3>";
  echo '<table cellspacing=0 cellpadding=0>';
  $p=0;
  for($y=0; $y<$hei; ++$y)
  {
    echo '<tr>';
    for($x=0; $x<$wid; ++$x)
    {
      $dx = $tilelist[$p][0];
      $dy = $tilelist[$p][1];
      $style = 'background:url("/imagemergetest.png")'." no-repeat -{$dx}px -{$dy}px";
      echo "<td width=$sizex height=$sizey style='".htmlspecialchars($style)."'>";
      ++$p;
    }
    echo '</tr>';
  }
  echo '</table>';
}
print_r($gdata);