algebra-precalculusgeometry
I have an area of $A = 320 \times 480$. I then have a number of rectangles of max size $128 \times 152$ which need to fit into the area. There can either be $1$ rectangle or $100$ rectangles. How would calculate the size that the rectangles need to be to fit into the given area?
Thanks in advance.
We will be referring to the primitive picture above. The original rectangle had horizontal side $a$ and vertical side $b$. It was rotated through an angle $\theta$ ($t$ in the picture).
We start with an $a \times b$ rectangle, with horizontal and vertical sides, such that the sides of length $a$ are horizontal. We rotate the rectangle counterclockwise about its center, through an angle $\theta\le \pi/2$.
How much horizontal and vertical space is occupied by the rotated rectangle? (In general, the minimal containing rectangle will not be a square.)
The diagram above can be used to see that the horizontal space occupied is
$$a\cos\theta+b\sin\theta,$$
and that the vertical space occupied is
$$a\sin\theta+b\cos\theta.$$
For suppose that the side labelled $a$ has length $a$, and the side labelled $b$ has length $b$. Then the horizontal side $PR$ of the containing rectangle is made up of two parts. By basic trigonometry, the part $QR$ has length $a\cos\theta$, and the part $PQ$ has length $b\sin\theta$. Add up. A similar argument deals with the vertical side of the containing rectangle.
If we want to fit the rotated rectangle into a square of side $s$, then the least $s$ that will work is given by $$s=\max(a\cos\theta+b\sin\theta, a\sin\theta+b\cos\theta).$$
If we have a square of fixed side $d$ (in the post, $d=100$), we may want to scale the original rectangle to make the rotated version fit. Let $\lambda$ be the (common) scaling factor of the sides of the original $a\times b$ rectangle that will make the fit in the $d\times d$ square snug horizontally and/or vertically. Then we need $$\lambda \max(a\cos\theta+b\sin\theta, a\sin\theta+b\cos\theta)=d,$$ and now we can compute $\lambda$.
Comment: The same basic formulas can be used to solve some of the more general problems that you mentioned. We obtained separate formulas for the horizontal and vertical space occupied by the rotated rectangle. Suppose that our target rectangle has given horizontal and vertical sides. We can compute the scaling factor $\lambda_h$ that will give a horizontal fit, and the scaling factor $\lambda_v$ that will give a vertical fit. Then the desired scaling factor for both a horizontal fit and a vertical fit is $\min(\lambda_h, \lambda_v)$. (Here as usual we are working on the assumption that the ratio of the sides must be maintained, so a common scaling factor must be applied to each.)
I don't think there's any "formula" for this and as far as I remember the problem is conjectured to be NP-hard, but not proven to be. For a heuristic that finds very good solutions (conjectured by the authors to be optimal), see this.
Best Answer
Given a number $n$ and a big rectangle of size $a\times b$, you want to find a rectangle size $x\times y$ such that $n$ such rectangles fit exactly into the big rectangle. A simple method to achieve this, is to find a factorization $n=m\cdot k$ of $n$ and let $x=\frac am$, $y=\frac bk$. This way it is possible to lay the small rectangles in a regular $m$ by $k$ pattern and thus fill the big rectangle.
For example, if $a=320$, $b=480$ as in your example and $n=100$, one might choose the factorization $n=10\cdot 10$ and thus arrange $10$ by $10$ rectangles of size $32\times 48$. Or we might factor $n=5\cdot20$ and arrange $5$ by $20$ rectangles of size $64\times 24$. Each factorization $100=1\cdot 100=2\cdot 50=4\cdot 25=5\cdot 20=10\cdot 10=20\cdot5=25\cdot 4=50\cdot 2=100\cdot 1$ gives rise to a different solution.
An interesting question arises: If we allow the small rectangles to be rotated by $90^\circ$ and thus use "mixed" patterns, could solutions with other sizes than those found by the method above come up? The somewhat surprising (partial) answer is: One of the fractions $\frac ax$, $\frac bx$ must be an integer, and one of the fractions $\frac ay$, $\frac by$ must be an integer (this can be shown using a clever integration trick). In special cases (e.g. if the given rectangle is a square, $a=b$), this already shows that $x\times y$ is among the solutions found with the factorization method described above.