How to check if a point in a triangle (or on it's edge)-CodePudding

I'm trying to write an algorithm to determine if point is located inside a triangle or on it's edge in 3D coordinate space. For example, I try to reach such results for different cases

I've figured out how to check if point P inside the triangle, I calculated normal vectors for triangles ABP, BCP, CAP and checked if they are similar.

Can someone explain how to check if a point is on the edge of a triangle (but not outside of a triangle)? You can provide formulas or code as you wish.

CodePudding user response：

Make vectors:

r = p - A (r.x = p.x - A.x, r.y = p.y - A.y, r.z = p.z - A.z)
s = B - A
q = C - A

Calculate normal to ABC plane:

n = s x q  (vector product)

Check if p lies in ABC plane using dot product:

dp = n.dot.r

If dp is zero (or has very small value like 1.0e-10 due to the floating point errors, then p is in the plane, and we can continue

Decompose vector p by base vectors s and q. At first check if z-component of normal (n.z) is non-zero. If so, use the next pair of equations (otherwise choose equations for x/z or y/z components):

px = a * sx   b * qx
py = a * sy   b * qy

Solve this system

a =  (sy * qx - sx * qy) / (py * qx - px * qy)  
b =  (px - a * sx) / qx

If resulting coefficients a and b fulfill limits:

a >= 0
b >= 0
a   b <= 1.0

then point p lies in triangle plane inside it.

CodePudding user response：

If the point and the triangle are unrelated (by the nature of the problem), the probability of the point being in the plane is zero, so you could return false all the time, with very little chance to be wrong. :-)

On the opposite, a point truly being in the plane will have little chance of exactly fulfilling the plane equation, due to numerical errors. So you need a tolerance, such as accepting a maximum distance to the plane or to the edges.

This said, a convenient method is by transforming space so that the triangle comes to the XY plane. For this, translate one vertex to the origin, take the vectors formed by the other two and generate an orthogonal frame on them (by the Gram-Schmidt process and cross-product). You will obtain a change-of-basis matrix, the inversion of which is immediate, as it is orthogonal.

Now you have a triangle in XY, and the distance of the test point to the plane of the triangle is just its |Z|. And the point is inside the triangle (when projected to XY) if it lies on the same side of the three sides, taken in cyclic order (this takes the computation of three determinants).

The point lies on an edge if it is aligned with two vertices and on the good side of the other two edges. Here we still face the numerical problem so it is better to estimate the distance to the edge to assess alignment. By Pythagoras, the 3D distance to the edge is the distance to the edge in 2D combined with the distance to the plane.