点が三角形の内側にあるかどうか

point-in-triangle.png

やり方は3通りあります

  1. 外積を使って、1辺ずつ点の位置との相対関係を調べる方法
  2. 重心座標を使う方法
  3. 内積を使う方法

1.の方法は図形が三角形じゃなくてもどの図形でも使える汎用的な方法です。
2.の方法は三角形ならではの方法です。

2次元平面上の点が有向線分の進行方向に対して左右どちら側にあるかを調べる関数

// 2次元平面上の点が有向線分の進行方向に対して左右どちら側にあるかを調べる関数を作る。
//*********************************************************
// 点 p が有向線分 e(a,b) の左右どちら側にあるか調べる。
// 点 p が有向線分 e の 左側にある場合  1 を、
//      有向線分 e の直線上にある場合  0 を、
//      有向線分 e の 右側にある場合 -1 を返す。
//*********************************************************
int CTriangle::side( CVertex *p, CLine *e )
{
    CVertex p1 = *p;
    CVertex p2 = *(e->begin); // 有向線分 e の始点
    CVertex p3 = *(e->end); // 有向線分 e の終点
 
    // 有向線分 (p2,p1), (p2,p3) の外積の z 成分を求める
    const int n  = p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
    if      ( n > 0 ) return  1; // 左
    else if ( n < 0 ) return -1; // 右
    else              return  0; // 線上
}//side

PtInTriangle

POINTSTATE CTriangle::PtInTriangle3(CVertex *_pt){//これが一番のオーバーヘッド
//http://katsura-kotonoha.sakura.ne.jp/prog/c/tip00030.shtml
CLine ab, bc, ca;
    ab.begin = this->a; ab.end = this->b;
    bc.begin = this->b; bc.end = this->c;
    ca.begin = this->c; ca.end = this->a;
    const int pab = side( _pt, &ab ); // 有向線分 ab から見た点 p の方向
    const int pbc = side( _pt, &bc ); // 有向線分 bc から見た点 p の方向
    const int pca = side( _pt, &ca ); // 有向線分 ca から見た点 p の方向
 
    // 三角形の内側にあれば正
    //if ( (0 < pab) && (0 < pbc) && (0 < pca) )
        //return 1; // 点 p が常に左側にある(時計回り)
    if ( (0 > pab) && (0 > pbc) && (0 > pca) )
        return INSIDE; // 点 p が常に右側にある(反時計回り)
 
    // 三角形の線上にあれば負
    //if ( (0 <= pab) && (0 <= pbc) && (0 <= pca) )
    //    return -1; // 点 p が常に左側にある(時計回り)
    if ( (0 >= pab) && (0 >= pbc) && (0 >= pca) )
        return INSIDE; // 点 p が常に右側にある(反時計回り)
 
    // 三角形の外側にあれば 0
    return OUTSIDE;
 
}
bool CTriangle::PtInTriangle(CVertex *_pt){
    //Same Side Technique
    //http://www.blackpawn.com/texts/pointinpoly/default.html
    CVertex ab;
    ab.CalcVector(this->initialedge->begin,this->initialedge->end);
    CVertex ap;
    ap.CalcVector(this->initialedge->begin,_pt);
    if(ab.CrossProduct(ap)<0){//内側
        CVertex ca;
        ca.CalcVector(this->initialedge->prev->begin,this->initialedge->begin);
        CVertex cp;
        cp.CalcVector(this->initialedge->prev->begin,_pt);
        if(ca.CrossProduct(cp)<0){
            CVertex bc;
            bc.CalcVector(this->initialedge->end,this->initialedge->prev->begin);
            CVertex bp;
            bp.CalcVector(this->initialedge->end,_pt);
            if(bc.CrossProduct(bp)<0){return true;}else{return false;}
        }else{return false;}
    }else{return false;}
 
}

重心座標を使う方法(この方法が一番良かった気がする)

POINTSTATE CTriangle::PtInTriangle2(CVertex *_pt,CVertex* _scale,CVertex* _offset){
    //Barycentric Technique
    //http://www.blackpawn.com/texts/pointinpoly/default.html
    // Compute vectors    
    CVertex aa(a->x*(_scale->x)+_offset->x,a->y*(_scale->y)+_offset->y);
    CVertex bb(b->x*(_scale->x)+_offset->x,b->y*(_scale->y)+_offset->y);
    CVertex cc(c->x*(_scale->x)+_offset->x,c->y*(_scale->y)+_offset->y);
 
    CVertex v0 = (cc) - (aa);
    CVertex v1 = (bb) - (aa);
    CVertex v2 = *_pt - (aa);
 
    // Compute dot products
    double dot00 = v0.CalcInnerProduct(&v0);
    double dot01 = v0.CalcInnerProduct(&v1);
    double dot02 = v0.CalcInnerProduct(&v2);
    double dot11 = v1.CalcInnerProduct(&v1);
    double dot12 = v1.CalcInnerProduct(&v2);
 
    // Compute barycentric coordinates
    double invDenom = 1 / (dot00 * dot11 - dot01 * dot01);
    double u = (dot11 * dot02 - dot01 * dot12) * invDenom;
    double v = (dot00 * dot12 - dot01 * dot02) * invDenom;
    //printf("u=%.8f,v=%.8f\n",u,v);
    // Check if point is in triangle
    if( (u >= 0) && (v >= 0) && (u + v <= 1)){
 
        if(u>=-EPSIRON && u<=EPSIRON  ){return INIEDGE;}
        if(v>=-EPSIRON&& v<=EPSIRON ){return PREVEDGE;}
        if(u + v >= 1.0-EPSIRON &&u + v <= 1.0+EPSIRON){return NEXTEDGE;}
        return INSIDE;
    }
 
    //printf("u=%.8f,v=%.8f\n",u,v);
 
    return OUTSIDE;
}

barycentric-coordinates delaunaytriangulation interpolation-in-random-points triangle

サポートサイト Wikidot.com barycentric-coordinatesdelaunaytriangulationinterpolation-in-random-pointstriangle