2011年9月11日日曜日

2011年9月6日火曜日

線分と線分の交差判定

線分と線分の交差判定をしたい。線分abと線分cdの交差判定をすることにしよう。交差判定には直線の方程式を使う。直線は、y=ax+bといった形になる。この直線よりも上に線分の一方の点があり、もう一方の点がこの直線よりも下にあればそれは、この直線と線分が交差するということだ。線分と線分の交差は、「ある線分ともう一方の線分を直線にしたものが交差し、かつ、もう一方の線分とある線分を直線にしたものが交差すれば」、それはすなわち線分と線分が交差することになるのだ。試してみたら分かるのだ。

よって、直線の方程式を使って上記条件に合致するか計算すればよろしい。
直線の方程式を変形しよう。y=ax+bをy-ax-b=0にする。この式に線分の各点のx,yを入れてみればよい。もし0になったらその点は既に直線にのっているということだ。交差というか接している状態だといえるだろう。大体の場合0よりも大きいか、0よりも小さいという結果になるだろう。0よりも大きければ、その点は直線よりも上にあるということだ。小さければその点は直線よりも下にあるということだ。要するに線分の端点である2点を上記式に当てはめたときの結果が、一方がマイナスで一方がプラスであれば交差するといえるわけだ。2つの結果を掛け合わせて、その結果がマイナスであれば一方のみがマイナスであったとことになる。これと同様にもう一方の線分と直線に対してもチェックして、両方とも結果がマイナスであれば、この線分と線分は交差していることになる。

javascriptでやるとこうなる。

var ax = 3, ay = 10, bx = 10, by = 3, cx = 3, cy = 3, dx = 10, dy = 10;

function lineCheck(ax,ay,bx,by,cx,cy){
  return   (by-ay)/(bx-ax)*cx+(ay-(by-ay)/(bx-ax)*ax)-cy;
} 

function lineCrossCheck(ax,ay,bx,by,cx,cy,dx,dy){
    var a = lineCheck(ax,ay,bx,by,cx,cy);
    var b = lineCheck(ax,ay,bx,by,dx,dy);
    var c = lineCheck(cx,cy,dx,dy,ax,ay);
    var d = lineCheck(cx,cy,dx,dy,bx,by);
    if(a*b<0 && c*d<0) return true;
    else return false;
}

document.write(lineCrossCheck(ax,ay,bx,by,cx,cy,dx,dy));

trueなので交差している。 そういえば、これだとx=5といったxが一定の直線との交差判定をしようとするとエラーになる。式のbx-axの部分が両方とも同じ値になるため0になるからだ。0で割るとjavascriptは結果がinfinityになるようなので、infinity様に何を足そうが引こうがきっと答えはinfinityになるのだろう。よって修正版をつくる。
ffunction lineCheck(ax,ay,bx,by,cx,cy){
 if(ax==bx){
  return cx - ax;
 }else{
  return (by-ay)/(bx-ax)*cx+(ay-(by-ay)/(bx-ax)*ax)-cy;
 }
}

これでどうだろう。

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

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

ある長方形(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だから、内側にある。

2011年9月5日月曜日

ベクトルの外積

ベクトルの外積は便利だ。ベクトルAとベクトルBの外積を求めたときに値がマイナスであれば、ベクトルBはベクトルAの右側にいるということが分かる。

試してみよう。

ベクトルA(6,6)、ベクトルB(6,0)としよう。
外積は下記の式になる。

Ax * By - Bx * Ay

よって、6*0-6*6 = -36 となる。
確かにマイナスである。

それでは、ベクトルA(6,0)、ベクトルB(6,6)としてみよう。
6*6-6*0 = 36 となる。
確かにプラスである。

ベクトルにはもう一つの成立する式がある。
|A| * |B| * sinθ

ベクトルA(6,0)、ベクトルB(6,6)だとすると、
6 * 6ルート2 *sin(45度)になるはずなので、javascriptだと下記になる。

document.write(6*6*Math.sqrt(2)*Math.sin(45*Math.PI/180));



確かに36で一致する。

cosθの値をグラフにしてみる

0度〜360度のcosθの値をグラフに出してみよう。HTML canvasを使おう。




一番上が1を表している。真ん中が0で、一番下が-1である。一番左が0を表していて縦の目盛線は、45ずつに引いている つまり、0度はcosは1。それから角度が拡大するにつれてcosは徐々に小さくなっていき、90度だとcosは0になる。90度を超えるとマイナス数値になり、180度でcosは−1になる。180度を超えると逆に大きくなり、270度で0に戻る。270度を超えるとプラス数値になり、360度で1に戻る。

<canvas id="cosCanvas" width="365" height="110"></canvas>
<script type="text/javascript">
var cosCanvas = document.getElementById("cosCanvas");
var COSC = cosCanvas.getContext("2d");
var CW = cosCanvas.width, CH = cosCanvas.height;

var cos = 0;

for(var deg=0;deg<361;deg++){
    cos = Math.cos(deg*Math.PI/180);
    COSC.beginPath();
    COSC.fillStyle = '#ff5500';
    COSC.arc(deg,CH/2-cos*50, 1, 0, 360,false);
    COSC.fill();
}

COSC.beginPath();
COSC.strokeStyle = '#666666';
COSC.moveTo(0,CH/2); 
COSC.lineTo(CW,CH/2); 
COSC.closePath();
COSC.stroke();

for(var i=0;i<361;i+=45){
    COSC.beginPath();
    COSC.strokeStyle = '#666666';
    COSC.moveTo(i,0); 
    COSC.lineTo(i,CH); 
    COSC.closePath();
    COSC.stroke();
}
</script>

ベクトルの内積の研究(1)

ベクトルの内積を研究する。

まずV,Uをそれぞれ、(3,5)、(6,3)としよう。
ベクトルの内積は下記のようになるものをいうらしい。

V●U = Vx * Ux + Vy * Uy

よって、内積は、3*6+5*3=となる。

内積ではもう一つ成立する式があるらしい。
V●U = |V|*|U|*cosθ

ベクトルの大きさは、三平方の定理で求められるので、下記のようになる。
|V| = 3^2+5^2の平方根 =
|U| = 6^2+3^2の平方根 =

よって、cosθの値が求められる。javascriptでやると下記のようになる。

var vx = 3, vy = 5;
var ux = 6, uy = 3;
var VU = vx*ux+vy*uy;
var valV = Math.sqrt(3*3+5*5);
var valU = Math.sqrt(6*6+3*3);
var cos = VU / valV / valU;
document.write(cos); 

 となる。

javascriptのMath.acos(cos)という関数は、cosの値を入れると角度を返してくれるようなのでやってみよう。

var rad = Math.acos(cos);
document.write(rad);



これはラジアンだが、360 度表記にすると、度ということだ。

これが合っているかをatan2関数を使って確認してみよう。

var radV = Math.atan2(vy, vx);
var radU = Math.atan2(uy,ux);
document.write(radV - radU);



おお合っている。

しかし、内積が便利に使えるシーンがまだよく分からない。atan2関数があれば不要だったりするのかのう。

2011年9月4日日曜日

Javascript Math.sin(rad) サインを求める

Math.sin(rad)でサインを求められる。引数のradはラジアン。ラジアンがよく分からない。

コンピュータゲームの物理という私のバイブルによると、ラジアンは角度を表す方法の1つのようだ。我々は360度で一周する方法をいつも使っているが、この360という中途半端な数字は、そもそも1年が360日だと思われていた頃の名残であること以外に理由はないそうだ。プログラム等で計算する場合もっと使い易い角度表記がないものかと、考えられたのがラジアンであるということだ。

ラジアンは、半径1の円を基準にした角度表記であるそうだ。ラジアンは、半径1の場合に角度がθだった場合の円周の長さのことである。つまり、角度θを半径1の場合の円周の長さで表すのがラジアンである。ちなみに、π(約3.14)は円周の長さが直径の何倍になるかを表した数字である。例えば半径1であれば、直径は2なので円周は、2π(約6.28)である。

つまり、360度をラジアンで表すと、2πということである。180度ならばπである。1度であれば、π/180ということだ。

ラジアンのすごいところは、360度表記と比べて円周の長さという実際の値に対応しているところと、長さと角度が完全に完全に一対一になっているところだそうだ。あんまりすごさが分からないが、確かに360度の360という数字自体には何の意味もないことはよく分かった。コンピュータがラジアンを使いたくなる気持ちも分かる。

さてこれでラジアンが分かったので、最初のMath.sin関数をみると、引数がラジアンなので、Math.sin(30度)ではいけない。これをラジアンに変えて引数に投入するので、Math.sin(30*Math.PI/180)となる。

Javascript Math.PI 円周率を求める関数

document.write(Math.PI);

Javascript Math.atan2() X軸からポイントまでの角度を取得

Math.atan2(y, x)

http://www.ajaxtower.jp/js/math_class/index15.html
ここの説明が分かり易そうだ。
atan2関数は座標の逆正接(アークタンジェント)を計算して返します。引数に指定した原点と座標(x, y)、そして座標からX座標へ降ろした点の3点からなる三角形を対象として逆正接(アークタンジェント)を計算します。引数がY座標からとなっていることに注意して下さい。

例えば座標(1, 1)とした場合、角度は45度になりタンジェントはtan(45度) = 1 / 1 = 1となります。atan2関数はタンジェントの結果が1となるような角度を取得するために、タンジェントの結果ではなく座標を指定します。つまりこの関数は座標を指定することで、原点からその座標に引いた直線のX軸からの角度を取得することができます。

ちょっと試してみよう。

var x = 10, y = 10;
document.write(Math.atan2(y,x));



結果はラジアンなので、360度表記に直してみよう。
ラジアンπが180度なので、ラジアンをπで割って180で書ければいいだろう。

var x = 10, y = 10, rad, deg;
rad = Math.atan2(y,x);
deg = rad/Math.PI*180;
document.write(deg);



原点を0,0とすると、x,yが10,10なので、直角二等辺三角形になるということだな。

では、x=1,y=ルート3にしてみよう。

var x = 1, y = Math.sqrt(3), rad, deg;
rad = Math.atan2(y,x);
deg = rad/Math.PI*180;
document.write(deg);



やはり60度だな。HTML5 Canvasの場合は、左上を原点とするから、そこだけ気をつけないといけないな。