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:
- Compute the bounding box
- 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.
- Then, a point exactly between the first and second intersection will
be inside the polygon.
Is there a better approach?
9
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.
4
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:
-
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.
-
Cast 2 or 4 rays: from corner to corner, from side to opposite side.
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.
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.
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.
2