点と三角形の当たり判定( 内外判定 )

外積を使った三角形の内外判定法とプログラミング例。

点と三角形の内外判定法

同一平面上にある三角形と点について、
三角形の内側に点があるかどうかは、外積を使って調べることができます。

三角形の内側に点があるとき、外積によるベクトルは３つとも同じ方を向きます

三角形の外側に点があるとき、外積ベクトルの向きは揃いません

この性質を利用して、３つの外積ベクトルの向きを比較すると、三角形の内外判定ができます。

点と三角形の内外判定法プログラミング例

点と三角形の当たり判定を行うプログラムです。2D用３D用ありますが考え方は同じです。

点と三角形の内外判定 2Dの場合

3Dの場合はこちら...
３つの外積ベクトルを求め、Z成分を比較してベクトル方向が同じか判定します。

#include <math.h>
struct Vector2D{
    double x;
    double y;
};
//頂点の定義(ベクトルと同じ)
#define Vertex2D Vector2D

//ベクトル引き算(a-b)
Vector2D sub_vector( const Vector2D& a, const Vector2D& b )
{
    Vector2D ret;
    ret.x = a.x - b.x;
    ret.y = a.y - b.y;
    return ret;
}

// 三角形と点の当たり判定(2Dの場合)
// 戻り値    0:三角形の内側に点がある    1:三角形の外側に点がある
int hittest_point_polygon_2d( Vertex2D A, Vertex2D B, Vertex2D C, Vertex2D P ) {

    //線上は外とみなします。
    //ABCが三角形かどうかのチェックは省略...
    
    Vector2D AB = sub_vector(B, A);
    Vector2D BP = sub_vector(P, B);

    Vector2D BC = sub_vector(C, B);
    Vector2D CP = sub_vector(P, C);

    Vector2D CA = sub_vector(A, C);
    Vector2D AP = sub_vector(P, A);

    //外積    Z成分だけ計算すればよいです
    double c1 = AB.x * BP.y - AB.y * BP.x;
    double c2 = BC.x * CP.y - BC.y * CP.x;
    double c3 = CA.x * AP.y - CA.y * AP.x;

    if( ( c1 > 0 && c2 > 0 && c3 > 0 ) || ( c1 < 0 && c2 < 0 && c3 < 0 ) ) {
        //三角形の内側に点がある
        return 0;
    }

    //三角形の外側に点がある
    return 1;

}

点と三角形の内外判定 3Dの場合

2Dの場合はこちら...
３Dの場合は三角形と点が同一平面上にあることが前提です。同一平面上にないと正しく動作しません。
３つの外積ベクトルを求め、内積を使ってベクトル方向が同じか判定します。

#include <math.h>

//ベクトルの定義と各種計算
struct Vector3D{
    double x;
    double y;
    double z;
};

//頂点の定義(ベクトルと同じ)
#define Vertex3D Vector3D

//ベクトル引き算(a-b)
Vector3D sub_vector( const Vector3D& a, const Vector3D& b )
{
    Vector3D ret;
    ret.x = a.x - b.x;
    ret.y = a.y - b.y;
    ret.z = a.z - b.z;
    return ret;
}

//ベクトル外積( vl × vr )
Vector3D cross_product( const Vector3D& vl, const Vector3D& vr )
{
    Vector3D ret;
    ret.x = vl.y * vr.z - vl.z * vr.y;
    ret.y = vl.z * vr.x - vl.x * vr.z;
    ret.z = vl.x * vr.y - vl.y * vr.x;

    return ret;
}

//ベクトル内積
double dot_product( const Vector3D& vl, const Vector3D vr) {
    return vl.x * vr.x + vl.y * vr.y + vl.z * vr.z;
}

// 三角形と点の当たり判定(３Dの場合)
// 戻り値    0:三角形の内側に点がある    1:三角形の外側に点がある
int hittest_point_polygon_3d( Vertex3D A, Vertex3D B, Vertex3D C, Vertex3D P ) {

    //点と三角形は同一平面上にあるものとしています。同一平面上に無い場合は正しい結果になりません
    //線上は外とみなします。
    //ABCが三角形かどうかのチェックは省略...
    
    Vector3D AB = sub_vector(B, A);
    Vector3D BP = sub_vector(P, B);

    Vector3D BC = sub_vector(C, B);
    Vector3D CP = sub_vector(P, C);

    Vector3D CA = sub_vector(A, C);
    Vector3D AP = sub_vector(P, A);

    Vector3D c1 = cross_product( AB, BP );
    Vector3D c2 = cross_product( BC, CP );
    Vector3D c3 = cross_product( CA, AP );


    //内積で順方向か逆方向か調べる
    double dot_12 = dot_product(c1, c2);
    double dot_13 = dot_product(c1, c3);

    if( dot_12 > 0 && dot_13 > 0 ) {
        //三角形の内側に点がある
        return 0;
    }

    //三角形の外側に点がある
    return 1;

}

戻る　　　次へ