凸多角形の内部判定
ある任意の位置が凸多角形の内部にあるかどうかの判定アルゴリズムの簡単な実装をメモしておく。とりあえず正常に動作すれば良し、という考え方で。isInside内の、forループのきれいな回し方があれば、それを模索する必要はありそう。
以下のコードは、Processing 0091用。
//! 凸多角形の頂点配列(左回り). int[][] g_points = {{10,75},{120,95},{360,100},{300,5},{70,25}}; // 準備. void setup() { size(400, 120); strokeWeight(1); framerate(30); } // 描画. void draw() { //! 背景の色. if( isInside( mouseX, mouseY, g_points ) ){ background( 250 ); } else{ background( 100 ); } //! 多角形を描画. int[] pre_point = {g_points[4][0], g_points[4][1]}; for( int i=0; i<5; i++ ){ line( pre_point[0], pre_point[1], g_points[i][0], g_points[i][1] ); pre_point[0] = g_points[i][0]; pre_point[1] = g_points[i][1]; } } // // pointsに渡すのは、凸多角形の左回りの頂点配列. boolean isInside( int x, int y, int[][] points ) { int X0, Y0; // チェックする点のベクトル. int X1, Y1; // 調べる辺のベクトル. for( int i=0; i<points.length-1; i++ ){ X0 = x - points[i][0]; Y0 = y - points[i][1]; X1 = points[i+1][0] - points[i][0]; Y1 = points[i+1][1] - points[i][1]; if( X0*Y1 - X1*Y0 < 0 ){ return false; // 外側にある. } } X0 = x - points[points.length-1][0]; Y0 = y - points[points.length-1][1]; X1 = points[0][0] - points[points.length-1][0]; Y1 = points[0][1] - points[points.length-1][1]; if( X0*Y1 - X1*Y0 < 0 ){ return false; } else{ return true; } }