1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Uniform rectangle packing

  1. May 23, 2009 #1
    Hi

    I'm writing a newspaper page management application and am having trouble trying to directly calculate a "best fit" column/row breakdown for displaying pages into arbitrary rectangles.

    The arbitrary rectangle in question is the content area of a window and can be resized at will by the user. The pages are a uniform fixed size and the problem is to calculate the best scale and column/row breakdown to display all the pages in the given rectangle with the least wasted space.

    Here are the knowns:
    vw = width of enclosing view
    vh = height of enclosing view
    pw = width of the page
    ph = height of the page
    pct = number of pages to be displayed in the view

    Unknowns:
    c = columns
    r = rows
    s = scaling factor
    cw = cell width
    ch = cell height

    After a bit of trial and error, I found that the optimal solution exists when

    1 - (c * pw * vh) / (r * ph * vw) = 0;

    Where r equals

    r = floor(pct / c);
    r += (c * r - pct < 0) ? 1 : 0 ;


    I wrote a C function that is fairly efficient, but was wondering if there is a more direct way to find the zero.

    Here's the C function
    Code (Text):

    for (c = 1; c < pct + 1; c++)
    {
        // calculate the number of rows
        r   = floor(pct / c);
        r   += (c * r - pct < 0) ? 1 : 0 ;
       
        // test for zero cross
        if (1 - (c * pw * vh) / (vr * ph * vw) < 0)
        {
            // found zero, decrement c and calculate scale
            c--;
           
            // calculate the scale
            s   = vw / (c * pw);
           
            // set the cell dimensions
            cw  = s * pw;
            ch  = s * ph;
           
            // since we've found the zero, exit the loop
            break;
        }
    }
     
    Thanks for any help
     
    Last edited: May 23, 2009
  2. jcsd
  3. May 23, 2009 #2
    Came up with a much more accurate function. The last one didn't work as well as I thought at first

    Code (Text):

    bool CalculateCellSize(float vw, float vh, float pw, float ph, int pct, float *outWidth, float *outHeight)
    {
        if (vw > 1)
        {
            bool    exeOK   = false;

            int lim = sqrt(vw - 1),
                c,
                r;
                   
            float   va  = vw * vh,
                pr  = ph / pw;
       
            for (c = 1; c < lim; c++)
            {
                r   = pct / c + ((pct % c) > 0);
                cw  = vw / c;
                ch  = cw * pr;
               
                if (r * ch ≤ vh)
                {
                    *outWidth   = cw;
                    *outHeight  = ch;
                    exeOK       = true;
                    break;
                }
            }
           
            return exeOK;
        }
       
        return false;
    }

     
     
    Last edited: May 24, 2009
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Uniform rectangle packing
  1. Close packing (Replies: 5)

  2. Rectangle in a circle (Replies: 5)

  3. Packing Problem (Replies: 11)

Loading...