10
$\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
    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
15

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:

how to find barycentric coordinates

If ALL of the following 4 restrictions are met:

  • $ 0 \le \alpha \le 1 $
  • $ 0 \le \beta \le 1 $
  • $ 0 \le \gamma \le 1 $
  • $\alpha + \beta + \gamma = 1$

then the point P is inside the triangle.

Note if you compute $\gamma$ as I did above (using $\gamma = 1 - \alpha - \beta$) then you don't have to check $\alpha + \beta + \gamma = 1$, but you would if you found $\gamma$ using areas (as shown in the diagram).

If ANY of $\alpha$,$\beta$,$\gamma$ are outside those ranges, or if the sum of $ \alpha + \beta + \gamma \ne 1 $ 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
    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
8

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