判断一个点是否在 3D 三角形内space

Question

我有一个由 3 个 3D 顶点表示的 3D 三角形。

我正在寻找必须满足以下要求的算法：

一个点位于三角形定义的同一平面上，
该点位于所述三角形的边界内

例如：

Answer 1

定义基向量b=AB, c=AC 和 n= b x c （向量积），其中 A, B , C - 三角形顶点坐标
在此基础上表示点P坐标，这里求解linear equation system (unknown t,u,v). Gaussian elimination method比较合适。

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

根据你的图片点是'inside'，如果

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

Answer 2

假设 ABC 是你的三角形，要知道一个点是否与三角形 ABC 在同一平面上，我们可以使用 cross and dot 乘积。如果点P在同一平面上那么，

(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

对于（2），最简单的方法是使用Barycentric coordinate来知道一个点是在三角形的内部还是在三角形的边界上。三角形内的任意一点P都可以表示为

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)

假设，X = P-A，Y = B-A，Z = C-A。那么等式就变成了，

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

现在我们要解下面两个未知数的线性方程。

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

求解这两个方程我们得到，

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)

判断一个点是否在 3D 三角形内space

Determine whether a point is inside triangle in 3D space

c++

algorithm

geometry