For a computational geometry application, I need to determine the two closest vertices that a point lies between on a circle that has been sliced into angular intervals.
To illustrate the problem, consider the crudely drawn diagram below. The circle that bounds the polygon is intersected at points by the line segments (green) that extrude from the polygon's vertices (red), yielding a set of angles.
Now suppose that a point(x,y) is placed at random on the circle (as in the diagram above with the orange dot) so that it lies between two red vertices. What is the fastest method for finding which two red vertices p lies between?
I know that a binary search over the array of vertices on the circle will work but am curious as to whether there is an analytical solution.
The motivation for solving this problem is to relate a given point to the convex polygon: to determine whether the point intersects or is interior to any of the triangles of the polygon.