Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Is the polygon convex? –  TonyK Sep 15 '11 at 14:30
    
@TonyK - Possibly. It should handle both convex and concave polys. –  Steve Sep 15 '11 at 15:00

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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

share|improve this answer
2  
Here is a medial axis algorithms link. Warning: The algorithms are easy for convex polygons, difficult for nonconvex. –  Joseph O'Rourke Sep 16 '11 at 0:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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