【C言語】点と多角形の内外の包含判定法
スポンサーリンク
任意の点の集合で作られる多角形に任意の1点が含まれているかを判定する。
卒業論文でこのアルゴリズムを調べていたのですが中々見つからなかったので自作のモノを公開します。原理自体は極めて簡単なのでプログラムが苦手な方も是非使ってみてさい。
参考サイト様:http://kone.vis.ne.jp/diary/
多角形領域の包含関係
ある多角形にその点が含まれているかどうかは,多角形の連続する二点とその点との「符号付き角度」の総和が360度で判定する。総和が2πであれば領域内、それ以外であれば領域外である。
※符号付角度…右回りが左回りかで正負が異なる角度のことである.
- 領域に含まれる場合
符号付角度の総和が2πの場合、領域に含まれる。
- 領域に含まれない場合
符号付角度の総和が2πでない場合、領域に含まれない
これをC言語で書くと以下のようになる。動かなかったら細かいミスです。言ってくれれば直します;
//M角形の頂点座標の集合C(con[k].x,con[k].y)(k=0,...,M-1)に, //任意の点(x,y)が含まれているか判定する。 int judge(int x,int y){ int k; double tmp=0; double angle=0; for(k=0;k<M-1;k++){ tmp = Calc_tan(x,y,k); angle += tmp; } } //角度の総和が2πかどうか if( fabs(2*M_PI-fabs(angle)) < 0.001 ) return(1); //含まれている else return(0); //含まれていない } //各多角形の辺と点との向付き角度を計算する。 double Calc_tan(int x,int y,int k){ double Ax,Ay,Bx,By; double AxB,AvB; double angle; Ax = con[k].x - x; Ay = con[k].y - y; Bx = con[k+1].x - x; By = con[k+1].y - y; AvB = Ax * Bx + Ay * By; AxB = Ax * By - Ay * Bx; //ライブラリ関数atan2()はmath.hをインクルードしておくこと angle = atan2(AxB,AvB); return(angle); } //ただし多角形なので(con[0].x,con[0].y)と(con[M-1].x,con[M-1].y)は同一である