Any way to automatically arrange selected objects to fit into the smallest area possible on a page?

Hi again,

During the development of Wordalizer, I tried a lot of "packing" techniques in JavaScript.

The code below is not used in my final script, but I wonder if it could be use for other purposes...

// IMPORTANT:
// To test this snippet, create a blank document mesured in POINTS
// and drag the axis origin at the center of the page (approximatly)

// The whEntries array is the input = a table of rectangle dims
// that you must sort by decreasing area

// The code try to pack the rectangles in a minimal space


var Parking = (function()
{
var Holes = function(/*num*/minArea)
     {
     var items = [],
          count = 0;

     var remove = function(i)
          { // removes the item #i (and returns the deleted item)
          count--;
          return items.splice(i,1)[0];
          };

     var findMaxIndexForArea = function(a)
          { // returns the max i such as items.a>=a | -1 on failure
          if( items[0].a < a ) return -1;
          if( items[count-1].a >= a ) return count-1;
          
          var i=0, j, k=count-1;
          while( (k-i) > 1 )
               {
               j = ~~((i+k)/2);
               if( items.a >= a ) i=j; else k=j;
               }
          return (items.a>=a)?k:i;
          };

     var insert = function(/*[0:x,1:y,2:w,3:h,4:a]*/t)
          { // create a new item from the array and insert it
            // returns index of inserted
          var i = (count)?(1+findMaxIndexForArea(t[4])):0;
          items.splice(i,0,{x:t[0],y:t[1],w:t[2],h:t[3],a:t[4]});
          count++;
          return i;
          };

     var query = function(w,h)
          { // returns the index of the optimal container of w X h
            // returns false on failure
          var a = w*h;
          for( var item, i=findMaxIndexForArea(a) ; i>=0 ; i-- )
               {
               item = items;
               if( item.w>=w && item.h>=h ) return i;
               }
          return false;
          };


     var fill = function(i,w,h)
          { // fill the hole #i with w X h, then split #i if possible
            // returns the position of the inserted rectangle
          var item = remove(i);
          
          var dh = item.h-h;
          var dw = item.w-w;
          var ox = (item.x + item.w/2 > 0) ? w : 0;
          var oy = (item.y + item.h/2 > 0) ? h : 0;
          
          // select the optimal split
          var keepMaxRow = (item.w * dh > minArea) && (h * dw > minArea);
          
          var aRow = ((keepMaxRow)?item.w:w)*dh;
          var aCol = ((keepMaxRow)?h:item.h)*dw;

          if( aRow >= minArea ) insert(
               ( keepMaxRow ) ?
               [ item.x, item.y+oy, item.w, dh, aRow ] :
               [ item.x+((ox)?0:dw), item.y+oy, w, dh, aRow ]
               );

          if( aCol >= minArea ) insert(
               ( keepMaxRow ) ?
               [ item.x+ox, item.y+((oy)?0:dh), dw, h, aRow ] :
               [ item.x+ox, item.y, dw, item.h, aRow ]
               );

          return [item.x+((ox)?0:dw), item.y+((oy)?0:dh)];
          };
          
     return {
          pack: function(w,h)
               { // Try to pack w X h in a hole
                 // Returns the [x,y] position of the packed rect if OK,
                 // else returns false
               if( count==0 ) return false;
               var i = query(w,h);
               return (i!==false) ? fill(i,w,h) : false;
               },
          conditionalInsert: function(x,y,w,h)
               {
               var a = w*h;
               return ( a>=minArea ) ? insert([x,y,w,h,a]) : false;
               },
          };
     };
     
var Space = function(/*[width,height]*/whFirst, /*[width,height]*/whLast)
     {
     var holes = Holes(whLast[0]*whLast[1]);
     var sXY = [-whFirst[0]/2,-whFirst[1]/2];
     var sWH = whFirst.concat();
     var alea = function() {return Math.random() < .5;};
     
     var packExtends = function(/*[w,h]*/wh)
          { // Extends the space as to include w X h
            // Returns the [x,y] position of the packed rect
          var ret = [0,0];
          var oXY = [0,0];
          var oWH = [0,0];
          
          var s = [wh[0]>sWH[0],wh[1]>sWH[1]];
          s = [s[0]?wh[0]:sWH[0],s[1]?wh[1]:sWH[1]];
          s = (s[0]*(sWH[1]+wh[1])) <= (s[1]*(sWH[0]+wh[0]))?0:1;
          // s==0 : HORIZONTAL PACK | s==1 : VERTICAL PACK

          var opp = alea() ? 1 : 0;          // 1 : pack from opposite corner
          var osd = alea() ? 1 : 0;          // 1 : pack on the over side
          var ovf = ( wh > sWH );     // overflow
          var rfx = sXY + opp*sWH;     // reference axis
          var minMax = ovf ? [sWH,wh] : [wh,sWH];
          
          ret = rfx - opp*wh;
          sXY = rfx - opp*minMax[1];
          sWH = minMax[1];
          oXY = rfx + (1-2*opp)*minMax[opp];
          oWH = minMax[1]-minMax[0];
          s = 1-s;
          if( ovf ) oXY = sXY;
          if( !osd ) sXY -= wh;
          ret = sXY + osd*sWH;
          oWH = ovf ? sWH : wh;
          sWH += wh;
          if( !ovf ) oXY = ret;

          holes.conditionalInsert(oXY[0],oXY[1],oWH[0],oWH[1]);
          return [ret[0],ret[1]];
          };
     
     return {
          xy: function(){return [sXY[0],sXY[1]];},
          pack: function(w,h){return holes.pack(w,h)||packExtends([w,h]);},
          };
     };

var pk = function(/*[width,height][]*/whs)
     {
     var i, count = whs.length;
     var space = new Space(whs[0],whs[count-1]);
     var positions = [space.xy()];
     for( i=1 ; i < count ; i++ )
          {
          positions.push(space.pack(whs[0],whs[1]));
          }
     return positions;
     };

return pk;
})();


var drawRec = (function()
     {
     var pgRecs = app.activeWindow.activePage.rectangles;
     return function(x,y,w,h) {pgRecs.add().geometricBounds = [y,x,y+h,x+w];};
     })();

var whEntries = [
     [120,40],
     [90,30],
     [60,30],
     [72,20],
     [72,20],
     [60,25],
     [24,50],
     [60,18],
     [50,15],
     [50,15],
     [20,45],
     [48,12],
     [45,12],
     [45,12],
     [16,40],
     [40,12],
     [32,10],
     [12,36],
     [12,36],
     [30,10],
     [30,10],
     [24,8],
     [20,8],
     [20,8],
     [8,20],
     [18,7],
     [10,20],
     [16,6],
     [12,6],
     [10,6],
     [10,4],
     ];


var pks = Parking(whEntries);

for( var i=0 ; i < pks.length ; i++ )
     {
     drawRec(pks[0], pks[1], whEntries[0], whEntries[1]);
     };

Here is a sample result (ID CS4 Win):

@+

Marc -- http://www.indiscripts.com

I'd like to know how much demand there is for a solution to this problem. I am asking because some years ago, I've been heavily involved in designing efficient algorithms to find solutions to similar issues (e.g. in the glass and furniture industry, they're not interested in just the most optimal packing - they also need to be able to physically cut the glass or wood panes along straight cutting lines - no corners allowed, which adds an extra twist to the problem).

The problem is a hard problem - a bit like chess - i.e. it is completely solvable, given enough time and computer power, but as soon as the number of rectangles increases to more than a few, calculating the proven best solution takes a enormous amount of computer cycles.

Instead, one needs to be happy with calculating a good solution (i.e. not necessarily the best) in less than an enormous amount of computer cycles - and that's where the art of algorithm design comes into play.

All that said - if no such tool exists, designing and creating a tool that would solve this to a satisfactory level is something I am able to do. But it would take quite a bit of time and effort - just the design and development cost involved to get to a usable version would easily surpass multiple $10,000s.

If there is sufficient demand, such a project could have merit. But if there are only a few takers, and they would rather have it for almost nothing or free (which seems to be the norm today), then it's a non-starter.

Any thoughts?

Cheers,

Kris

Did you ever find a solution? So far the best thing i have found for Windows is 2D Load Packer 1.8: http://www.softrecipe.com/Business-Finance/Project-Management/2d_load_packer.html it's an older program from 2006, so it didn't care for my 64bit to much, but i was able to get it running on xp just fine.

Still not exactly what were looking for though...

Linpacker for linux looks prety cool too.

http://answers.yahoo.com/question/rectangle_packing_software

You mean something like Rectangle Packing? http://en.wikipedia.org/wiki/Packing_problem