I know this sounds like bin packing but it's a bit different so please read the question to the end.
Given a rectangle of known width and height, I need to divide it into smaller rectangles using column and rows. I'm essentially creating a grid(Think of iPhone's home screen, it's a grid with square icons).
Now the problem(constrain):
- Cells' have a minimum size(say height > 10 and width > 10)
- The proportion of the cell needs to be as close to a square(1:1) as possible
- All cells' dimension need to be uniform in the grid.
I'm solving for the number of columns and rows needed to satisfy the requirements above.
Example:
A rectangle of width=3; height=3 and with a cell minimum size of width >= 1; height >= 1
Becomes:
In this example, column and row is 3 while all cells have a width and height of 1
UPDATE:
A very rough solution that works some of the time:
size = max(cellMinWidth, cellMinHeight)
columns = floor(width/size)
rows = floor(height/size)
This fails when the difference between the width and height of the rectangle is big.
Best Answer
Let us call $w$ and $h$ the width and height of the rectangle. If we start by considering perfectly square cells of size $s \times s$, the maximal area that can be covered is given by the product between the maximal number of packable cells $\displaystyle \lfloor{\frac{w}{s}}\rfloor \cdot \lfloor{ \frac{h}{s}}\rfloor$ and the area $s^2$ of each cell. It is not difficult to show that the remaining uncovered area R is given by
$$ R =h \cdot [w\pmod s]+ w \cdot [h \pmod s] - [w \pmod s] \cdot [h \pmod s] $$
For example, covering a $200 \times 50$ rectangle with area $A=10000$ using $7 \times 7$ cells, the maximal number of cells is $\displaystyle \lfloor{\frac{200}{7}}\rfloor \cdot \lfloor{ \frac{50}{7}}\rfloor=28 \cdot 7=196$, and the maximal covered area is $196 \cdot 7^2=9604$. The remaining uncovered area, which in this example is $10000-9604=396$, corresponds to
$$R= 50 \cdot [200\pmod 7]+ 200 \cdot [50 \pmod 7] - [200 \pmod 7] \cdot [50 \pmod 7]\\ =50 \cdot 4+ 200 \cdot 1- 4 \cdot 1=396$$
The formula for $R$ showed above, which for $s$ equal to max(cellMinWidth, cellMinHeight) also reflects the residual uncovered area obtained by applying the solution proposed in the OP, explains why this approach works well when $w$ and $h$ are similar, and fails when the difference between $w$ and $h$ is big. In fact, noting that both mod terms can range between $0$ and $s$, we get that the value of $R$ ranges between $0$ and $s(w+h-s)$. So, for a rectangle with given area $A=w \cdot h$ to be covered with cells of size $s \times s$, the condition that minimizes the sum $w+h$ (and that therefore minimizes the upper bound of $R$) clearly corresponds to the case $w=h$ (this is easily checked by setting $h=A/w$ and noting that $w+h=w+A/w$ has a minimum in $w=\sqrt{A}$). Accordingly, if we vary $w$ and $h$ by keeping their product constant (i.e., if we consider rectangles with constant area and variable proportions), the sum $w+h$ and the upper bound of $R$ progressively increases as the rectangle proportion departs from $1$ and as the difference between $w$ and $h$ becomes larger. This is also visible starting from the same example of a $200 \times 50$ rectangle as above: covering it with $s \times s$ cells, the value of $R$ ranges between $0$ and $s(250-s)$, but the upper bound of $R$ decreases to $s(200-s)$ if we consider a $100 \times 100$ rectangle, and raises to $s(1010-s)$ if we consider a $1000 \times 10$ rectangle (in both cases, despite no changes in the rectangle area). This explains why this method leads to a high probability of having a large uncovered area when the difference between $w$ and $h$ is large.
These considerations suggest that, when choosing the value of cell side $s$ to divide a $w \times h$ rectangle in the "best" way, a good idea could be to test all possible values of $s$, starting from the minimal values allowed, and to choose the value that minimizes $R$ according to the formula above. This analysis can be easily and rapidly obtained by a simple algorithm on a PC. Once the value of $s$ that minimizes $R$ has been found, we can also make a minimal variation in the cell size to achieve a $100\%$ covering, by adding to the cell width and height (until now considered equal in our analysis) a small quantity obtained by dividing the residual uncovered edges among all cells. The formulas for these small final adjustments are $\displaystyle \frac{w \pmod s}{\lfloor {w/s} \rfloor}$ and $\displaystyle \frac{h \pmod s}{\lfloor {h/s} \rfloor}$. For instance, if we find that in a $90 \times 34$ rectangle the best value for $s$ is $11$, we can initially cover the rectangle with a $8 \times 3$ grid of square cells of size $11$. Then, we can take the remaining edges $90 \pmod {11}=2$ and $34 \pmod {11}=1$ and distribute them among all cells, obtaining a $100\%$ covering using cells with width $11 +\frac{2}{8}=11.25$ and height $11+\frac{1}{3}\approx 11.33$. This keeps a nearly square shape for the cells and allows a complete covering.
Lastly, if we want to find a more rapid method to choose a good value of $s$ that avoids the need of testing all its possible values, it could be more convenient to privilege minimization of the mod term that, in the formula for $R$, is multiplied by the longest dimension of the rectangle. Taking again the same example of a $200 \times 50$ rectangle, to divide it in cells of size $s$ it is convenient to choose a value of $s$ that makes $50\pmod s$ as small as possible (privileging this, rather than minimization of $200\pmod s$), since then this mod term has to be multiplied by $200$. Although this method does not guarantee that the best value of $s$ is found, it might be useful to create simplified, faster algorithms to find "good" values of $s$.