I'm looking to print text inside a polygon, programmatically. I'd like to find the largest rectangle to position the text inside the polygon out of a sub set of rectangles, ie those oriented with their longest axis along 45° increments, eg 0°, 45°, 90° etc.
I'm not even 100% sure if I've even asked this question correctly, but the point of it is to get a sensible default position and orientation for text within a polygon. I'm open to all sensible alternative suggestions, but I guess ideally would like an algorithm to work out this rectangle.
I'm also aware that it's possible to contrive a polygon which would make most algorithms useless which would include as part of the polygon an extremely long thin rectangular section, resulting in illegible text, if it's not possible to account for this some way, I'm fine with assuming this will not occur in my situation as there will be a manual override for position and orientation in my scenario.
EDIT:
Thinking about how complicated this is, it might be easier to remove the angular restriction, then rotate and shrink the rectangle to one of those orientations after calculating it as a simplification. Also I guess the length of the text is quite important, so the algorithm would have to be adaptable to a rectangle of a specific ratio…
Feel free to throw ideas out, I'm happy to bounce back and forth with people about the best way to do this.
EDIT2:
Suggested by a friend: Calculate the longest line inside the polygon, then use that as an axis for a rectangle. So I will enumerate all lines going through 2 vertexes till I find the longest, then rectangularise each line starting at the longest, into the largest rectangle with the correct ratios. Then the largest one of these should be quite close to what I want. Any feed back on this approach?
EDIT3:
I ended up drawing the "biggest" rectangle by subdividing my problem area up into a grid of n by n squares (where n was a relatively large, yet sensible for my problem domain, size), checking if the four corners were all inside the poly. If they were I'd increase the size of the square by n, interating this until it was outside the poly, then increase it by n length wise and repeat the width increase (keeping a record of the largest area rectangle as I went) until I'd found the biggest rectangle for that size subdivision. I'd then half n and starting from my current largest rectangle, repeat the process. Repeating everything until I reached a suitable small value of n.
Best Answer
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.