線分交差判定

A(x1, y1), B(x2, y2), C(x3, y3), D(x4, y4)のとき、線分ABとCDが交差しているかを判定する。

A,Bを通る直線の方程式は

これだとx1=x2のときにｵﾜﾀなのでx1-x2をかけて、
(y1-y2)(x-x1)-(x1-x2)(y-y1)=0
ちなみにこの式のx,yに座標を代入して成り立つ場合は直線状にあることになるます。

交差するにはC,Dが直線ABを境に別々のところに居ればいいので、
先の式にCの座標,Dの座標を代入した式の積が正ではない⇒それぞれの式の符号が異なるかまたは0である
すなわち
{ ( y1 - y2 )( x3 - x1 ) - ( x1 - x2 )( y3 - y1 ) } { ( y1 - y2 )( x4 - x1 ) - ( x1 - x2 )( y4 - y1 ) } ≦ 0
同様に
{ ( y3 - y4 )( x1 - x3 ) - ( x3 - x4 )( y1 - y3 ) } { ( y3 - y4 )( x2 - x3 ) - ( x3 - x4 )( y2 - y3 ) } ≦ 0
この両方が成り立つとき、線分ABと線分BCは交わっている（もしくは接している）