I want to divide a rectangle into grid rows and columns.

I need the grid to have fewer rather than more rows and columns.

Here's an illustration

enter image description here

Requirements for each cell (eg the blue cell above):

  • The height of each cell in the grid should be equally sized.

  • The width of each cell in the grid should be equally sized.

  • The ratio of each cell width & height should be 1.25 or less.

    Max(width,height) / Min(width,height) <= 1.25

Is there an algorithm to calculate the number of rows and columns needed to produce the fewest number of "square-ish" sub-rectangles?


You need $n,m$ with $\frac 45\le \frac{w/n}{h/m}\le\frac 54$ and $nm$ minimal (here $w,h$ are the dimensions of the given large rectangle adn $n,m$ the number of columns and rows we should produce). The bounds can also be rewritten as $$\alpha\le \frac nm\le \beta $$ with $\alpha=\frac{4w}{54}$ and $\beta=\frac{5w}{4h}$. This is generally solved by the "simplest" fraction in the range $[\alpha,\beta]$, for which several methods exist. An easily rememberable one is this:

  1. Start with $n'=0,m'=1$, $n''=1,m''=0$
  2. Let $n=n'+n''$, $m=m'+m''$
  3. If $\frac nm<\alpha$, let $n'=n,m'=m$ and go back to step 2
  4. If $\frac nm>\beta$, let $n''=n,m''=m$ and go back to step 2
  5. At this point $\alpha\le \frac{n}{m}\le\beta$; we are done and have found $n$ and $m$ as desired.

Why is the found $n,m$ optimal? One can show that any fraction $\frac xy$ between $\frac {n'}{m'}$ has $x\ge n'+n$, $y\ge m'+m$, hence $xy\ge (n'+n)(m'+m)>nm$. Similar for $\frac xy$ between $\frac nm$ and $\frac {n''}{m''}$.

  • $\begingroup$ I see, its kind of a recursive bounds check between 1/1.25 and 1.25. Thanks! $\endgroup$ – JustAsking Jun 9 '15 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.