2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Is the polygon convex? $\endgroup$ – TonyK Sep 15 '11 at 14:30
  • $\begingroup$ @TonyK - Possibly. It should handle both convex and concave polys. $\endgroup$ – Steve Sep 15 '11 at 15:00
2
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

The point that maximizes the distance from the polygon will be one of the vertices of the polygon's medial axis. There are algorithms for finding the medial axis, and they should also give the distance of each axis vertex from the original polygon; then you just pick the farthest one of them.

If you want to do this for a rectangle with fixed orientation, you can compute the Minkowski sum of the polygon with the rectangle (oriented so that the polygon is reduced rather than expanded) and then do the same procedure as above.

(Sorry for not providing links; I'm typing this on a mobile device. But these are all fairly standard terms you can look up on Google.)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.