21 Replies Latest reply on Apr 7, 2010 9:27 AM by Marc Autret

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

    amm09

      Is there any way to automatically have selected objects be transformed (rotated if needed and moved) to have them be arranged to take up the smallest amount of space on a page without having to visually do it myself?

        • 4. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a page?
          nickdclements Level 1

          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://freehackers.org/~tnagy/linpacker/linpackerng-tb.png

           

           

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

          • 5. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a page?
            amm09 Level 1

            nope, I've been looking some more for Photoshop and some other programs, but

            nothing yet. I'll have to check out your links. Thanks!

            • 8. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a pa
              RorohikoKris-u5pUJw Level 2

              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

              • 9. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a page?
                Marc Autret Level 4

                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[i].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[j].a >= a ) i=j; else k=j;
                               }
                          return (items[k].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[i];
                               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[s] > sWH[s] );     // overflow
                          var rfx = sXY[s] + opp*sWH[s];     // reference axis
                          var minMax = ovf ? [sWH[s],wh[s]] : [wh[s],sWH[s]];
                          
                          ret[s] = rfx - opp*wh[s];
                          sXY[s] = rfx - opp*minMax[1];
                          sWH[s] = minMax[1];
                          oXY[s] = rfx + (1-2*opp)*minMax[opp];
                          oWH[s] = minMax[1]-minMax[0];
                          s = 1-s;
                          if( ovf ) oXY[s] = sXY[s];
                          if( !osd ) sXY[s] -= wh[s];
                          ret[s] = sXY[s] + osd*sWH[s];
                          oWH[s] = ovf ? sWH[s] : wh[s];
                          sWH[s] += wh[s];
                          if( !ovf ) oXY[s] = ret[s];
                
                          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[i][0],whs[i][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[i][0], pks[i][1], whEntries[i][0], whEntries[i][1]);
                     };
                

                 

                Here is a sample result (ID CS4 Win):

                Parking-test.jpg

                @+

                 

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

                • 10. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a pa
                  RorohikoKris-u5pUJw Level 2

                  Hi Marc,

                   

                  Cool script! It's fun stuff, eh?

                   

                  It's been a long time since I did anything in this regard, so I might be wrong, but by the looks of it, it should be possible to get a substantially tighter packing; there's quite a bit of white. That's where the fun starts!

                   

                  But then again, in practical terms, this script of yours, or a derivative thereof, could be sufficient for most intents and purposes - it all boils down to what is 'good enough'?

                   

                  If the cost of having unused areas is low, nobody cares whether you're reaching, say, 60% instead of 90% packing density. On the other hand, if the cost of unused areas is sufficiently high, 60% vs. 90% can add up to a significant difference.

                   

                  My hunch is that there is not really a demand for highly optimized packing, and quick-and-loose will do fine for most users, so I think there is little point in putting in a lot of effort trying to gain a few extra percentages of density - but then, who knows?

                   

                  Cheers,

                   

                  Kris

                  • 11. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a pa
                    Harbs. Level 6

                    I would probably take some real market analysis to figure out what the demand of such a thing would really be. Not to mention the need to actually marketing it as a solution...

                     

                    Two areas that none of us "geeks" are very good at...

                     

                    Harbs

                    • 12. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a pa
                      RorohikoKris-u5pUJw Level 2

                      Hear, hear! That's a big truth, that's for sure. I cannot count the times I've come up with a solution - and found out there was no problem to go with it ;-)

                      • 13. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a pa
                        Marc Autret Level 4

                        Guys, you're so right!

                         

                        But maybe the "coding brain" needs to work like a muscle. Coding for nothing is coding for learning.

                         

                        @+

                        Marc

                        • 14. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a pa
                          [Jongware] Most Valuable Participant

                          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!

                           

                          jwwordle.PNG

                          • 15. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a pa
                            Marc Autret Level 4

                            Hi Jongware,

                             

                            Thanks for your feedback ;-)

                             

                            It's funny how a few words end up inside other words -- I don't think that's intentional, but I like it!

                             

                            That's because "Allow Internal Words".is checked in the Wordalizer UI dialog.

                             

                            @+

                            Marc

                            • 18. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a pa
                              amm09 Level 1

                              Yes, this would probably take a lot of work. I hadn't realized it was quite so complex a process.

                               

                              For the purposes of my original post I was just hoping to get rectangles packed relatively tightly. White space would be desired because the document I am creating is sent to a vendor who uses it to create metal die cuts. They create our sheets exactly as they are sent in the .eps file and we get charged the amount of linear space used, i.e. if we use 7 inches of an 11 inch page we get charged for the 7 inches, but if we could fit all of our templates into 5 inches it would obviously be more desirable. 

                               

                              The very tricky part about my particular request (whether or not it gets done, it's interesting to consider) is that I would even be okay with rectangles getting rotated in order to fit more tightly.

                               

                              Overall the savings wouldn't be worth it to pay for a script to be created because it would not save enough time or money. I guess I'll continue to pack the rectangles by eye.

                               

                              Thanks!

                              • 19. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a page?
                                jay fresno Level 1

                                Is there a setting to vary the size of the words using Wordalizer? It varies the point size when using Test, but if I use my own file the words are always the same size.

                                Withdrawing question: After reading the FAQ, I found the answer.

                                • 20. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a page?
                                  Marc Autret Level 4

                                  jay fresno wrote:

                                   

                                  Is there a setting to vary the size of the words using Wordalizer?.

                                   

                                  Wordalizer parses the source text and creates a list of "weighted words" according to the frequency. However, you can input directly a weighted word list (love:10 faith:8 death:5...) using the syntax <word>:<weight> for each term (in a text frame, a text file, or the clipboard). That's still one of the hidden features of this "beta-test" script. Note that I mentioned it here just for fun --I don't want to interfere the main discussion--, so I suggest you to post Wordalizer specific requests in the dedicated script page: http://www.indiscripts.com/post/2010/01/wordalizer-a-tribute-to-wordle

                                   

                                  Thanks,

                                  Marc

                                  • 21. Re: Any way to automatically arrange selected objects to fit into the smallest area possible on a page?
                                    Marc Autret Level 4

                                    Just for your information, the final release of Wordalizer is available now:

                                    http://www.indiscripts.com/post/2010/04/wordalizer-125-create-word-clouds-in-indesign

                                     

                                    A big thank you to Jongware and Peter Kahrel, who kindly participated in beta testing and have provided me with valuable feedback.

                                     

                                    @+

                                    Marc

                                    http://www.indiscripts.com