Uniform rectangle packing

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

 

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;
}