0

My Situation

  • I have a N rectangles
  • The rectangles all have the same shape (for example 2 inches wide x 1 inch tall) - Let's refer to this size as Sw and Sh for the width and height
  • I want to position these rectangles in a grid such that the rects completely on top and next to each other - like what you would see in a spreadsheet
  • What I need is this: Given N, Sw, and Sh what are the number of rows (R) and columns (C) that would stack these rects into the most square-like arrangement possible
  • It is understood that R & C may provide more cells than in needed (for example if N=15,Sw=1,Sh=1 then R=4,C=4 yielding 16 "slots" for 15 rectangles - that is OK.
  • If Sw=Sh then my humble math skills are enough - when they rectangles have differing widths and heights - well frankly that's beyond me.

Some Notes

  • Yes I have read this question: Stacking rectangles to take as little space as possible and no it did not help. Also it isnt the same question. That question is about rectangles that could be of different sizes, in this question the rectangles have the same size
  • Yes I have searched on wolfram.com, etc and no luck there
  • I don't have a strong math background so I the way I phrasing this problem may itself be preventing me from finding the answer - I've tried related searches relating to tiling, dissecting, decomposing, and not had any success there either

Some examples

the * indicates the edges of the rects
the | indicates that a cell is "filled-in"
Notice that not all R*C cells are filled in, but only and exactly N cells

IF N=1, Sw=2, Sh=1 THEN R=1, C=1

********
*||||||*
********

IF N=2, Sw=2, Sh=1 THEN R=2, C=1

********
*||||||*
********
*||||||*
********

IF N=3, Sw=2, Sh=1 THEN R=2, C=2


***************
*||||||*      *
***************
*||||||*||||||*
***************

IF N=4, Sw=2, Sh=1 THEN R=2, C=2


***************
*||||||*||||||*
***************
*||||||*||||||*
***************

IF N=5, Sw=2, Sh=1 THEN R=3, C=2


***************
*||||||*      *
***************
*||||||*||||||*
***************
*||||||*||||||*
***************

Implementation of AaronofTomorrow's answer

# Implementation of AaronofTomorrow's answer
# implemented in python 2.6
# reasonable output
# works in constant time

import math

def f( N, Sw, Sh ) :
    cols = math.sqrt( float(N) * float(Sh) / float(Sw) )
    cols = round(cols)
    rows = float(N) / float(cols)
    rows = math.ceil(rows)
    return (int(cols),int(rows))

Another implementation inspired by Will's answer (Updated on 2008-12-08) - this is the one I finally used

# Another implementation inspired by Will's answer
# implemented in python 2.6
# reasonable output - a bit better in yielding more squarelike grids
# works in time proportional to number of rects
#
# strategy used it to try incrementaly adding a rect.
# if the resulting rect requires more space then two
# possibilities are checked - adding a new row or adding a new col
# the one with the best aspect ratio (1:1) will be chosen 


def g( N, Sw, Sh ) :
    slope = float(Sh)/float(Sw)
    cols = 1
    rows = 1
    for i in xrange( N ) :
        num_to_fit =i+1
        allocated_cells= cols* rows
        if ( num_to_fit <= allocated_cells ) :
            pass # do nothing
        else :
            hc,wc = float(Sh * rows), float(Sw * (cols+1))
            hr,wr = float(Sh * (rows+1)), float(Sw * cols)
            thetac = math.atan( hc/wc)
            thetar = math.atan( hr/wr)
            alpha = math.pi/4.0
            difr = abs(alpha-thetar)
            difc = abs(alpha-thetac)
            if ( difr < difc ) :
                rows = rows +1
            else:
                cols = cols + 1

    return (cols,rows)
Cœur
  • 37,241
  • 25
  • 195
  • 267
namenlos
  • 5,111
  • 10
  • 38
  • 38

4 Answers4

2

Building on Will Dean's response, find the derivative of his formula (with respect to nCols):

-N*Sh / nCols + Sw

Then set it to 0 and solve for nCols, which gives:

nCols = sqrt(N * Sh / Sw)

Round that and you should have the optimum number of columns:

cols = round(sqrt(N * Sh / Sw))
rows = ceil(N / cols)

AaronOfTomorrow
  • 121
  • 2
1

I think you'll found 'most square-like' is a step on the way to 'most circle-like', which is the point at which the circumference (perimeter length) will be at its minimum.

Your circumference is 2*nRows*Sh + 2*nColsSw. You know that nRowsnCols >= N, and I think simplifying that to nRows*nCols = N would be OK in the following bit.

Without trying it, I think you could then usefully try and find a (the) minimum of the function:

N/nCols*Sh + nCols*Sw

Dunno if any of this would work, but it's usefully allowed me to delay the start of my working day by 5 minutes, so it's not a dead-loss.

Will Dean
  • 39,055
  • 11
  • 90
  • 118
  • Since nCols and nRows are integers and not continuous variables, you can't optimize by taking derivatives. – David Norman Dec 04 '08 at 17:19
  • I wasn't really thinking that 'find a minimum' and 'differentiate' were synonyms - you might perhaps use some iterative approach. – Will Dean Dec 05 '08 at 22:03
0

If the number of rectangles was unlimited, you would need to find the LCD (Least Common Denominator) of Sw and Sh. Then you could divide it by Sw and Sh to find the horizontal and vertical count.

Since it is limited, it's different. Do I understand correctly that you have to use up ALL the rectangles and the result has to be a rectangle as well? I'll assume so.

In such a case you don't really have that many choices on how to arrange the rectangles. There are only that many integer-pairs that give N when multiplied together.

In your case I'd try to find all possible such pairs of integers (use a simple FOR loop) and see which one is closest to a square. In the FOR loop notice, that you have to check only up to sqrt(N), because every integer-pair that you find after that will be the same as one you have already found, just in reverse.

Vilx-
  • 104,512
  • 87
  • 279
  • 422
  • Vilx - use up all the rectangles - yes – namenlos Dec 04 '08 at 09:11
  • Vilx - the result has to be a rectangle - YES in the sense that I am going draw grid based with R rows and C columns - but it is fine if R & C give me more cells than I need. In that case that I woudl be drawing a non-rectangular area on the screen (could be an "L" shape for example) – namenlos Dec 04 '08 at 09:13
0

First, special-case truely-square rectangles or rectangles where a dimension is zero.

Otherwise, for simplicity of explanation, build it iteratively:

    add a new row until height is greater than width
    add a new column until width is greater than height

which might in code look like this:

    // place the first tile as an initialisation
    int tiles = num_tiles - 1;
    int rows = 1;
    int columns = 1;
    int width = sx;
    int height = sy;

    int i=1; // just because we're curious how many iterations we have

    // build the near-square
    while(tiles > 0) {
        while((tiles > 0)
        && ((width + sx) <= (height + sy))) {
            // add a column
            tiles -= rows;
            columns++;
            width += sx;
        i++;
        }
        while((tiles > 0)
        && ((height + sy) < (width + sx))) {
            // add a row
            tiles -= columns;
            rows++;
            height += sy;
        i++;
        }
    }

    // done
    printf("%d = %d (%dx%d) = %dx%d (%dx%d) in %d\n",
    num_tiles,tiles,sx,sy,rows,columns,width,height,i);

and some results:

100 = -5 (10x20) = 7x15 (150x140) in 21
1000 = -12 (10x20) = 22x46 (460x440) in 67
10000000 = -1628 (10x20) = 2236x4473 (44730x44720) in 6708
200 = 0 (7x13) = 10x20 (140x130) in 29
2000 = -13 (7x13) = 33x61 (427x429) in 93
20000000 = -3790 (7x13) = 3282x6095 (42665x42666) in 9376
400 = -14 (17x13) = 23x18 (306x299) in 40
4000 = -15 (17x13) = 73x55 (935x949) in 127
40000000 = -192 (17x13) = 7232x5531 (94027x94016) in 12762

worst case O(n), for very very thin rectangles, or a small number of rectangles. But O(sqrt(n)) in general cases?

Will
  • 73,905
  • 40
  • 169
  • 246