Subj : Re: stacking algorithm
To   : comp.programming
From : Scott McPhillips [MVP]
Date : Thu Aug 04 2005 12:16 am

nobiscuit wrote:
> Hi,
> 
> I need some pointers on a good place to start with an algorithm to
> solve this problem.
> 
> Given an arbitrary collection of lines with differing 'lengths' and
> starting points - like this:
> 
> ---------   (length = 9, start = 0)
>   ---       (length = 3, start = 2)
> --          etc
> -----------
>     -----
>        -----
> ---
> 
> 
> And a fixed width 'tray' to place them in, like this:
> 
> 
> |____________|  (length = 12)
> 
> 
> 
> I need to find a way to 'stack' them in a reasonably efficient way -
> like this:
> 
> 
> (Gaps in between lines shown for clarity)
> 
>  --- -----
>  -- ---	-----
>  ---------
>  -----------
> |____________|  TRAY
> 
> 
> The code I inherited just checks the starting point of the current line
> being processed against the ending point of the previous line being
> processed and if there is overlap it moves the current line up a level
> in the stack.  This creates situations like this:
> 
>           ------
>     ----------
> --------
> 
> The requirements team wants something like this instead:
> 
>     ----------
> --------  ------
> 
> 
> I figure this has to be a pretty common problem.  I did a google search
> but didn't find anything.  Can anyone suggest an algorithm which is
> similar or does anyone have any cunning suggestions for an algorithm?
> 
> Thanks!
> 

I had to solve this for a practical application involving circuit board 
layers.  My algorithm was "Do your best to use all the space on each 
layer before starting on the next layer."  So you place the longest line 
that will fit, then iterate until nothing else will fit on the current 
layer.  Thinking about it backwards, this algoritm tends to minimize 
wasted space, which tends to minimize the number of layers required.

-- 
Scott McPhillips [VC++ MVP]

.