Point In Simple Polygon

From CGAFaq

Given a Simple_Polygon, find some point inside it. Here is a method based on the proof that there exists an internal diagonal, in [O'Rourke (C), 13-14]. The idea is that the midpoint of a diagonal is interior to the polygon.

1. Identify a convex vertex v; let its adjacent vertices be a and b.
2. For each other vertex q do:
   • If q is inside avb, compute distance to v (orthogonal to ab).
   • Save point q if distance is a new min.
3. If no point is inside, return midpoint of ab, or centroid of avb.
4. Else if some point inside, qv is internal: return its midpoint.

Code for finding a diagonal is in [O'Rourke (C), 35-39], and is part of many other software packages. See also Graphics_Source_Code.