２つの直線の交点 - melpon日記 - HaskellもC++もまともに扱えないへたれのページ

すごい基本的な部分なんですけど、ゼロ除算で失敗してしまったので……（;´Д｀）

$(x_1,y_1)$ と $(x_2,y_2)$ を結ぶ直線を $L_1$ とし、 $(x_3,y_3)$ と $(x_4,y_4)$ を結ぶ直線を $L_2$ としたときに、この $L_1,L_2$ の交点 $(X,Y)$ はどうなるかを考えてみる。

$L_1$ と $L_2$ を $y=ax+b$ とし、それぞれ $(x_1,y_1)$ と $(x_2,y_2)$ 、 $(x_3,y_3)$ と $(x_4,y_4)$ で計算すると、
$\begin{array}L_1&=&\frac{y_1-y_2}{x_1-x_2}x+\frac{x_1~y_2-x_2~y_1}{x_1-x_2}(x_1\neq~x_2)\\L_2&=&\frac{y_3-y_4}{x_3-x_4}x+\frac{x_3~y_4-x_4~y_3}{x_3-x_4}(x_3\neq~x_4)\end{array}$
となる。

それぞれ、
$\begin{array}A&=&\frac{y_1-y_2}{x_1-x_2}\\B&=&\frac{x_1~y_2-x_2~y_1}{x_1-x_2}\\C&=&\frac{y_3-y_4}{x_3-x_4}\\D&=&\frac{x_3~y_4-x_4~y_3}{x_3-x_4}\end{array}$
とすれば、 $L_1,L_2$ の交点 $(X,Y)$ は、
$\begin{array}\array{X&=&\frac{D-B}{A-C}\\Y&=&\frac{AD-BC}{A-C}}&{$\array{x_1\neq~x_2\\x_3\neq~x_4\\A\neq~C}$}\end{array}$
となり、 $A,B,C,D$ を展開し、再計算すると、
$\begin{array}\array{X&=&\frac{(x_1-x_2)(x_3~y_4-x_4~y_3)-(x_3-x_4)(x_1~y_2-x_2~y_1)}{(x_3-x_4)(y_1-y_2)-(x_1-x_2)(y_3-y_4)}\\Y&=&\frac{(y_1-y_2)(x_3~y_4-x_4~y_3)-(y_3-y_4)(x_1~y_2-x_2~y_1)}{(x_3-x_4)(y_1-y_2)-(x_1-x_2)(y_3-y_4)}}&{$\array{x_1\neq~x_2\\x_3\neq~x_4\\~\frac{y_1-y_2}{x_1-x_2}\neq\frac{y_3-y_4}{x_3-x_4}}$}\end{array}$
となる。

また、 $(x_1=x_2\wedge~x_3=x_4)\vee~(x_1\neq~x_2\wedge~x_3\neq~x_4\wedge~A=C)$ の場合は、 $L_1\parallel~L_2$ になり、１点だけが交差するということはないので、解なし。
$x_1\neq~x_2\wedge~x_3=x_4$ の場合は、 $X=x_3$ となるので、
$\begin{array}X&=&~&x_3&\\Y&=&\frac{y_1-y_2}{x_1-x_2}~&x_3&+\frac{x_1~y_2-x_2~y_1}{x_1-x_2}\end{array}$
となる。同様に、 $x_1=x_2\wedge~x_3\neq~x_4$ の場合は、
$\begin{array}X&=&~&x_1&\\Y&=&\frac{y_3-y_4}{x_3-x_4}~&x_1&+\frac{x_3~y_4-x_4~y_3}{x_3-x_4}\end{array}$
となる。