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

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 2

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 3

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.