[Math] get a point in polygon (maximize the distance from borders)

algorithmsdiscrete geometrymg.metric-geometry

I have several 2D polygons represented by lists of xy-coordinates of their vertices.
It is needed to get several points inside the polygon so that they lie possibly far from the polygon's borders (then one point that is the farthest one from the borders can be chosen..).

The polygons may contain holes, but there are no edges intersections. The number of vertices can be also quite large (up to 500 vertices or so).

If the condition that the polygons may have holes is restrictive, you may neglect it. However, if the holes are present, they are "known" (e.g. the order of points in the outer boundary is clockwise, and the order of points in holes is then counterclockwise).

I saw Get a point inside a polygon and Finding a point farthest away from k points in a polygon, but these links are still not really suitable for the problem described above.

I'm glad to receive any suggestions about possibly simple solution approaches for my question. The maximization of the distance from the borders is the highest goal, but actually it suffices to ensure that the picked points are inside the polygon and not closer to the borders than some predetermined distance.

Best Answer

Perhaps it will help to investigate the medial axis of a polygon. It was discussed in this earlier MO question, Retraction of a Riemannian manifold with boundary to its cut locus. The junctions of the medial axis are points that are far from the boundary, centers of disks touching the boundary at three or more points—local maxima, to quote from Wlodek's comment. The medial axis can be computed for polygons with holes as well:

  enter image description here
         (Image from this Matlab link)
It would be "straightforward" (with the right software) to compute for several thousand vertices. All computations also compute the disks radii, so with the medial axis in hand, one can select the disk of maximal radius.

You may also find papers that focus directly on the largest incircle of a polygon, e.g., "An Efficient Algorithm to Calculate the Center of the Biggest Inscribed Circle in an Irregular Polygon" (arXiv link).

Related Question