2011年9月6日火曜日

点が長方形の内側にあるかチェックする

点が長方形の内側にあるか否かをチェックするには、外積を使えばよい。

ある長方形(10,10),(30,10),(30,30),(10,30)と、ある点(20,20)があるとしよう。このある点がある長方形の内側にあるのか外側にあるのかを判定したい。このような長方形であれば、外積を使うまでもなくチェックが可能だが、長方形が回転している場合や、長方形以外の多角形の場合などになると、簡単ではなくなる。しかし、外積を使えば一発で分かる。外積はこのようにベクトルAとベクトルBの外積を求めた場合、その値がマイナスであればベクトルBはベクトルAの右側にあることになるので、長方形の各辺とある点が全て右側にあることを外積によって確かめればよい。(HTML5のcanvasの場合、座標は左上が原点となるので注意が必要じゃ。一般的な一番左下を原点とする形態であれば、長方形の各辺を時計回りにベクトルにしていけば、点がベクトルの右側にある場合、外積の数値はマイナスになるが、canvasの場合は反時計回りにベクトルにしていくとよい。マイナスになればベクトルの左側にあることにあり、(全ての辺に対して左側にあるのであれば)それはすなわち内側にあるということだ。)

まず、長方形の(30,10)-(10,10)の辺と点の位置関係を確認しよう。長方形の辺をベクトルにすると(-20,0)になる。長方形の辺の始点と点をベクトルにすると、(-10,10)となる。この2つのベクトルの外積を求めると、下記になる。
-20*10-10*0 = -200

マイナスなので点は辺の左側にあるということだ。これを全ての辺でチェックして、全ての結果がマイナスであれば内側にあるということになる。

javascriptによって内側判定をするとこうなる。

var x = 10; //長方形の左上x
var y = 10; //長方形の左上y
var w = 20; //長方形のwidth
var h = 20; //長方形のheight
var px = 20; //点のx
var py = 20; //点のy

function gaiseki(ax,ay,bx,by){
     return ax*by-bx*ay;
}

function pointInCheck(X,Y,W,H,PX,PY){
    var a = gaiseki(-W,0,PX-W-X,PY-Y);
    var b = gaiseki(0,H,PX-X,PY-Y);
    var c = gaiseki(W,0,PX-X,PY-Y-H);
    var d = gaiseki(0,-H,PX-W-X,PY-H-Y);
    if(a<0&&b<0&&c<0&&d<0) return true;
    else return false;
}

document.write(pointInCheck(x,y,w,h,px,py)); 


tureだから、内側にある。

0 件のコメント:

コメントを投稿