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?