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.

locally maximalcircle inside a given polygon. One idea is to start at a randomly chosen vertex, and "inflate" a small circle around it, keeping the circle inside, and tangent to the boundary of, the polygon until it cannot grow any longer. The details may require a lot of computations - to get it AT ONCE may be too much to ask. $\endgroup$ – Wlodek Kuperberg Mar 26 '14 at 21:01