# Getting a point in the interior of a polygon without relying on winding order?

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.

• I assume the points are known to be coplanar, so this is really a 2D problem. Do you know how to solve it if you know the orientation? Please edit the question to clarify. Commented Nov 17, 2023 at 1:32
• If the points have known orientation a very simple way to solve the problem is to grab an edge, find a vector coplanar and orthogonal to it that points towards the interior and then grab a point an epsilon along that direction. In theory it works, it has a few edge cases in practice for really degenerate polygons, but it should be fine. Commented Nov 17, 2023 at 1:40

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.