Best fit Paper algorithms

Dev Shed Forums Sponsor:

August 20th, 2003, 09:33 AM

sam@pcm

Contributing User

Join Date: Jun 2002

Location: South Africa - Johannesburg

Posts: 30

Time spent in forums: 1 h 40 sec
Reputation Power: 7

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

August 21st, 2003, 01:27 PM

epl

Contributing User

Join Date: Mar 2001

Location: Dublin

Posts: 413

Time spent in forums: 2 h 18 m 18 sec
Reputation Power: 8

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 01:30 PM.

August 21st, 2003, 02:43 PM

sam@pcm

Contributing User

Join Date: Jun 2002

Location: South Africa - Johannesburg

Posts: 30

Time spent in forums: 1 h 40 sec
Reputation Power: 7

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 ) < 5 )

                {

                    $size_id = $row[id];

                    $pecentage_cover_best = $percentage_cover;                

                }

            }

        }

        

        $Size = new Size($this->DB,$size_id);

        return $Size;

    }

August 21st, 2003, 05:47 PM

dog135

Doggie

Join Date: Jul 2003

Location: Seattle, WA

Posts: 751

Time spent in forums: 10 h 38 m 25 sec
Reputation Power: 7

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)

August 22nd, 2003, 03:52 AM

sam@pcm

Contributing User

Join Date: Jun 2002

Location: South Africa - Johannesburg

Posts: 30

Time spent in forums: 1 h 40 sec
Reputation Power: 7

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

Thread Tools	Search this Thread
Email this Page	Search this Thread: Advanced Search
Display Modes	Rate This Thread
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode	Rate This Thread: