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 have a 3D plane defined by three points: $P_0$ , $P_1$ and $P_2$. How to check whether a point $P$ is located right on and inside the 3D triangle?

So, for example, if I have a plane defined by $({0,0,0})$, $({10,0,0})$ and $({0,10,0})$, then the point $({50,0,0})$ is considered not located on the plane, whereas the point $({5,0,0})$ is.

share|improve this question
    
Does $P$ have to be within the triangle defined by the three points, or you just want to check that $P$ satisfies the equation of the plane? –  J. M. Sep 9 '10 at 6:28
    
@J.M. Yes, it has to be. See the updated question. –  Graviton Sep 9 '10 at 6:31
    
A point-in-polygon test: ics.uci.edu/~eppstein/161/960307.html in conjunction with the determinant check provided by Robin, should be suitable for your purposes. –  J. M. Sep 9 '10 at 6:43
2  
As I thought, it was already asked at stackoverflow.com/questions/924171 –  J. M. Sep 9 '10 at 6:49
1  
If you're going to be implementing this in a computer program, beware that because of floating-point error your point P will almost surely not lie exactly on the plane defined by the other three points. –  Rahul Sep 9 '10 at 7:19

3 Answers 3

up vote 4 down vote accepted

Try to solve the system $$ x * (P_1 - P_0) + y * (P_2 - P_0) = P - P_0 $$ If it is solveable, the point $P$ lies on the plane. If in addition $x \geq 0$, $y \geq 0$, and $x + y \leq 1$, then $P$ lies inside the triangle.

share|improve this answer
    
I believe this should say x*(P_1-P_0)+y*(P_2-P_0)=P-P_0. –  Jonas Kibelbek Sep 9 '10 at 8:16
    
Michael, I'm trying to understand your solution... is this three equations in two unknowns? –  J. M. Sep 9 '10 at 8:19
    
@J.M. Yes, these are three equations (one for each dimension) in the two skalar unknowns x and y. –  Michael Ulm Sep 9 '10 at 8:31
    
@Jonas Kibelbek: Good Catch. Corrected. –  Michael Ulm Sep 9 '10 at 8:31
    
Hmm... so it's an overdetermined system. Would least squares apply here, or is there a specialized method for this problem? –  J. M. Sep 9 '10 at 8:49

A common technique in a computer program is to use barycentric coordinates.

Barycentric coordinates are a lot easier to find than any web resources indicate, so I'm not linking to them.

The easiest way to obtain barycentric coordinates of a point P, given a triangle with vertices described by the vectors A, B, C is likely this method:

$ AreaABC = \frac{ \left| \overline{AB} \times \overline{AC} \right| }{ 2 } $

$ \alpha = \frac{ \left| \overline{PB} \times \overline{PC} \right| }{ 2AreaABC } $

$ \beta = \frac{ \left| \overline{PC} \times \overline{PA} \right| }{ 2AreaABC } $

$ \gamma = 1 - \alpha - \beta $

Here $\alpha$ is the ratio of the area of a subtriangle PBC over the area of the whole triangle ABC, as shown in this image from Peter Shirley's book:

If ALL of $ 0 \le \alpha \le 1, 0 \le \beta \le 1, 0 \le \gamma \le 1 $, then the point P is inside the triangle.

If ANY of $\alpha$,$\beta$,$\gamma$ are outside those ranges, then the point P is not inside the triangle.

Note also when one of $\alpha$,$\beta$,$\gamma$ is 0, and the other 2 coordinates are between 0 and 1, the point P is on an edge of the triangle.

When one of $\alpha$,$\beta$,$\gamma$ is 1 and the other two are 0, then the point P is exactly at a vertex of the triangle.

Of course, these computations assume P is already in the plane of the triangle. If P is not in the plane of the triangle, then you should project it there first, before computing the barycentric coordinates.

share|improve this answer
    
See also Vector3.Barycentric on MSDN –  bobobobo Mar 24 '11 at 1:41
    
If $P$ is not in the plane, there is an elegant solution here math.stackexchange.com/questions/544946/… –  Håkon Hægland Oct 30 '13 at 0:59

There may well be a more efficient algorithm, but here's a way to check that P is on the triangle defined by the three points

Compare the cross products $\vec {P_0 P_1} \times \vec {P_0 P_2} = \vec a$ and $\vec {P P_1} \times \vec {P P_2} = \vec b$. If $\vec b = k_1 \vec a$ with $k_1 \geq 0$, then P is on the plane and is on the correct side of the line through P1 and P2.

Now, compute $\vec {P P_2} \times \vec {P P_0} = \vec c$ and $\vec {P P_0} \times \vec {P P_1} = \vec d$. If $\vec c = k_2 \vec a$ and $\vec d = k_3 \vec a$ with $k_2, k_3 \geq 0$, then P lies within the triangle.

Of course, there's a lot of redundancy in this calculation. Once we know P is on the plane, we could just check one coordinate of the $\vec c$ and $\vec d$ to see that they have the correct sign. This is just projecting the problem onto one of the coordinate planes.


My old answer below explains how to check that P is on the infinite plane defined by the first three points, not how to check if it lies inside the triangle defined by the first three points, which is what the question intended.


A general plane equation is Ax + By + Cz = D. The 3-dimensional vector <A,B,C> is perpendicular to the plane.

(Note that there is not a unique equation of this form; you can multiply the equation by any nonzero number and get another equation of the plane. --So you can try to find a solutions with D=1, and if that doesn't work, use D=0.)

If you find an equation of the plane defined by your first three points, you can just plug in the fourth point to check if it satisfies the equation.

You can solve for the plane equation by hand by setting up equation from the first three points; but a more efficient method is to take the cross product of the vector $\vec {P_0 P_1}$ and the vector $\vec {P_0 P_2}$, and to use the resulting vector as <A,B,C>. You'll find it very useful to understand the cross product if you like working in 3-D space.

share|improve this answer
    
please not that the point has to be located inside the triangle. Not sure how your solution checks for this. –  Graviton Sep 9 '10 at 6:49

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.