I am given an arbitrary set of points embedded in 3D.
The points are guaranteed to be ordered such that their order yields a simple closed polygon, but there is no information about whether they wind CW or CCW.
The task is to find a single point anywhere on the interior of this polygon.
If the polygon is convex, the solution is simple, the centroid. But there is no such guarantee.
I am struggling to think of an elegant way to do this better than grabbing a point and testing all possible lines connecting it to the other points for crossings.
Let $L$ be a ray from any vertex that does not meet another vertex. Calculate the number $p$ of intersections of $L$ and the other edges of the polygon. If $p$ is odd then any point near the starting vertex is in the interior. If $p$ is even, pick a point near the starting vertex on the opposite ray.
I don't know whether this is elegant enough as an answer. It's an $O(n)$ algorithm when the polygon has $n$ vertices. So is finding the centroid in the convex case.