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
... View more