Divide the rectangle into n equal sized rectangles

Question

I am looking for an algorithm to split a rectangle (say, 1000x800) into n (or more, but as few as possible additional rectangles) rectangles of the same size inside this rectangle, so the whole space is used. Small rectangles should also be as close as possible to the original aspect ratio.

For instance:

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

Divide by n = 2:

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

Divide for n = 3

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

Etc.

Is there such an algorithm? Ideally, I would like to have it in Python, but actually any language is beautiful, since I have to translate it ...

EDIT:

Some additional information:

The target surface will be the browser, so the surface will be approximately 4: 3 or 16: 9 or another popular dimension. The rectangle is made of pixels. Aspect ratio is not guaranteed as an integer.

Less redundant rectangles are slightly preferable in terms of aspect ratio limitation.

Answer 1

(I suppose, perhaps by mistake, that your rectangles are infinitely divisible rather than composed of discrete pixels.)

You can always get exactly the right proportions for a small fee in empty rectangles by allowing m = ceil (sqrt (n)) and using m parts on each side.

Otherwise, you are looking for p, q close to sqrt (n), such that pq> = n and p, q are close to each other. The best choice p, q, of course, will depend on how you are willing to trade from inaccuracies. It doesn't seem likely that you will ever want to take p, q very far from sqrt (n), because it will give you a big error in the form. 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*qn 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 the very wrong shapes are very bad will mean that you never have to take many iterations of the loop.

Here merit_function should embody your preferences regarding trade in waste forms.

Answer 2

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 instance:

 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 

Answer 3

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 the result depends on what you prefer for the coefficient of the rectangles or the additional number of rectangles (for example, for n = 14, shoud is 2x7 or 3x5, for n = 7, if it should be 3x3 or 2x4)

The first idea is incorrect due to some consumption:

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

This is just a general idea of ​​the algorithm, depending on your requirements you must build the correct algorithm.

The sizes for the new rectangles will be as follows:

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

Here is a similar problem, but it will not return the minimum value: Algorithm for dividing a rectangle into n smaller rectangles and calculating each center