#1
  1. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2002
    Location
    South Africa - Johannesburg
    Posts
    30
    Rep Power
    13

    Best fit Paper algorithms


    Hi There


    This is a problem that I have been really struggling with. But then again I suppose thats the common ground with any difficult algorithm.

    I am writing an application for a printing company and the question is:

    Given a desired output paper size of length x1 and height y1. Then what paper, from a given set of paper sizes, will minimise paper wastage and maximise throughput.

    Here is a simple example:
    consider output paper size is A4. I have paper options A2,A3 available. Then A4 fits 4 times on A3 and 16 times on A2. Laying A4 over A3 or A2 has no wastage. So in this case we would use A2 on the print run. This would maximise throughput.

    Now that was a nice simple example because there was no wastage. When wastage comes into play it gets a lot more complicated.

    Consider if we had a smaller piece of paper than A4 and laying it over A2 resulted in more wastage than laying it over A3. The we would definitely use A3 paper because to minimise wastage is out primary goal.

    Her is my initial algorithm and its not ideal requiring a lot of mods. Note that % returns the remainder of the quotient.

    PHP Code:
    while ( available paper sizes 
    if (  
    x1 xi  diff1 )  &&  ( y1 yi  diff2 
    {
         
    then choose this paper size
    }
    if (  
    x1 yi  diff1 )  &&  ( y1 xi  diff2 
    {
         
    then choose this paper size


    Thanks all
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2001
    Location
    Dublin
    Posts
    413
    Rep Power
    14
    how about this...
    Code:
    //given document dimensions x * y
    minW=1;//proportion of sheet wasted
    minX=default width / A2 width;
    minY=default length / A2 length;
    for each paper size xx * yy
     {w=calculateWastage(x,y,xx,yy);
      if (w<minW)
       {minW=w;
        minX=xx;
        minY=yy;// or just store A2 / A3 / etc. 
       }
     }
    Code:
    calculateWastage(x,y,xx,yy)//paramters passed by value
     {x=xx%x;
      y=yy%y;
      return x/xx+y/yy-(x*y)/(xx*yy);
     }
    obviously you can also try switching the x and y coordinates and rerunning just in case laying the documents out sideways produces less wastage etc
    Last edited by epl; August 21st, 2003 at 12:30 PM.
  4. #3
  5. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2002
    Location
    South Africa - Johannesburg
    Posts
    30
    Rep Power
    13
    OK

    After thinking about this problem for a while and working through it, I realise I was way of the mark with the first algorithm.

    Some of the issues that influence the solution are:

    1. You can place the original paper over the new paper in any orientation i.e. Portrait or Landscape. So we must work out which orientation produces the best utilisation.
    2. Also an overlay cannot result in less than the entire original being overlaid on the new. A complete original overlay on the new piece of paper is necessary.

    Thanks epl the idea of using a calculate wastage helped a lot. I ended up calculating what percentage of paper was wasted.

    Anyway this is what I came up with. Please excuse the fact that the algorithm is presented here in PHP code but really the code format is immaterial.

    PHP Code:
        function area_used($x1,$y1,$x2,y2)
        {
            
    // Laying the paper landscape on landscape
            
    $div_11 = (int)  $x1 $x2 ;
            
    $div_12 = (int)  $y1 $y2 ;
            
    $cuts_1 $div_12 $div_11 ;

            
    // Laying the paper protrait on landscape
            
    $div_21 = (int) $x1 $y2 
            
    $div_22 = (int) $y1 $x2 ;
            
    $cuts_2 $div_22 $div_21 
                
            
    // How many time we can lay our origional over the new
            
    $cuts max($cuts_1,$cuts_2);
            
            
    // Areas    
            
    $a1 $x1 $y1 
            
    $a2 $x2 $y2 ;
                
            
    $used_area $cuts $a1 ;
            
    $percentage_used $used_area $a2 100;
            
            return     
    $percentage_used;
        }
        
        
    // Returns the minimum Size object that utilises the highest percentage of paper area. 
        
    function get_smallest_best_fit()
        {    
            
    $sql_query "SELECT `id`, `name`, `height_mm`, `width_mm`
                          FROM `q_size` ORDER BY `height_mm` ASC"
    ;     
            
    $this->DB->sql_query($sql_query);

            
    $pecentage_cover_best 0// The worst case when no paper is used
            
    $x $this->val[height_mm]; // Dimension of the origional paper
            
    $y $this->val[width_mm];        
            while ( 
    $row $this->DB->sql_fetchrow() )
            {
                
    $x_i $row[height_mm];
                
    $y_i $row[width_mm];

                
    $percentage_cover $this->area_used($x1,$y1,$x2,y2);
                
                if  ( 
    $percentage_cover $pecentage_cover_best )
                {
                    
    // Percentage cover increase must be greater than 5% for this situation 
                    
    if ( ($percentage_cover $pecentage_cover_best ) < )
                    {
                        
    $size_id $row[id];
                        
    $pecentage_cover_best $percentage_cover;                
                    }
                }
            }
            
            
    $Size = new Size($this->DB,$size_id);
            return 
    $Size;
        } 
  6. #4
  7. Doggie
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2003
    Location
    Seattle, WA
    Posts
    751
    Rep Power
    13
    Can you mix portrait and landscape?

    ie: Fit three vertical images along the botton, and two horizontal images along the top.

    Not trying to make things difficult or anything... well.. yeah I am.

    Rather then doing:
    $cuts = max($cuts_1,$cuts_2);

    you may want to figure out the area of waste for each papersize and orientation and take the min of that list.

    (You may be able to fit 4 cuts on one sheet with no waste, and 6 cuts on another sheet with some waste. In which case you'd pick the one with 4 cuts)
  8. #5
  9. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2002
    Location
    South Africa - Johannesburg
    Posts
    30
    Rep Power
    13
    Nah it does not mix Landscape and Portrait

    I suppose that would be the best possible situation. Bummer I thought I had solved this.

    That is pretty difficult and would require some sort of bin packing algorithm. Anybody have any ideas on how to do that

    Sam

IMN logo majestic logo threadwatch logo seochat tools logo