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...