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.

$\endgroup$
  • 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 Mar 26 '14 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 Mar 26 '14 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 Mar 26 '14 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 Mar 28 '14 at 13:54
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).

$\endgroup$
  • $\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 Mar 28 '14 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 Mar 28 '14 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 Mar 30 '14 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

$\endgroup$
  • $\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 Mar 26 '14 at 23:25

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.