1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ethan Bolker
    Commented Nov 17, 2023 at 1:32
  • $\begingroup$ 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. $\endgroup$
    – Makogan
    Commented Nov 17, 2023 at 1:40

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .