21
Replies
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
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
That's an extremely wicked script! No complaints at all about the speed (2.67GHz PC) -- it rips right through a moderately large document.
I also checked out both the rectangle packing problem and Wordle. Extracting the interesting words is easy, but packing them at random is hard. So I gave up on that 🙂 Kudos to you, Marc!
Here is a Wordle of my JS Help page. It's funny how a few words end up inside other words -- I don't think that's intentional, but I like it!
AdChoices