Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
The best method depends on how your polyhedron is characterized. How? –  Lord Soth Apr 18 '13 at 18:30
    
@LordSoth I have a set of triangular faces that form a closed surface. The simplest example would be three triangles forming a simplex. More generally, I have a skeleton graph with vertices and edges defining the 3-polytope. –  John Apr 18 '13 at 18:36
2  
@John: Testing if a point is to the "left" or "right" of a plane is done by calculating scalar products. However, an easier way for you to see if your point is inside the polytope is to see if the line segment between your point, and a point which is definitely outside the polytope, intersects one of your triangles. –  Samuel Apr 18 '13 at 18:40
    
As @LordSoth said, it depends on your characterization of the problem. One way is to first compute an 'inside' point by taking the average of all vertices. Then, for each face, compute a normal using the cross product. Then determine which 'side' of the normal is inside or outside. –  copper.hat Apr 18 '13 at 18:49
1  
Well, you need to compute the inner product of a point on the triangle with the normal and similarly the inner product of the barycentre with the normal. This gives you the 'direction'. Then compute the inner product of an arbitrary point with the normal, and use the previous numbers to decide 'inside', 'on' or 'outside'. –  copper.hat Apr 18 '13 at 19:03
show 2 more comments

3 Answers

up vote 2 down vote accepted

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)$.

share|improve this answer
    
Thanks! To make sure I understand the point about computing the normal, could you give me a simple example? –  John Apr 18 '13 at 20:02
    
@John: Sure, I gave the formula and a simple example above. –  copper.hat Apr 18 '13 at 20:12
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.