holes: a good way to find a point inside of it?

Apr 12, 2014 at 2:15 PM
The way to define holes by having to provide a point inside of the hole seems quirky.

It's rather tricky to define such a point when the hole is concave.

What's a reliable way to find a point inside a concave hole?

Is an algorithm like this really needed?
Coordinator
Apr 13, 2014 at 10:16 AM
Edited Apr 14, 2014 at 7:00 PM
Probably not needed, but straightforward to implement:

Let's assume your polygon is made up of the points (a_0, a_1 ... a_n).
  1. Find a convex corner a_k.
  2. There exists a point inside triangle a_(k-1), a_k, a_(k+1) which lies inside the polygon.
To find that point you use the above algorithm:
  1. Let c = (a_(k-1) + a_(k+1)) / 2, the center point on the line [a_(k-1) a_(k+1)].
  2. Let d = a_k - c, the vector from c to a_k, and let x = length(c) / 2
    Repeat:
  3. Check if p = c + (1 - x) * d is inside the polygon
  4. Let x = x / 2
So this is a binary search on the line from c to a_k. If the loop is processed m times, the total complexity is O(m n) since the "is inside the polygon" check is O(n).
Coordinator
Apr 13, 2014 at 10:28 AM
Actually, it is easier to just choose any segment of the hole and do the above binary search in both directions perpendicular to the segment. Probably not as efficient, but still O(m n).
Apr 15, 2014 at 8:18 AM
Should the polygon points be stored in clockwise or anticlockwise direction? If there is not a specific rule, how can I identify a convex corner?
Coordinator
Apr 15, 2014 at 9:25 AM
Edited Apr 15, 2014 at 9:58 AM
Well, obviously the user should know how the contours are stored. I guess, that's one reason why Shewchuk chose to define holes the way he did: the user should know best how to handle them!

If you don't like the heuristic approach above, you could triangulate the hole and choose a point in any of the triangles. But this will always be O(n log n)...
Apr 15, 2014 at 10:54 AM
Edited Apr 15, 2014 at 11:00 AM
Hey all, I settled on this very compact implementation to check whether a point is inside the convex hole.

I then iterate and construct a series of candidate points: two per corner (one on either 'side' of it, on the corner's bisector), and test until positive.