CODEWITHSUNDEEP
c++algorithmgeometry
user3030712
user3030712

Reputation: 27

Determine whether a point is inside triangle in 3D space

I have a 3D triangle that is represented by 3x 3D vertices.

I'm looking for an algorithm that must cover the following requirements:

  1. a point lies on the same plane as defined by the triangle and
  2. that the point resides within the boundaries of said triangle

for example:

enter image description here

Upvotes: 1

Views: 4918

Answers (2)

t.muttaqueen
t.muttaqueen

Reputation: 11

Suppose ABC is your triangle, to know if a point is on the same plane as triangle ABC we can use cross and dot product. If point P in on the same plane then,

(P-A).( (B-A)x(C-A) ) = 0 
here [.] is dot product and [x] is cross product.
A, B, C are co ordinates of vertex of the triangle

For (2), Simplest way is to use Barycentric coordinate to know if a point lies inside or on the boundary of a triangle. Any point P inside a triangle can be represented as

P = a*A + b*B + c*C where 0 <= a, b, c <= 1 and a+b+c = 1 
(on boundary if at least one of a,b,c is zero)
Now, we can write, a = 1 - b - c.
   P = (1-b-c)*A + b*B + c*C
=> P-A = b*(B-A) + c*(C-A)

Suppose, X = P-A, Y = B-A, Z = C-A. Then the equation becomes,

X = b*Y + c*Z
taking dot product with Y and Z, we get
X.Y = b*(Y.Y) + c*(Z.Y)
X.Z = b*(Y.Z) + c*(Z.Z)
define x1 = X.Y, y1 = Y.Y, z1 = Z.Y, 
       x2 = X.Z, y2 = Y.Z, z2 = Z.Z

Now we have to solve the following linear equation with two unknown.

x1 = b*y1 + c*z1
x2 = b*y2 + c*z2

solving these two equation we get,

b = (x1*z2 - x2*z1)/(y1*z2-y2*z1)
c = (-x1*y2 + x2*y1)/(y1*z2-y2*z1)
a = 1 - b - c

Then we can easily check if a,b,c satisfies the condition. 
(actually checking 0 <= b,c <= 1 and b+c <= 1 is enough)

Upvotes: 1

MBo
MBo

Reputation: 80072

Define basis vectors b=AB, c=AC and n= b x c (vector product), where A, B, C - triangle vertices's coordinates
Represent point P coordinate in this basis, solving linear equation system (unknown t,u,v). Gaussian elimination method is suitable here.

t * b.X + u * c.X + v * n.X = P.X
t * b.Y + u * c.Y + v * n.Y = P.Y
t * b.Z + u * c.Z + v * n.Z = P.Z

Point is 'inside' according to your picture, if 

0 <= t <= 1
0 <= u <= 1
and
t + u <= 1

Upvotes: 2

Related Questions