9
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What do you mean by "need to get several points"? Why not find one such point, say the center of the maximum radius circle contained in the polygon, and then put a bunch of other points very close to the first one...? $\endgroup$
    – Wlodek Kuperberg
    Commented Mar 26, 2014 at 16:58
  • $\begingroup$ If it's possible to find ONE optimal point at ONCE (e.g. the center of the maximum radius circle contained in the polygon as you said), that would be even better! The only question is how to find this maximum radius circle for an arbitrary polygon in a reasonable time. $\endgroup$
    – Omicron_Persei_11
    Commented Mar 26, 2014 at 17:13
  • 1
    $\begingroup$ I think there should be an algorithm in computational geometry for finding a locally maximal circle 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
    Commented Mar 26, 2014 at 21:01
  • $\begingroup$ @WlodekKuperberg: You are correct, there is such an algorithm. I've posted a quick description of it. $\endgroup$
    – Joseph O'Rourke
    Commented Mar 28, 2014 at 13:54

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ I really want to say thanks, although I know that it isn't a "constructive comment". You've definitely pushed me in a good direction (and may be even the best direction). And now I'm considering skeleton algorithms as well. I have one probably stupid question: is it generally possible to calculate only some part of a medial axis/skeleton? This is because I don't need the whole object but only one "good" point inside a polygon, and partial/reduced calculations may save some time (although this solution is surprisingly fast) ... $\endgroup$
    – Omicron_Persei_11
    Commented Mar 28, 2014 at 16:51
  • $\begingroup$ @Omicron_Persei_11: That's an interesting question. Offhand I do not know. I suspect the answer is Yes, asymptotically, for convex polygons, but No for arbitrary polygonal domains (polygons with holes in your notation). You might look at the randomized algorithms explored in the paper to which I linked. $\endgroup$
    – Joseph O'Rourke
    Commented Mar 28, 2014 at 20:35
  • $\begingroup$ Ok, thanks a lot. I think I go first in the direction of randomized algorithms, and then we will see... $\endgroup$
    – Omicron_Persei_11
    Commented Mar 30, 2014 at 12:45
1
$\begingroup$

You seem willing to accept non-optimal solutions as long as they lead to optimal solutions. For convex polygons, I suggest using a midpoint method: pick pairs of vertices (ideally they are presented in clockwise order, so if $k = \lfloor n/2 \rfloor$ you could try pairs $(v_i, v_{i+k})$) and use their midpoints. The locus of many of these will have a center of mass that should be near your optimal point. You could also use an average of all vertices as a candidate.

If the polygon is not convex, you could run this with a selection of pairs and find a point that would be far from the edges but be OUTSIDE of the polygon. My recommendation would be to settle on finding a subpolygon (say a triangle sharing two edges with the original polygon) that is convex and contained within the entire polygon, and generate points for that. It wouldn't be far from all edges, but it would be far from all but two of the edges.

If the polygon has holes, all bets are off: if you use any proper subset of the vertices, you may end up with the desired points in a triangular hole. Again you can try the subpolygon idea, but unless you have an oracle that tells you when you are in the interior, you will likely need to sample a large number (if not all) of the vertices.

Gerhard "Specializes In Dirty And Quick" Paseman, 2014.03.26

Improve this answer
$\endgroup$
1
  • $\begingroup$ There are easily constructed examples where this heuristic can fail, even for convex polygons. Consider a rectangle with one side augmented with many points: most midpoints will be near if not on the augmented "side". If you have a bizarre distribution of vertex points, you will run into similar issues in trying to compute an answer using few of the vertices. Gerhard "Quick and Dirty and Error-prone" Paseman, 2014.03.26 $\endgroup$
    – Gerhard Paseman
    Commented Mar 26, 2014 at 23:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .