ポリゴンに対する内外の判定

ある点がポリゴンの中にあるかどうかを調べるには、ポリゴンに対して十分に離れている点とその点を結んだ直線がポリゴンの辺と何回交差したかを調べ、偶数回であれば外、奇数回であれば内側にあると判断できます。

２つの線分が交差するかどうかを調べるには、一方の線分の２点ともう一方の線分の頂点との回り方向を調べ、異なる回りであれば交差すると判断できます。

３点が時計回りか反時計回りかを調べるには以下のようにします。
p1；(x1,y1)、p2；（x2,y2）、p3；（x3,y3）とすると、
(x2-x1)*(y3-y1)と(x3-x1)*(y2-y1)を比較して、負なら反時計回り、正なら時計回り、等しければ直線になります。

ただし、ポリゴンの内外を判定するときに判定の対象となる点と十分に遠い点の直線上にポリゴンの頂点がある場合の取り扱いに注意が必要です。

//３点が時計回りかどうかを調べる
//時計回りなら１，反時計回りで-1、直線で０を返す。
int clckw(double p1x, double p1y, double p2x, double p2y, double p3x, double p3y)
{
    int a;
    double dx2, dy2, dx3, dy3;

    dx2 = p2x - p1x;
    dy2 = p2y - p1y;
    dx3 = p3x - p1x;
    dy3 = p3y - p1y;

    if ( ( dx2 * dy3 ) > ( dx3 * dy2 ) ) a = -1;
    else if ( ( dx2 * dy3 ) < ( dx3 * dy2 ) ) a = 1;
    else a = 0;

    return a;
}

//２つの線分が交差するかどうかを調べる。
//交差するときに１，しないときは０を返す。
int cross(double xa1, double ya1, double xa2, double ya2,
 double xb1, double yb1, double xb2, double yb2)
{
    int b;

    if ( ( clckw( xa1, ya1, xa2, ya2, xb1, yb1 ) *
        clckw( xa1, ya1, xa2, ya2, xb2, yb2 ) ) < 0 && 
        ( clckw( xb1, yb1, xb2, yb2, xa1, ya1 ) *
        clckw( xb1, yb1, xb2, yb2, xa2, ya2 ) ) < 0 )
    {
        b = 1;
    }
    else b = 0;

    return b;
}

//ある点( xp, yp )がpolygの中にあるかどうかを調べる。
//中にあれば１、外にあれば０を返す。
int io(double xp, double yp, double **polyg, int lines )
{
    int i, a = 0;

    for ( i = 0; i < lines; i++ )
    {
        if ( i != lines - 1 )
        {
            a+=cross( 0,0,xp,yp,polyg[i][1],polyg[i][2],polyg[i+1][1],polyg[i+1][2] );
        }
        else
        {
            a+=cross( 0,0,xp,yp,polyg[i][1],polyg[i][2],polyg[0][1],polyg[0][2] );
        }
    }
    return a % 2;
}

参考文献

計算幾何学と地理情報処理