geometrypolar coordinatesspherical-geometry
Given three latitude/longitude coordinates on a sphere forming a triangle, how do I test if a point p is inside that triangle?
I know latitude and longitude implies Earth and Earth is not perfectly spherical, but in my simplified model it will be. Essentially I'm interested in a point-in-triangle test for spherical geometry, using polar coordinates.
Well, I ended up solving this myself after a little more thought. The solution is to convert from the (r, phi, theta) of spherical coordinates to the (x, y, z) of Cartesian coordinates, then swap the z-axis with one of the others before finally converting back to spherical coordinates again.
Here's a simple algorithm
Define the angles $(\theta_1,\phi_2)$ and $(\theta_2,\phi_1)$
Transform these into cartesian vectors ${\bf x}_1$ and ${\bf x}_2$ using
\begin{eqnarray} x &=& \sin\theta\cos\phi \\ y &=& \sin\theta\sin\phi \\ z &=& \cos\theta\tag{1} \end{eqnarray}
$$ {\bf k} = \frac{{\bf x}_1 \times {\bf x}_2}{|{\bf x}_1 \times {\bf x}_2|} \tag{2} $$
This is a vector perpendicular to the plane spanned by ${\bf x}_1$ and ${\bf x}_2$
$$ \theta = \cos^{-1}\left(\frac{{\bf x}_1 \cdot {\bf x}_2}{|{\bf x}_1||{\bf x}_2|}\right) \tag{3} $$
$$ {\displaystyle \mathbf {x}_\psi =\mathbf {x}_1 \cos \psi +(\mathbf {k} \times \mathbf {x}_1 )\sin \psi +\mathbf {k} ~(\mathbf {k} \cdot \mathbf {x}_1 )(1-\cos \psi )} \tag{4} $$
This is an example using $(\theta_1,\phi_1) = (0.4, 1.0)$, $(\theta_2,\phi_2) = (2.0, 1.6)$ and $\Delta \theta = 0.1$
Best Answer
Note that for the point $p$ to lie within the spherical triangle bound by $\{ p_1, p_2, p_3 \}$, the intersection of the ray from the origin to $p$ (basically the line joining $(0,0,0)$ and $p$) with the 3D-plane defined by $\{ p_1, p_2, p_3 \}$ lies inside the planar triangle $\{ p_1, p_2, p_3 \}$. This can be formulated with the unknown quantities $\lambda$, $\alpha$, $\beta$ and $\gamma$, to be determined by solving the linear system of equations: $$ \alpha p_1 + \beta p_2 + \gamma p_3 = \lambda p $$
If $\lambda, \alpha, \beta, \gamma > 0$ and $\alpha + \beta + \gamma = 1$, then the projection of $p$ onto the plane $\{p_1, p_2, p_3\}$ lies in the triangle $\{p_1, p_2, p_3\}$ and therefore the point $p$ itself lies in the spherical triangle. With a little jugglery, this can be implemented in any popular linear algebra package very easily. I would start by solving the linear system: $$ \frac{\alpha}{\lambda} p_1 + \frac{\beta}{\lambda} p_2 + \frac{\gamma}{\lambda} p_3 = p $$ And then determining $\lambda$ by forcing $\alpha + \beta + \gamma = 1$.