Point in Polygon on the sphere

Question

I'm looking at geometric objects on the sphere and need to determine if a point on the sphere is inside a spherical polygon.

In our case a spherical polygon is a an ordered set of vertices $v_1v_2...v_n$ and the edges $v_iv_{i+1}$ are given by great circle arcs. The polygon is uniquely defined by a counterclockwise walk through the ordered set (hence we do not have the problem which of the two possible polygons is the one we are talking about).

I had a look at similar questions/problems:

1. The Paper: Locating a Point on a Spherical Surface Relative to a Spherical Polygon of Arbitrary Shape. Essentially they implement the classic rayshooting algorithm, but because of the spherical nature they need an anchor point $S$ which is guranteed to lie in the polygon. (In my application this would not be possible)

2. The question: Is a point inside or outside a polygon which is on the surface of a globe. The accepted answer suggests, that we can use the standard ray tracing algorithm with a great circle, but I do not see how that would work. In the Image the dotted line is the part that wraps around the sphere. If we now count the number of intersections it is even in both cases since we always intersect all lines on the great circle.

Any ideas how I could solve point in polygon without the anchor point would be appreciated or of cause a correction about my thoughts with respect to 2) would also be nice.

A visualization of the answer given by John L.:

Answer 1

What is the meaning of "the polygon is uniquely defined by a counterclockwise walk through the ordered set" of vertices?

To define what is a "counterclockwise" walk, what do we need to know besides the edges of the spherical polygon?

• An immersion of the (2-dimensional) sphere in some 3-dimensional space.
• A point that is inside the a spherical polygon. Or a point that is outside the spherical polygon.

If that is how "counterclockwise" is defined, then we should not have any problem applying the classic ray-shooting algorithm as described in the paper mentioned if we have been given a "counterclockwise walk" on the vertices.

---

However, it looks like that you are not given a point that is inside the given spherical polygon explicitly. Here is another possible way to define a "counterclockwise" walk.

Suppose we have a spherical polygon $P$ with vertices $v_0v_1v_2\cdots v_n$, where $n\ge3$, $v_n=v_0$ and, for each $0\le i\lt n$, $v_i$ and $v_{i+1}$ are two adjacent vertices. A "counterclockwise" walk on the edge $\{v_i,v_i+1\}$, is an ordered pair $(a,b)$, which is either $(v_i, v_{i+1})$ or $(v_{i+1}, v_i)$, such that when you, as a human, will find the inside of $P$ is to your left when you walk from $a$ to $b$ following that edge with your feet between your head and the center of the sphere (a.k.a. the center of the ball). So, "a counterclockwise walk" will specify which side of each edge faces the inside of $P$ (facing inwards). This definition of "counterclockwise" is consistent with the situation when we are looking at a mechanical clock on a sphere that faces outwards from outside of the sphere, considering the hour numbers on the clock are the vertices of $P$.)

Note that once we know which side of any given edge faces inwards, then we know which side of an adjacent edge faces inwards. So, we know which side of each edge faces inwards.

Then the question becomes how we can determine if a point on the sphere is inside $P$ if we know which side of each edge faces inwards.

Suppose the query point is $X$. We can select an arbitrary point $A$ on an arbitrary edge of $P$. Draw $\alpha$, a great circle arc between $X$ and $A$. Compute all intersection points between $\alpha$ and each edge of $P$. Find the intersection point that is nearest to $X$ and the edge (or one of the two edges) it is on, say point $I$ and edge $E$. Consider $\beta$, the great circle arc from $I$ to $X$ that is part of $\alpha$.

• If $\beta$ is on the inward side of $E$, $X$ is inside $P$.
• If $\beta$ is on the outward side of $E$, $X$ is outside $P$.
• If $\beta$ is on the same great circle as $E$,
  • If $X$ is on $E$, that says $X$ is on the perimeter of $P$.
  • Otherwise, $I$ must be a vertex of $P$. We can determine which one of the two angles between the two edges that share the vertex $I$ is the "inner angle" of $P$ and whether $\beta$ is in that "inner angle", which tells us whether $X$ is inside of $P$ or not.

Once we know one particular point is inside or outside, we can also use the ray-shooting algorithm.