サイトマップ
お知らせ、メモ
案内板
うちのヘッドライン
 




トップ  >  プログラム豆知識  >  アルゴリズム豆知識  >  ポリゴンに対する内外の判定

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

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

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

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

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

//3点が時計回りかどうかを調べる
//時計回りなら1,反時計回りで-1、直線で0を返す。
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;
}

//2つの線分が交差するかどうかを調べる。
//交差するときに1,しないときは0を返す。
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の中にあるかどうかを調べる。
//中にあれば1、外にあれば0を返す。
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;
}

参考文献

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

クリエイティブ・コモンズ・ライセンス
This documents by Yamate,N is licensed under a Creative Commons 表示 - 継承 3.0 非移植 License.
login