Note: I have an "okay" solution to this problem (see below), but I'm wondering if there's a better algorithm, since mine is fairly conservative.
The problem:
We have a rectangle with a some width, height ($W$,$H$), and thus a given aspect ratio $A=\frac WH$.
We want to evenly subdivide this rectangle into $M \times N$ pieces. We want the aspect ratio of each resulting cell to be near some target aspect ratio, $T$. Furthermore, we want the final number of cells to be at most $C$.
For instance, if we have a $300 \times 200$ rectangle, with $T = 1$ and $C = 10$, then the best answer is $M=3, N=2$. If instead we chose $C=3$, it would be $M=2, N=1$.
Graphhically:
My current solution:
This solution works, but is conservative:
The cells' aspect ratio will be $\frac{\frac WM}{\frac HN} = \frac WH \cdot \frac NM = A \cdot \frac NM$
So, we want $T \approx A \cdot \frac NM \implies \frac NM \approx \frac TA$.
Thus, we want a rational number approximation of $\frac TA$, where $M \cdot N <= C$.
I learned about the limit_denominator algorithm (Python source code), which essentially does that, using convergents of the continued fraction, but instead of limiting $M\cdot N$, it limits the denominator to some maximum, $D$.
This is where the "conservative" aspect comes in: I use that algorithm, and choose $D = \lfloor \sqrt{C} \rfloor$. This covers the worst case, where the rational approximation is $\frac{D-1}{D}$ (which would make $M\cdot N$ large). Towards that end, I also flip the input fraction if needed, so the numerator is never bigger than the denominator, which means limiting the denominator also limits the numerator.
Going back to the $300 \times 200$ example, if I use $C=6$, I get $D=\lfloor \sqrt 6 \rfloor = \lfloor 2.449... \rfloor = 2$. This does not allow the $3 \times 2$ split, only $2 \times 1$, which is inferior, even though $3 \times 2 <= C$ holds. I need to increase to $C = 9$ so we get $D = 3$ in order to get the better answer.
Of course, if I wanted to, I could use binary search to find the best $D$ in the range $[\lfloor \sqrt C \rfloor, C]$.
The question:
Is there a better way?
I feel somehow vaguely as though there might be a way to integrate the "limit to $M\cdot N$" requirement into the limit_denominator algorithm, but it does not seem straightforward.
Maybe there is a better algorithm, entirely?