How to check if point $x \in \mathbb{R}^n$ is in a $n$-simplex?

Question

Is there any universal solution how to check if a point $x \in \mathbb{R}^n$ is in $n$-simplex for any number of dimensions (any $n$)?

Is it possible to use Barycentric coordinates for any $n$? I have only found examples for 2 and 3 dimensions.

Answer 1

Yes, barycentric coordinates can be easily used with any number of dimensions to determine if a point $\textbf{p} \in \mathbb{R}^n$ is in a simplex $\textbf{S} = (\textbf{v}_1, \dots, \textbf{v}_{n+1})$, where $\textbf{v}_i \in \mathbb{R}^n, i=1,\dots,n+1$ are simplex vertexes.

Simply solve this equation, to get barycentric coordinates: $$\lambda = \textbf{T}^{-1}(\textbf{p} - \textbf{v}_{n+1}), \;\textrm{where}\\ \textbf{T} = (\textbf{v}_1 - \textbf{v}_{n+1}, \dots, \textbf{v}_n - \textbf{v}_{n+1})^T$$

If barycentric coordinates $$\lambda = (\lambda_1, \dots, \lambda_n), \\\lambda_{n+1} = 1-\sum \lambda_i, i=1,\dots,n$$ satisfies these two conditions: $$ \lambda_i \ge 0,\\ \sum \lambda_i \le 1, \\i = 1, \dots, n+1$$ the point is in the simplex, $\textbf{p} \in \textbf{S}$.

Otherwise, its outside of the simplex, $\textbf{p} \notin \textbf{S}$.

Answer 2

Let be $v_0,v_1,\ldots, v_n\in \mathbb R^n$ the vertices of an n-simplex. If this simplex is non degenerated, the vectors $v^*_1=v_1-v_0,\,v^*_2=v_2-v_0,\ldots, \,v^*_n=v_n-v_0$ are linear independent so they are a basis of $\mathbb R^n$. It means $$x-v_0=\alpha_1v^*_1+\alpha_2v^*_2+\ldots+\alpha_nv^*_n$$ where the coefficients $\alpha_1,\ldots,\alpha_n$ are uniquely determined by the point $x$. We claim $x$ is in our simplex if and only if $\alpha_i\geq 0$ for every $i=1,\ldots,n$ and $\sum\alpha_i\leq1$. To show it we compute the baricentric coordinates of $x$: $$x=\left(\alpha_1+\ldots+\alpha_n + \left(1-\sum\alpha_i\right)\right)x=\alpha_1v_1+\ldots+\alpha_nv_n+\left(1-\sum\alpha_i\right)v_0.$$ As we know x is in the convex hull of the $v_i$s if and only if all of these coordinates aren't negative. This is equivalent to our condition qoud erat demonstrandum.