An algorithm for fitting a rectangle inside a polygon
Let $P=(p_1,\dots,p_n)$ be the polygon and $\overline{P}$ the set of points it contains.

Let $R=(a,b,c,d)$ be the rectangle of width $w$ and length $l$ with $l\ge w$ (and we assume $d(a,b)=w$) and $\overline{R}$ the set of points it contains.

You want $\overline{R}\subset \overline{P}$.



Suppose $\overline{R} \subset \overline{P}$.

Let $q=a+\cfrac{1}{2}\vec{ab}$ and $r=c+\cfrac{1}{2}\vec{cd}$.

Since $q\in [ab]\subset \overline{R}$ and $r\in [cd]\subset \overline{R}$, $[qr]\subset \overline{P}$.

Since $q\not=r$, we can find $s$ and $t$ on the border of $P$ so that $(qr)=(st)$.



Now suppose you are given a convex $P$

Here's the algorithm:


$\forall i \in [1,n]$


$\forall j \in [i+1,n]$


If $\max \{d(x,y),x\in[p_ip_{i+1}],y\in[p_jp_{j+1}]\}\ge l$


$s = p_i + k_1 \vec{p_ip_{i+1}}$
$t = p_k + k_2 \vec{p_jp_{j+1}}$
$q = s + k_3 \vec{st}$
$r = q + \cfrac{l}{\|\vec{st}\|}\vec{st}$
$\vec{v}:=$ a vector so that $\vec{sr}\perp \vec{v}$ and $\|\vec{v}\|=\cfrac{w}{2}$
$a := s - v, b:= s + v, c := r+v,d:= r-v$
$S:=solve(\{"k_1\in [0,1]", "k_2 \in [0,1]", "k_3 \in [0,1]", "a,b,c,d\in P"\}$
If $S\not= \emptyset$, return true



return false


The way this algorithm works is it chooses an orientation and an ax for the rectangle by choosing two arbitrary points $s$ and $t$ somewhere on two arbitrary segments of $P$. Then it takes an arbitrary $q$ in $[st]$ and expresses $a,b,c,d$ in terms of the constants $k_i$ determining $s,t$ and $q$. Then for a point, you know how to determine if it is in a convex polygon so you just need to solve those linear inequalities (in $k_1,k_2,k_3$) for all $4$ points. And if you have solutions, $R$ fits in $P$. Otherwise, you just try another one. And if none worked, since we know that if $R$ fits in $P$, then at least one must work, we know $R$ doesn't fit in $P$.

NB: $\max \{d(x,y),x\in[p_ip_{i+1}],y\in[p_jp_{j+1}]\}=\max\{d(p_i,p_{i+1}),d(p_j,p_{j+1}),d(p_i,p_j),d(p_{i+1},p_{j+1})\}$



Then for the non-convex case, you loose the fact that: $a,b,c,d\in \overline{P}\Rightarrow \overline{R}\subset \overline{P}$. So I'm not sure how to do it.

If I had to try, I'd break $P$ into several convex polygons and try to apply a similar algorithm except that I'd try every recombination of $A,B,C,D$ with $a\in A,\dots,d\in D$ with $A,B,C,D$ different convex polygons forming $P$ and then check that the segments of $R$ don't cross segments of $P$...