I'd like to determine which point(s) within an irregular polygon are furthest from the edges.
Is there an existing algorithm to determine this?
Also, if it's already out there, I'd like to do a similar thing, but for a rectangle of known size (fit the rectangle within the polygon maximizing it's distance from the edges).
Thanks
Best Answer
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.)