Finding Optimal Cell Size for 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

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

 

[ktoz]

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

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