How to determine a point in a triangle in a high dimension?

Question

I have 3 points: $(x1, x2, x3) \in R^d$

Given a query point $q \in R^d$, how can I efficiently determine whether $q$ resides inside the triangle that is defined by $(x1, x2, x3)$ ?

Thanks!

Answer 1

You want to solve $ax_1+bx_2+cx_3=q$ with $a+b+c=1$.
Form the augmented matrix with $d+1$ rows and $3+1$ columns: $$\left[\begin{array}{ccc|c}1&1&1&1\\ x1&x2&x3&q\end{array}\right]$$ Solve it with row reduction. If there is no solution, it is not even in the plane. If $a$ and $b$ and $c$ are all positive, it is within the triangle. If one of them is zero, it is on an edge of the triangle; if two of them are zero, then $q$ is one of the three points $x1,x2,x3$

Answer 2

You can check that $q$ lies in the same plane as the triangle by checking if e.g. the vectors $(q-x_1)$, $(x_2-x_1)$, and $(x_3-x_1)$ are not linearly independent.

You can then check that $q$ is also bounded by all of the triangle's line segments by checking that the segments $(q,(x_1+x_2+x_3)/3)$ and $(x_i,x_j)$ don't intersect, for all choices $i,j$ of $1,2,3$.