# Uniform rectangle packing

ktoz
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:
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:

ktoz
Came up with a much more accurate function. The last one didn't work as well as I thought at first

Code:
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: