Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Split a rectangle into n equally sized rectangles

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.

like image 401
ojii Avatar asked Apr 08 '11 12:04

ojii


People also ask

How do you divide a rectangle into n equal parts?

All we have to do is put A - 1 lines along the long side of the rectangle, and B - 1 lines along the short side. For example: n = 4, A = 2 and B = 2 is optimal, so you put A - 1 = 1 and B - 1 = 1 lines along each side of the rectangle (as in your GOOD column for n = 4).

Can you divide a rectangle into 4 equal parts?

We could divide our rectangle into two equal parts, or halves. Then, we can halve each half again until we have four equal parts. If we take two-halves and halve them again, we get quarters. So, this is the rectangle that is divided into quarters.

Why can you divide a rectangle into 8 equal parts?

Because all the sides of a square are equal, you know how to divide all sides equally. Once you have four rectangles, you can simply draw one horizontal line through the center of the square, dividing it into eight equal rectangles.


2 Answers

(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.

like image 60
Gareth McCaughan Avatar answered Sep 21 '22 22:09

Gareth McCaughan


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 
like image 33
Farrukh Shahzad Avatar answered Sep 23 '22 22:09

Farrukh Shahzad