Thank God, there is a math section to this site, I'm going insane
I have a problem I know how to solve by trial and error but I'm trying to figure out the 'smart' way to do it so I can make it into a macro using auto-hotkey and never have to guess and check again.
I think what I need is an algorithm to do the following,
Here's the problem:
For any large rectangle, place the least amount of smaller rectangles inside the large rectangle with as equal spacing as possible, the smaller rectangles will all be $A$ units wide and $B$ units long.
Here's the parameters:
Smaller rectangles can only have a maximum area of $250$ units.
Smaller rectangle can't be more than $20$ units in any direction.
Smaller rectangle can't be less than $10$ units in any direction.
Smaller rectangles may overlap.
Here's how I manually solve it, takes a while and is messy:
I divide the big rectangle area by the smaller rectangle area. This gives me the minimum amount of rectangles possible, assuming no minimum or maximum sizing limitations. In some cases, the minimum or maximum sizing limitations of the smaller rectangles means I will have to use a few more rectangles. If I had a $5 \text{unit}\times 200.01 \text{unit}$ big rectangle, for example, I would have to use $11$ small rectangles to fill the big rectangle (the $0.01$ makes me have to add another rectangle by itself), since I can't make the small rectangles longer than $20$ units according to the parameters.
For most of these problems, the best way to figure out the best solution is to find the ratio of the sides of the big rectangle (a $200 \times 400$ rectangle would have a ratio $1:2$), and scale that down to the smaller rectangles. However, I have to be careful not to have a ratio that exceeds the size limits imposed on the smaller rectangles ($10$ minimum, $20$ maximum).
Thanks for any help. It seems a lot simpler to me than how it looks on paper, but I still can't wrap my head around how to put it into an algorithm or solve it neatly in the quirky situations where you're not using nice clean numbers.
Best Answer
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:
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 functionceil()
rounds it up to the next integer: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.