I need a formula to divide a fixed area in 'N' number of equal parts.
For example I am having a picture/image of 800*800, So now I need to slice it into 10 number of equal parts (squares/ rectangles) and what will be the dimension (height * width) of the sliced portions.
Can you help me in that?
If in case it is an odd number then we will add +1 to it and will merge the last 2 images resulting in making a rectangle.
[Math] Dividing a picture into N number of equal parts
geometry
Related Solutions
Let's analyze a single case:
If we want to cover a $6x5$ rectangle with $7$ squares, we first note that each square at most has an area of $30/7$. We also know that for our filling to be optimal, we need to fill at least an axis.
So now we know that we will fill either the $6$ or the $5$ completely. We will first try with the 5. Since the maximal side of our squares is $\sqrt{30/7}$, we now need the smallest integer more than $5/\sqrt{30/7}$, that is equal to $\lceil5/\sqrt{30/7}\rceil=3$
So we would divide the $5$ in $3$ parts $p_x$, so each side will have $5/3$ . If so, I would cover $(5/3)^2*7=19\frac49$ of the thirty squares. If they don't fit vertically, we try with more parts $p_x$, until the squares fit in the other axis. $$\lfloor6/(5/p_x)\rfloor*\lfloor5/(5/p_x)\rfloor=\lfloor6/(5/p_x)\rfloor*p_x\ge7 \,\,\,\,\,\,\,\,\,\, (5/p_x=\text{the actual size of our squares)}$$ Also, since $p_x$ is integer $\lfloor p_x \rfloor =p_x$
If we do the same with the $6$, we get $\lceil6/\sqrt{30/7}\rceil$ again covering $19\frac49$ of the surface. We then do the same as with the $5$ and save it as $p_y$
Let's now recall the formulas we had.
We had an $x∗y$ rectangle and filled it with $N$ squares. We started with $p_x=⌈x/\sqrt{xy/N}⌉$=$⌈\sqrt{Nx/y}⌉$ or $p_y=⌈y/\sqrt{xy/N}⌉=⌈\sqrt{Ny/x}⌉$ and then we made them fit by shrinking them until they fit in the other axis. But we know we want the area maximised, so $Side=max(x/p_x,y/p_y)$.
A better method:
Once we have the start value $p_x=⌈x/\sqrt{xy/N}⌉=⌈\sqrt{Nx/y}⌉$,if it does not fit in the $y$ axis, we need to make it fit in the $y$ axis. For that, we use that $$a=x/p_x$$ where $a$ is the value of the actual side of our squares. Then we know that for our side to fit we need to reduce it: $$S_x=y/(\lceil y/a \rceil)$$ We do the same with $S_y$ and calculate $max(S_x,S_y)$ The advantage of this is that it needs a constant number of operations, the most expensive one being the square root.
Plain, unoptimized C Code
Some multiplications may be reused but for code readability and practical uses this is enough. Input: values of $x$,$y$, and $n$. Handcoded.
Output: The optimal side of our squares
#include <math.h>
#include <stdio.h>
#define MAX(x,y) (x)>(y)?(x):(y)
int main(){
double x=5, y=6, n=7;//values here
double px=ceil(sqrt(n*x/y));
double sx,sy;
if(floor(px*y/x)*px<n) //does not fit, y/(x/px)=px*y/x
sx=y/ceil(px*y/x);
else
sx= x/px;
double py=ceil(sqrt(n*y/x));
if(floor(py*x/y)*py<n) //does not fit
sy=x/ceil(x*py/y);
else
sy=y/py;
printf("%f",MAX(sx,sy));
return 0;
}
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$.
Best Answer
Let's assume that $N$ divides $800 \times 800 = 64000$ for now. Then in order to split up the $800 \times 800$ image we factorise $N$ into integers $(a, b)$ such that $a|800$ and $b|800$.
For example, if $N = 10$ then you have $(1, 10)$, $(2, 5)$, $(5, 2)$ and $(10, 1)$ as valid factorisations. Then each rectangular slice would have dimensions $\frac{800}{a} \times \frac{800}{b}$. So for $N = 10$ the solutions are:
$\frac{800}{1} \times \frac{800}{10} = 800 \times 80$
$\frac{800}{2} \times \frac{800}{5} = 400 \times 160$
$\frac{800}{5} \times \frac{800}{2} = 160 \times 400$
$\frac{800}{10} \times \frac{800}{1} = 80 \times 800$
Note that for some $N$, there may be. For example, $(1600, 1)$ is not a valid factorisation for $N = 1600$ because 1600 exceeds the side lengths of the initial $800 \times 800$ image.
If $N$ does not divide 64000 then you cannot divide the image into equal rectangles.