algorithmsgeometrypolygonstrigonometry
I'm having trouble working out an algorithm required for polygon offsetting.
I think it's best explained by the illustration…
I have worked out a solution for when $ML=\delta$ (see below) but I'd like a more general solution to this problem.
Edit: Updated the solution with thanks for the help below.
You need to define "furthest from the edges". In following, it is taken to mean: Point $C$ within polygon $P$ is "furthest from edges" if for any other point $D$ within $P$, the minimum distance from $D$ to any point on $P$ is not less than the like amount for point $C$.
Answers to this maximum-circle-in-polygon question (which was recently duplicated) give two methods for finding "furthest point" in a polygon.
Note that it's easy to find examples (non-convex, but connected and non-intersecting) where the first method (per paper of Garcia-Castellanos) in that reference does not come close to finding a neighborhood of the correct answer, because of no initial point falling into the region of the polygon containing the "furthest point". The Voronoi method does not have that problem.
Regarding the rectangle-fitting part of your question, if we presume orientation and aspect ratio of the rectangle are fixed and given, it is easy to find examples where placing the rectangle center at the "furthest point" give an infeasible solution while other points are feasible. This might be a problem harder to solve. Update 1 The Minkowski sum method previously mentioned by Rahul properly addresses this issue, although computing the boundary of the sum polygon can be tricky. (As noted in cgal manual with code examples, it is straightforward for convex shapes, more involved for non-convex.)
As has been mentioned over at SO, this problem is very difficult from a computational perspective. It may help to see what methods have been implemented for the packing problem. There are some algorithms out there, but you may have to fine-tune one to fit your needs.
Even a naive, greedy approach may end up being pretty inefficient. Would you take into account things like rotating the shape? There are all kinds of trade-offs to be made, but your "slices" (first fit) approach may work if you need something quick and dirty.
Best Answer
Let $m$ be the midpoint of $eb$, then extend $Ym$ and $cb$ to meet at $o$. We obtain two similar right triangles sharing an angle of $\beta/2$ at $o$. Then $$om=\frac\delta{\sin\beta/2}-ML$$ $$ob=\frac{om}{\cos\beta/2}=\frac\delta{\sin\beta/2\cos\beta/2}-\frac{ML}{\cos\beta/2}$$ $$cb=oc-ob=\frac\delta{\tan\beta/2}-\frac\delta{\sin\beta/2\cos\beta/2}+\frac{ML}{\cos\beta/2}$$ $$=\frac{\delta\cos\beta/2}{\sin\beta/2}-\frac\delta{\sin\beta/2\cos\beta/2}+\frac{ML}{\cos\beta/2}$$ $$=\frac{\delta(\cos^2\beta/2-1)+ML\sin\beta/2}{\sin\beta/2\cos\beta/2}$$ $$=\frac{ML\sin\beta/2-\delta\sin^2\beta/2}{\sin\beta/2\cos\beta/2}$$ $$=\frac{ML-\delta\sin\beta/2}{\cos\beta/2}.$$