Algorithm to check that a point is in the convex rule of $4$ points in the $3$-dimensional space

Question

I am looking for an algorithm to check easily that a point $A(x,y,z)$ is in the convex hull of $4$ points $A_i(x_i,y_i,z_i)$ in the usual $3$-dimensional Euclidean space. The only algorithm I see comes from my Math education (I really know nothing specific about this subject). It consists of solving the $4$-dimensional linear system $k_1A_1+k_2A_2+k_3A_3+k_4A_4 = A$ and $k_1+k_2+k_3+k_4=1$ using Cramer's rule and to check that $k_1,\dots,k_4$ belong to the interval $[0,1]$ (I forget on purpose the case where the main determinant is $0$). That requires to calculate five $4$-dimensional determinants. Is there any simpler way for this particular case ?

Answer 1

You just need to implement a signed-volume function for tetrahedra. See below for one source (among many). You will need to orient the faces of your tetrahedron consistently counterclockwise.

Then your point p(=A) is in the tetrahedron a,b,c,d if and only if the volume of p,a,b,c is negative, and similarly negative for all four faces and p. If p is outside the tetrahedron, one or more of those volumes will be positive. (Interchange counterclockwise with clockwise just flips all the signs.)

---

     
      ^{Computational Geometry in C}

---