How to optimize the layout of rectangles

Question

I have a dynamic number of equally proportioned and sized rectangular objects that I want to optimally display on the screen. I can resize the objects but need to maintain proportion.

I know what the screen dimensions are.

How can I calculate the optimal number of rows and columns that I will need to divide the screen in to and what size I will need to scale the objects to?

Thanks,

Jamie.

Answer 1

Your mention of rows and columns suggests that you envisaged arranging the rectangles in a grid, possibly with a few spaces (e.g. some of the bottom row) unfilled. Assuming this is the case:

Suppose you scale the objects such that (an as-yet unknown number) n of them fit across the screen. Then

objectScale=screenWidth/(n*objectWidth)

Now suppose there are N objects, so there will be

nRows = ceil(N/n)

rows of objects (where ceil is the Ceiling function), which will take up

nRows*objectScale*objectHeight

of vertical height. We need to find n, and want to choose the smallest n such that this distance is smaller than screenHeight.

A simple mathematical expression for n is made trickier by the presence of the ceiling function. If the number of columns is going to be fairly small, probably the easiest way to find n is just to loop through increasing n until the inequality is satisfied.

Edit: We can start the loop with the upper bound of

floor(sqrt(N*objectHeight*screenWidth/(screenHeight*objectWidth)))

for n, and work down: the solution is then found in O(sqrt(N)). An O(1) solution is to assume that

nRows = N/n + 1

or to take

n=ceil(sqrt(N*objectHeight*screenWidth/(screenHeight*objectWidth)))

(the solution of Matthieu M.) but these have the disadvantage that the value of n may not be optimal.

Border cases occur when N=0, and when N=1 and the aspect ratio of the objects is such that objectHeight/objectWidth > screenHeight/screenWidth - both of these are easy to deal with.

Answer 2

One way I like to do that is to use the square root of the area:

Let

r = number of rectangles

w = width of display

h = height of display

Then,

A = (w * h) / r is the area per rectangle

and

L = sqrt(A) is the base length of each rectangle.

If they are not square, then just multiply accordingly to keep the same ratio.

Another way to do a similar thing is to just take the square root of the number of rectangles. That'll give you one dimension of your grid (i.e. the number of columns):

C = sqrt(n) is the number of columns in your grid

and

R = n / C is the number of rows.

Note that one of these will have to ceiling and the other floor otherwise you will truncate numbers and might miss a row.

Answer 3

Assuming that all rectangles have the same dimensions and orientation and that such should not be changed.

Let's play!

// Proportion of the screen
// w,h width and height of your rectangles
// W,H width and height of the screen
// N number of your rectangles that you would like to fit in

// ratio
r = (w*H) / (h*W)

// This ratio is important since we can define the following relationship
// nbRows and nbColumns are what you are looking for
// nbColumns = nbRows * r (there will be problems of integers)
// we are looking for the minimum values of nbRows and nbColumns such that
// N <= nbRows * nbColumns = (nbRows ^ 2) * r
nbRows = ceil ( sqrt ( N / r ) ) // r is positive...
nbColumns = ceil ( N / nbRows )

I hope I got my maths right, but that cannot be far from what you are looking for ;)

EDIT: there is not much difference between having a ratio and the width and height...

// If ratio = w/h
r = ratio * (H/W)

// If ratio = h/w
r = H / (W * ratio)

And then you're back using 'r' to find out how much rows and columns use.

Answer 4

Thanks for the responses, but we don't have the info used in them, more specifically the size of the objects that need to fit inside the rectangle.

here's the info we have

• width and height of container rectangle
• width and height ratios of items to fit inside (NOTE we only have the ratios, not the actual size)
• number of items to fit inside.

Once we know the number of columns and rows, we then plan to resize the items that fit inside the container rectangle, preserving their ratios.

Hope this makes sense and thanks for any help.

Answer 5

Jamie, I interpreted "optimal number of rows and columns" to mean "how many rows and columns will provide the largest rectangles, consistent with the required proportions and screen size". Here's a simple approach for that interpretation.

Each possible choice (number of rows and columns of rectangles) results in a maximum possible size of rectangle for the specified proportions. Looping over the possible choices and computing the resulting size implements a simple linear search over the space of possible solutions. Here's a bit of code that does that, using an example screen of 480 x 640 and rectangles in a 3 x 5 proportion.

def min (a, b)
  a < b ? a : b
end

screenh, screenw = 480, 640
recth, rectw = 3.0, 5.0
ratio = recth / rectw

puts ratio

nrect = 14

(1..nrect).each do |nhigh|
  nwide = ((nrect + nhigh - 1) / nhigh).truncate
  maxh, maxw = (screenh / nhigh).truncate, (screenw / nwide).truncate
  relh, relw = (maxw * ratio).truncate, (maxh / ratio).truncate
  acth, actw = min(maxh, relh), min(maxw, relw)
  area = acth * actw
  puts ([nhigh, nwide, maxh, maxw, relh, relw, acth, actw, area].join("\t"))
end

Running that code provides the following trace:

1 14 480 45 27 800 27 45 1215
2 7 240 91 54 400 54 91 4914
3 5 160 128 76 266 76 128 9728
4 4 120 160 96 200 96 160 15360
5 3 96 213 127 160 96 160 15360
6 3 80 213 127 133 80 133 10640
7 2 68 320 192 113 68 113 7684
8 2 60 320 192 100 60 100 6000
9 2 53 320 192 88 53 88 4664
10 2 48 320 192 80 48 80 3840
11 2 43 320 192 71 43 71 3053
12 2 40 320 192 66 40 66 2640
13 2 36 320 192 60 36 60 2160
14 1 34 640 384 56 34 56 1904

From this, it's clear that either a 4x4 or 5x3 layout will produce the largest rectangles. It's also clear that the rectangle size (as a function of row count) is worst (smallest) at the extremes and best (largest) at an intermediate point. Assuming that the number of rectangles is modest, you could simply code the calculation above in your language of choice, but bail out as soon as the resulting area starts to decrease after rising to a maximum.

That's a quick and dirty (but, I hope, fairly obvious) solution. If the number of rectangles became large enough to bother, you could tweak for performance in a variety of ways:

• use a more sophisticated search algorithm (partition the space and recursively search the best segment),
• if the number of rectangles is growing during the program, keep the previous result and only search nearby solutions,
• apply a bit of calculus to get a faster, precise, but less obvious formula.

Answer 6

This is almost exactly like kenneth's question here on SO. He also wrote it up on his blog.

If you scale the proportions in one dimension so that you are packing squares, it becomes the same problem.