交差判定アルゴリズム

多分>>19や>>24と同じなんだろうけど、
座標をパラメーター表示するので考えてみた。
(x1,y1)と(x2,y2)の線分と(x3,y3)と(x4,y4)の線分は、
パラメーターsとtで表すと、それぞれ
    (x1+(x2-x1)s,y1+(y2-y1)s)
と
    (x3+(x4-x3)t,y3+(y4-y3)t)
となる。ただし、0≦s≦1、0≦t≦1。

これらの交点は、
    x1+(x2-x1)s=x3+(x4-x3)t
    y1+(y2-y1)s=y3+(y4-y3)t
となり、s、tでまとめると、
    (x2-x1)s-(x4-x3)t=x3-x1
    (y2-y1)s-(y4-y3)t=y3-y1
となる。

これをsとtについて解くことにする。
    D=-(x2-x1)(y4-y3)+(x4-x3)(y2-y1)
とすると、D≠0のとき線分を通る直線が交差し、
    s=(-(x3-x1)(y4-y3)+(x4-x3)(y3-y1))/D
    t=((x2-x1)(y3-y1)-(x3-x1)(y2-y1))/D
となる。

このsとtがともに0以上1以下の場合に線分が交差する。

ちなみに、最初の(x1+(x2-x1)s,y1+(y2-y1)s)に代入すれば交点をえる。

おそらく、行列式でもっときれいに表すことができ、
n次元に拡張するのでも同じとなる。