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;
 }
}

これでどうだろう。

0 件のコメント:

コメントを投稿