[明白なものの非自明なアルゴリズム]アルゴリズム2.空間内の三角形の点に属する

一連の投稿[自明でないものの非自明なアルゴリズム]には自明で単純に見えるアクションアルゴリズムが含まれますが、「これはどのように行われますか？」 もちろん、これらのアルゴリズムはすべて文献に記載されています。 カットの下に、点Pの空間内の三角形ABCへの帰属を決定するアルゴリズムがあります。

空間内の三角形ABCへの所属ポイントP

アイデア

ポイントが幾何学的図形に属しているかどうかを判断する必要がある場合があります。 最も単純なのは三角形のABCです。

与えられた：

ポイントP（P_x、P_y、P_z）、頂点のある三角形：A（A_x、A_y、A_z）、B（B_x、B_y、B_z）、C（C_x、C_y、C_z）。

方法論

3つの三角形が形成されます：ABP、ACP、BCP。 その後、それらの面積S _ABP 、S _ACP 、S _BCPが計算されます。 その後、これらの面積の合計が三角形の面積S _ABCでチェックされます。 ポイントが三角形ABC上にある場合、三角形ABP、ACP、BCPは三角形ABCの​​一部になり、それらの面積の合計はその面積S _ABCに等しくなります。 ポイントが三角形に属さない場合、面積S _ABP 、S _ACP 、S _BCPの合計は、三角形ABCの​​面積を超えます。

三角形の面積が何であるかを覚えていない人のための簡単な叙情的な余談：最も簡単な方法は、ヘロンの公式を使用することです。 便利に

機能コード：

#define EPS 1e-10 float triangle_square(float a,float b, float c){ float p=(a+b+c)/2; return sqrt(p*(pa)*(pb)*(pc)); } float inside_triangle(float P_x,float P_y, float P_z, float A_x, float A_y, float A_z, float B_x, float B_y, float B_z, float C_x, float C_y, float C_z){ int inside=0; float AB=sqrt( (A_x-B_x)*(A_x-B_x) + (A_y-B_y)*(A_y-B_y) + (A_z-B_z)*(A_z-B_z) ); float BC=sqrt( (B_x-C_x)*(B_x-C_x) + (B_y-C_y)*(B_y-C_y) + (B_z-C_z)*(B_z-C_z) ); float CA=sqrt( (A_x-C_x)*(A_x-C_x) + (A_y-C_y)*(A_y-C_y) + (A_z-C_z)*(A_z-C_z) ); float AP=sqrt( (P_x-A_x)*(P_x-A_x) + (P_y-A_y)*(P_y-A_y) + (P_z-A_z)*(P_z-A_z) ); float BP=sqrt( (P_x-B_x)*(P_x-B_x) + (P_y-B_y)*(P_y-B_y) + (P_z-B_z)*(P_z-B_z) ); float CP=sqrt( (P_x-C_x)*(P_x-C_x) + (P_y-C_y)*(P_y-C_y) + (P_z-C_z)*(P_z-C_z) ); float diff=(triangle_square(AP,BP,AB)+triangle_square(AP,CP,CA)+triangle_square(BP,CP,BC))-triangle_square(AB,BC,CA); if (fabs(diff)<EPS) inside=1; return inside; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

math.hをアタッチするのが面倒だと感じたら、 この投稿のルート関数を使用できます。