今回は、交差の判定にベクトルを使います。

図１
上の図の、赤と青の線分の交差条件について考えてみましょう。
図のように直線のうち片方をO-Pとして、Oを原点(0,0)、Pを(x,y)と取るようにし、
もう一方の直線をA(a,b)-B(c,d)とします。
O->A,O->Bをそれぞれ

O->Pを

とします。

上の図では、2ベクトルが独立な為、変数s,tを用いて
(式１)
と表せます。座標成分で表示すれば
(式２)
となります。

ここまではいいですか？

で、Pが図における斜線部にある時に、２つの線分が交差することになるのが分かると思います。
その斜線部にPが入る条件をs,tで表すと
(式３)
という条件式が出てきます。

条件にはsとtが関わってくるので、この２つをどうにか数式で表しましょう。
そこで、(式２)のxに関する部分をsについて整理します。すると
(式４)
このようにsが表せます。これを同じく(式２)のyに関する式にぶち込みます。
(式５)
つまり、
(式６)
このように表せます。
同様に、sについても
(式７)
に変形できます。

ここまで来ればだいたい想像は出来てくるのではないかと思います。
でも何だかごちゃごちゃしてますね。ちょっと変数の置き換えをしましょう。
(式８)
これで、(式３)の１つ目の条件は
(式９)
おぉ、スッキリしましたね。
同じようにすると(式３)の２つ目はこうなります。
(式10)

というわけで、(式９)と(式10)をチェックすればいいわけです。が、
残念ながら数学はそんなに甘くありません。
というのは、分母、すなわち(式８)に置けるDが０の場合はこの式では定義できません。
(式９)では０で割ることになってしまうからです。

(図２)
実は、調べてみると分かるのですが、このDが０になるのは
図２のように点Aが直線ABの上に乗っているときなのです。
ただし、「"直線"の上」なので、安直にすぐtrueを返すわけにも行きません。

そこで、点Oから見たときのベクトルの内積を使います。
(式11)
もしこれが成り立つならば、∠AOBの角度は90度以上ということになります。
いまOはAB上にあることが保証されているので、取りうる角度は0か180。
つまり、これが負ならば180度と言えるわけです。

この判定は∠AOBだけでなく、∠APBと∠OAP(もしくは∠OBP)に対してもやらなければなりません。
でないと、

• ・Oが線分の外でPが線分に乗っているとき
• ・線分OPの中に線分ABがまるまる乗っているとき

さぁやってまいりました、いよいよソースです。
C言語の関数でお送り致します。(コメントはC++スタイルですけど)

//	線分の当たり判定 (x1,y1)-(x2,y2) × (x3,y3)-(x4,y4)
int CheckLineCrossing(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
	int S,T,D;	//	一時変数を宣言

	//	分母を先に計算。計算量を減らすため、分子は後で行う。
	D = (x3-x1) * (y4-y1) - (y3-y1) * (x4-x1);
	
	//	D の符号に応じて分岐
	if(D < 0){
		S = (y4-y1)*(x2-x1) - (x4-x1)*(y2-y1)
		T = (x3-x1)*(y2-y1) - (y3-y1)*(x2-x1)
		
		return S <= 0 && T <= 0 && (S+T)/D >= 1 ;
	}
	else if(D > 0){
		S = (y4-y1)*(x2-x1) - (x4-x1)*(y2-y1)
		T = (x3-x1)*(y2-y1) - (y3-y1)*(x2-x1)
		
		return S >= 0 && T >= 0 && (S+T)/D >= 1 ;
	}
	
	//	D = 0 の時には、点が線分の上かどうかを判定する。
	return (x3-x1)*(x4-x1)+(y3-y1)*(y4-y1) <= 0
	    || (x3-x2)*(x4-x2)+(y3-y2)*(y4-y2) <= 0
	    || (x1-x3)*(x2-x3)+(y1-y3)*(y2-y3) <= 0;
}

余談1
試しに動作速度を検証してみたところ、一千万回ループで9.7秒。
一方、矩形の当たり判定を同じように試すと一千万回で9.0秒。
あれ？思ったより速いぞ？

余談2
今回使用したベクトルの考え方を使うと、三角形と点の当たり判定も可能です。
三角形と点が出来るということは、何度も判定を行うことで
多角形×多角形の判定もある程度出来ます。不完全ですがね。