判断三维空间中的一个点是否在三角形内,边上的一种算法

时间:2021-05-11 09:43:31
   

   假设三角形的三点用A(Xa,Ya,Za),B(Xb,Yb,Zb),C(Xc,Yc,Zc)表示,判断P(Xp,Yp,Zp)与三角形ABC的关系

网上判断点是否处于三角内内部,边上的方法有很多,但是比较简洁的方法,比如面积法,即判断三角形PAB,PAC,PBC之和与三角形ABC的面积。如果S(PAB+PAC+PBC)=S(ABC),则点位于三角形内部,或边上。但是上述方法由于涉及到平方和开根号,计算量比较大。

   最近自己整理了一个计算量稍小的算法。具体如下:

判断三维空间中的一个点是否在三角形内,边上的一种算法

令向量(B-A)=(X1,Y1,Z1);向量(C-A)=(X2,Y2,Z2);向量(P-A)=(X3,Y3,Z3);

假设点P位于三角形ABC所在的平面,则向量(P-A)可以用向量(B-A)和(C-A)表示,即(P-A)=m*(B-A)+n(C-A);只要求出m,n的值即可判断点与三角形的关系。如果没有解,那么p不在三角形所在平面,如果有解,那么:                            若:          若:         若:

   m>0                         m=0;          n=0;         m>0;

   n>0;                        n>0;          m>0;         n>0;

   m+n<1                       m+n<1;         m+n<1;       m+n=1;

则P在三角形内部。               P在AC边上   P在AB边上      P在BC边上

 

所以,问题的关键是要计算m,n的值,从而可以得到点和三角形的空间关系。

具体步骤如下:

由(P-A)=m*(B-A)+n(C-A)得到(X3,Y3,Z3)=m*(X1,Y1,Z1)+n*(X2,Y2,Z2),写成矩阵形式,得到:

X1 X2      X3

Y1 Y2*     Y3

Z1 Z2      Z3

          X1X2                   X3

令矩阵K为  Y1Y2               b为 Y3

          Z1Z2                   Z3

      因为ABC为三角形,所以向量(B-A)=(X1,Y1,Z1);向量(C-A)=(X2,Y2,Z2)线性不相关,即矩阵K为列满秩矩阵,所以

    m

        =K的加号逆*b;

    n

其中K的加号逆为