How do I test if a 3d point is to the "left" or "right" of a triangle in 3-space? I'm attempting to determine if a point in 3-space is inside or outside of a convex polyhedron with triangular sides.  One strategy, I suppose, is to determine which side of each triangle the point is on.  If the point is on the same side of each triangle, then it will be inside the convex polytope.  What is the best method to perform this test?
 A: Here is a method:
Suppose the convex polytope is described by a collection of triangles $T_k$, where each triangle is a face. 
Let $\bar{x} = \frac{1}{n} \sum_k x_k$, where the vertices of the polytope are $\{x_k\}$. Each triangle is of the form $T_k = \{x,y,z \} \subset \mathbb{R}^3$. Define the normal $n_k = (y-x) \times (z-x)$,  let $\alpha_k = \langle n_k , x \rangle$ and $\beta_k = \langle n_k , \bar{x} \rangle - \alpha_k$.
Choose $p \in \mathbb{R}^3$ and a triangle $T_k$. Let $\gamma_k = \langle n_k , p \rangle -\alpha_k$. Then $p$ is on the hyperplane passing through  $T_k$ if $\gamma_k = 0$, 'inside' the triangle if $\gamma_k$ and $\beta_k$ have the same sign, and 'outside' otherwise.
Then $p$ will be 'inside' the polyhedron iff it is 'inside' each triangle $T_k$.
Normal computation: Let $a=y-z$, $b=z-x$. Then $n = (y-x) \times (z-x) = ( a_2 b_3 - a_3 b_2, a_3 b_1 - a_1 b_3, a_1 b_2 - a_2 b_1 )$. For a simple example, take $x= (0,0,0), y=(0,1,0), z=(0,0,1)$, then the formula gives $(1,0,0)$.
A: I would represent the polytope via a system of linear constraints in 3 variables, and for each point in question, verify that constraints are satisfied (potentially costing a multiplcation of a matrix by a vector each time).
Advantage of this approach is that you can preprocess the constraints for the polytope, leaving just the matrix multiplication for the time of the evaluation.
A: If you're concerned about efficiency, point location is a well studied problem in computational geometry. Depending on how many points you need to locate, you might be interested in a sub-linear time query time $i.e.$ instead of testing $n$ triangles every time you need to check a point, pre-process the polyhedron so you can check inclusion in something like $O(\log^2 n)$ time. 
