This is probably overkill, but if the polygon is convex and you fix the axis along which the rectangle is to be aligned, the problem is a second order cone program. If $x$ is a 2-d vector, any convex polygon can be expressed as the set of points satisfying $Ax \le b$, where A is a matrix and b is a vector. (Why? each bounding line is an inequality $a_i^T x \le b_i$, so then let $a_i^T$ be the ith row of $A$, and $b_i$ the ith component of b.)
So if $x$ is a corner of your rectangle, and $\ell,w$ are the length and width of your rectangle, the problem is:
$$
\begin{eqnarray}
\max_{x,\ell, w} \ \ell w \\
Ax \le b, \quad
A\left(x + \left[\begin{matrix} 0 \\ w\end{matrix}\right] \right) \le b,
\quad
A\left(x + \left[\begin{matrix} \ell \\ 0\end{matrix}\right] \right)& \le b,
\quad
A\left(x + \left[\begin{matrix} \ell \\ w\end{matrix}\right] \right)& \le b,
\quad \ell,w \ge 0
\end{eqnarray}
$$
Then there's a standard trick to turn a hyperbolic constraint into an SOCP:
$$\left \|
\left[\begin{matrix} 2z \\ \ell - w\end{matrix}\right] \right\|_2 \le \ell + w \Leftrightarrow z^2 \le \ell w
$$
So instead of maximizing $\ell w$ you can include the above constraint, and maximize $z$. If you don't have access to an SOCP solver is probably more complicated than what you need, but it does show how one can solve the problem exactly.
Here's a method that should give an optimal answer, assuming that all the small rectangles have the same shape and orientation. (I haven't ruled out the possibility that there could be arrangements of different-shaped rectangles that might be more efficient in some cases.)
First, assume that the smaller rectangles are all $x$ by $y$ units, where $12.5 \le x \le 20$ and $y = 250/x$. (There's no need to consider rectangles with $x \le 12.5$, since they can always be replaced by $12.5 \times 20$ rectangles with suitable overlap.) Then the number of such small rectangles required to cover the big $A$ by $B$ rectangle is $$f(x) = \lceil A/x \rceil \cdot \lceil B/y \rceil$$ where $\lceil a \rceil = \operatorname{ceil}(a)$ denotes the smallest integer greater than or equal to $a$.
We'll note that, as $x$ increases, $f(x)$ can only decrease at the points where $A/x$ is an integer. Thus, the minimum of $f(x)$ must be attained either at $x = 12.5$ or at $x = A/k$ for some integer $k$. To find the actual minimum, we can use the following procedure:
- Let $x_0 = 12.5$ and let $n = \lceil A/x_0 \rceil$. Let $m = n - \lfloor A/20 \rfloor$.
- Let $x_i = A/(n - i)$ for all $i$ from $1$ to $m$.
- Find among the values $x_0$ to $x_m$ the one that gives the smallest $f(x)$.
Note that, in most cases, this procedure will yield a value of $x$ which exactly divides $A$, whereas in the other direction the small squares will cover up to $y \cdot \lceil B/y \rceil = 250/x \cdot \lceil xB/250 \rceil$ units. To get rid of the extra area, you can either reduce $y$ to $B / \lceil xB/250 \rceil$ (assuming that this does not reduce $y$ below the lower limit of $10$) or arrange for the rectangles to overlap.
Ps. If you want to make the small rectangles overlap approximately equally in both directions, you could replace the dimensions $x$ and $y = 250/x$ chosen by the above procedure with $y' = \frac12 y + \frac12 B / \lceil B/y \rceil$ (clipped to the range $12.5 \le y' \le 20$) and $x' = 250/y'$.
Here's the same algorithm in pseudocode. Assume that all variables and constants are floating point numbers; the function floor() rounds a number down and the function ceil() rounds it up to the next integer:
// Tile size constraints. We only consider tiles with maximum area,
// since smaller tiles can be replaced by overlapping larger tiles:
const maxArea = 250;
const maxWidth = 20;
const minWidth = maxArea / maxWidth;
function coverRectangleWithTiles ( rectWidth, rectHeight ):
// How many columns of tiles do we need at least?
var minColumns = ceil( rectWidth / maxWidth );
// ...and how many at most?
var maxColumns = floor( rectWidth / minWidth );
// First see what how well we can do with minimum-width tiles:
var columns = maxColumns;
var rows = ceil( rectHeight / maxWidth );
// Lowest total found so far; we'll try to improve this below:
var minTiles = columns * rows;
// Now try it with wider tiles; we only need to try the minimum
// tile width for each possible number of columns. The case
// columns = maxColumns is already tried above, so we can exclude
// it (and should, because otherwise the formulas below might
// give tileWidth < minWidth, and thus tileHeight > maxWidth):
for columns from minColumns to maxColumns-1 do:
// Find the minimum tile width for this number of columns:
var tileWidth = rectWidth / columns;
// ...the maximum height allowed for this width:
var tileHeight = maxArea / tileWidth;
// ...and the number of rows needed with this height:
var rows = ceil( rectHeight / tileHeight );
// Multiply columns with rows to get total number of tiles:
var tiles = columns * rows;
// ...and save it if it's smaller than the minimum so far:
if tiles < minTiles then:
minTiles = tiles;
// Could also save the tile dimensions needed to obtain
// the minimum here.
end if
end for
return minTiles;
end function
Note that the algorithm above actually calculates the minimum number of non-overlapping tiles needed to cover a rectangle at least as large as the given one. That is to say, if the resulting number of tiles were arranged without overlap, they might (and usually would) extend outside the rectangle.
Normally, this shouldn't be a problem, since the tile dimensions can simply be reduced to make them fit exactly, and/or the tile positions can be adjusted to make them overlap instead of spilling outside the rectangle. However, when adjusting tile sizes, you'll have to keep in mind the hard lower width/height limit of 10 units, which the algorithm above ignores.
Best Answer
From this article :