Split a rectangle into n equally sized rectangles

7
votes

I'm looking for an algorithm to split a rectangle (let's say 1000x800) into n (or more, but as few extra rectangles as possible) equally sized rectangles within that rectangle, so all the space is used. The small rectangles should also try to be as close to the original aspect ratio as possible.

Eg:

+---------------+
|               |
|               |
|               |
+---------------+

Split for n = 2:

+---------------+
|               |
+---------------+
|               |
+---------------+

Split for n = 3

+-------+-------+
|       |       |
+-------+-------+
|       |       |
+---------------+

Etc.

Is there such an algorithm? Ideally I'd like to have it in Python, but really any language is fine since I should be able to translate it...

EDIT:

A few extra infos:

The target surface will be a browser window, so the surface will be roughly 4:3 or 16:9 or another popular dimension. The rectangle is made of pixels. The aspect ratio is not guaranteed to be an integer.

Less excess rectangles is slightly preferable over the aspect ratio constraint.

3
pythonalgorithmgeometry
you should pick min(a, b), max(a, b)/2 pair for the next rectangle with the closest accept ratio. BTW, is the dimension integer? – khachik
You have two constraints "as few extra rectangles as possible" and "as close to the original aspect ratio as possible" — which of these is more important? (From your example for n=3, which uses 4 rectangles, probably the second.) And how do you measure "closeness" to the original aspect ratio? – ShreevatsaR
Descriptions like "roughly" and "slightly preferable" are not very useful unless you can make them precise. :-) (E.g. for n=3, you can split horizontally or vertically into exactly 3 rectangles; why is this not preferred, exactly speaking?) – ShreevatsaR
Well the roughly is because I don't know what resolution people will use this software on. The slightly is just because less excess rectangles should not always trump the aspect ratio. – ojii
@ojii: So when should it trump? (Anyway, Gareth's answer below which tries to accommodate an arbitrary merit function is probably the best that can be done short of mind-reading.) – ShreevatsaR

3 Answers

2
votes

(I'm assuming, perhaps wrongly, that your rectangles are infinitely divisible rather than being made up of discrete pixels.)

You can always get exactly the correct aspect ratios, at some cost in wasted rectangles, by letting m = ceil(sqrt(n)) and using m pieces on each side.

Otherwise, you're looking for p,q close to sqrt(n) such that pq >= n and p,q are close to one another. The best choice of p,q will of course depend on how willing you are to trade off waste against inaccuracy. It doesn't seem likely that you'll ever want to take p,q very far from sqrt(n), because doing so would give you a large error in shape. So I think you want something like this:

p = ceiling(sqrt(n))
best_merit_yet = merit_function(p,p,0)
best_configuration_yet = (p,p)
for p from floor(sqrt(n)) downward:
  # we need pq >= n and q as near to p as possible, which means (since p is too small) as small as possible
  q = ceiling(n/p)
  if max(merit_function(n/p,n/q,0), merit_function(n/q,n/p,0)) < best_merit_yet:
    break
  n_wasted = p*q-n
  merit1 = merit_function(n/p,n/q,n_wasted)
  merit2 = merit_function(n/q,n/p,n_wasted)
  if max(merit1,merit2) > best_merit_yet:
    if merit1 > merit2:
      best_configuration_yet = (p,q)
      best_merit_yet = merit1
    else:
      best_configuration_yet = (q,p)
      best_merit_yet = merit2

and hopefully the fact that very wrong shapes are very bad will mean that you never actually have to take many iterations of the loop.

Here, merit_function is supposed to embody your preferences for trading off shape against waste.

1
votes

Use this function to get 2 numbers as a list:

def divide_equally(n):
    if (n<3):
        return [n, 1]
    result = list()
    for i in range(1, int(n ** 0.5) + 1):
       div, mod = divmod(n, i)
       #ignore 1 and n itself as factors
       if mod == 0 and i != 1 and div != n:
           result.append(div)
           result.append(i)
    if len(result)==0: # if no factors then add 1
        return divide_equally(n+1)
    return result[len(result)-2:]

For example:

print divide_equally(1)
print divide_equally(50)
print divide_equally(99)
print divide_equally(23)
print divide_equally(50)

will give 

[1, 1]
[10, 5]
[11, 9]
[6, 4]  # use the next even number (24)
[10, 5] # not [25, 2] use the 2 closest numbers
0
votes

Edit: second idea:

var countHor = Math.Floor(Math.Sqrt(n));
var countVer = Math.Ceil(n / countHor);
var widthDivided = widthTotal / countVer;
var heightDivided = heightTotal / countHor;

Although result depends on what are you preferring rectangles ratio or extra rectangle count (e.g. for n = 14, shoud it be 2x7 or 3x5, for n = 7, should it be 3x3 or 2x4)

The first idea is wrong due some consumptions:

If you want to get minimum number of equal rectangles you should use sqrt operation. For example if n = 9, when it would be 3x3 rectangles (2 lines vertically and 2 lines horizontally). If n = 10 it would be 3x4 rectangles as floor(sqrt(10)) x ceil(sqrt(10)) => 3x4 (2 lines vertically and 3 lines horizontally or otherwise).

This is just general algorithm idea, depending on your requirements you should build correct algorithm.

Sizes for new rectangles would be as following:

var widthDivided = widthTotal / Math.Floor(Math.Sqrt(count));
var heightDivided = heightTotal / Math.Ceil(Math.Sqrt(count));

Here's similar task but it will not return minimum value: Algorithm to split rectangle into n smaller rectangles and calculate each center