Selecting a point inside a non-convex polygon

Question

There are a lot of algorithms which will tell you whether or not a given point is found inside a polygon.

I'm looking to write an algorithm which, given a non-convex polygon, will return a point which is inside the polygon.

I don't need the point to be in any specific location inside the polygon, but I prefer to receive a point which isn't very close to an edge, but that is not a deal-breaker. It's there merely to mark that polygon's planar straight-line graph (PSLG) as an internal shape for use with Shewchuck's Triangle library for some complicated constrained Delaunay triangulations.

My initial thinking is:

1. Compute the bounding box
2. Cast a ray from one corner in the direction of the opposite corner, or from the center of a bounding box edge to the opposite edge center.
3. Then, a point exactly between the first and second intersection will be inside the polygon.

Is there a better approach?

Answer 1

The following algorithm will do nicely:

p = randpoint();
while(!IsInsidePolygon(p, poly)) {
  p = randpoint();
}

Big problem is choosing randpoint() so that the whole area of the polygon is covered, but the area cannot be too large or the while loop takes too long time.

Answer 2

Your initial approach sounds like it would do what you need, but depending on how much time you could spend on finding a "good" point (not too close to an edge), you could gather several samples in various ways:

1. Let the intersecting ray hit the other side of the bounding box and look for pairs of intersections (1 & 2, 3 & 4, etc) that are farthest apart from one another.

2. Cast 2 or 4 rays: from corner to corner, from side to opposite side.

Answer 3

If you create a bounding circle instead of a bounding box, you can then select a random point on the circle, and cast rays at every X degrees across the circle (ie, like a chord, creating a fan of rays) to find the points. Then, using whatever preferences you have for point selection, you can select the best point out of the points your 'sweeps' found.

But, I would recommend trying what you have come up with first, because that very well may be sufficient for your needs.

Answer 4

Given a polygon (P1, P2, ... Pn), construct triangles from the points adjacent to each vertex (P1 P2 P3), (P2 P3 P4), ... (Pn P1 P2), and check if the center of the triangle is inside the polygon.

Answer 5

Finding the point in a triangle which is furthest from its boundary is just finding the incentre. If you triangulate the polygon (not linear time, but not far off), you can then look for a "nice" triangle (e.g. the one with the largest shortest side) and take its incentre.