9
$\begingroup$

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.

  • 0
    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?2010-09-09
  • 0
    @J.M. Yes, it has to be. See the updated question.2010-09-09
  • 0
    A point-in-polygon test: http://www.ics.uci.edu/~eppstein/161/960307.html in conjunction with the determinant check provided by Robin, should be suitable for your purposes.2010-09-09
  • 2
    As I thought, it was already asked at http://stackoverflow.com/questions/9241712010-09-09
  • 0
    @Robin, I've make a requirement that the point must be inside the triangle defined by the three points.2010-09-09
  • 0
    @J.M., is there a 3D analogue for the above algorithm? I hate the idea of casting the 3D plane into a 2D one and perform the check.2010-09-09
  • 0
    Ngu: I **knew** you'd say that... ;) I will have to dig around the CG literature if there's anything that doesn't need projection.2010-09-09
  • 0
    A suggestion: maybe change the title to something like "Check if a point is within a 3D Triangle" or something like it.2010-09-09
  • 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.2010-09-09
  • 0
    Once we know P is on the plane, we can throw away 1 coordinate and treat it as a 2-D problem, as long as the normal vector is nonzero in that coordinate.2010-09-09
  • 0
    How can you have a 3D plane, planes are 2D?2014-05-29

4 Answers 4

0

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.

  • 0
    please not that the point has to be located inside the triangle. Not sure how your solution checks for this.2010-09-09
13

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.

  • 0
    See also [Vector3.Barycentric](http://msdn.microsoft.com/en-us/library/bb195068.aspx) on MSDN2011-03-24
  • 0
    If $P$ is not in the plane, there is an elegant solution here http://math.stackexchange.com/questions/544946/determine-if-projection-of-3d-point-onto-plane-is-within-a-triangle2013-10-30
  • 0
    This doesn't work, try $a = [0.5, 0, -1]$, $b = [0.5, 0, 1]$, $c = [0.92, 1.2, 0]$ and check if $p = [1, 1.4, 0]$ is in there. It won't work.2015-10-11
  • 0
    Your conclusion is incorrect. P is inside the triangle ONLY if $ \alpha, \beta, \gamma \ge 0 $ AND $ \alpha + \beta + \gamma = 1 $2018-10-24
  • 0
    A, alpha, and beta will always be positive (areas) and so gamma could also be positive even if the point lies outside the triangle. Something isn't quite complete about your algorithm. Should we be keeping track of the signs of the cross products by dotting them with the unit normal instead? See correct solution here: https://math.stackexchange.com/questions/544946/determine-if-projection-of-3d-point-onto-plane-is-within-a-triangle/5449472018-10-25
6

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.

  • 0
    I believe this should say x*(P_1-P_0)+y*(P_2-P_0)=P-P_0.2010-09-09
  • 1
    Michael, I'm trying to understand your solution... is this three equations in two unknowns?2010-09-09
  • 1
    @J.M. Yes, these are three equations (one for each dimension) in the two skalar unknowns x and y.2010-09-09
  • 0
    @Jonas Kibelbek: Good Catch. Corrected.2010-09-09
  • 1
    Hmm... so it's an overdetermined system. Would least squares apply here, or is there a specialized method for this problem?2010-09-09
  • 0
    Michael's solution is correct. If P is your test point, first of all you want the three vectors P_1-P_0, P_2-P_0 and P-P_0 to be coplanar, i.e. linerly dependent. That's the linear equation in x and y whose solvability is equivalent to the vanishing of some determinant (as noted also by others).2010-09-09
  • 0
    Moreover the conditions on the coefficients are those that characterize the points in the simplex spanned by the vectors (just two vectors, in this case), which is the convex hull of the points P_0. P_1 and P_2, i.e. the triangle that they define. Everything generalizes straightforwardly in arbitrary dimension.2010-09-09
2

Vectors $V_{01}=P_1-P_0$ and $V_{02}=P_2-P_0$ lie in the plane of the triangle, and $V_{01}\times V_{02}$ is normal to this plane. Let $V_{0p}=P-P_0$, and if $V_{0p} \cdot (V_{01}\times V_{02}) = 0$ then $P$ lies in the plane.

Let $P=cP_0+aP_1+bP_2$ where $c=1-a-b$. Then $P=(1-a-b)P_0+aP_1+bP_2$ or $V_{0p}=aV_{01}+bV_{02}$. If $0 \le a,b,c \le 1$ then $P$ lies in the triangle or on its edge.

Vector $V_{01} \times (V_{01}\times V_{02})$ is orthogonal to $V_{01}$ so $V_{02} \cdot(V_{01} \times (V_{01}\times V_{02}))b=V_{0p} \cdot(V_{01} \times (V_{01}\times V_{02}))$ can be solved for b.

Likewise $V_{02} \times (V_{01}\times V_{02})$ is orthogonal to $V_{02}$ so $V_{01} \cdot(V_{02} \times (V_{01}\times V_{02}))a=V_{0p} \cdot(V_{02} \times (V_{01}\times V_{02}))$ can be solved for a.