二直線の交点を求める

# 前書き
平面上の直線$AB,CD$について、点$A, B, C, D$の座標から交点$P$の座標を求めます。
求め方が分かりしだい関数をJavaScriptで実装します（本来の目的）。

計算方法を調べる過程で数式やプログラムに脳が拒否反応を起こしてしまったため、必要な中学・高校の学習内容を記憶の中から引っ張り出しながら解いていきます。
「さすがにこのくらい分かるわ！」って部分は大いに飛ばしていただいてかまいません。

高校数学が（中学数学も）わりと怪しいので、間違いや不足などあればご指摘ください。
それとQiitaについても初心者なので、粗相などございましたら以下略。
ついでにJavaScriptも初心者なので(ry

# 本題
以下、点$A$の$x$座標、$y$座標をそれぞれ$x_A$、$y_A$と置きます（ほかの点も同様）。
### まず直線の方程式を思い出す
二点の座標から直線を表す方程式です。

```math
\displaylines{
y-y_1=\frac{y_2-y_1}{x_2-x_1}(x-x_1) \\
(y-y_1)(x_2-x_1)=(x-x_1)(y_2-y_1)
}
```

一行目の式が高校数学の教科書でよく出てくる直線の方程式ですね（多分）。
今回は$x_2-x_1$が$0$でも問題ない二行目の式に変形しました。
添え字の$1,2$をそれぞれ$A,B$、$C,D$に置き換えることで直線$AB$、$CD$を表す方程式ができます。
```math
\displaylines{
(y-y_A)(x_B-x_A)=(x-x_A)(y_B-y_A) \\
(y-y_C)(x_D-x_C)=(x-x_C)(y_D-y_C)
}
```

### 連立方程式を立てる
さて、直線$AB,CD$を方程式に表すことに成功したので、あとは交点$P$を求めるだけです。
やることは単純。

交点$P(x_P,y_P)$は直線$AB$上の点であり、直線$CD$上の点でもあります。
つまり、直線$AB$、$CD$それぞれの方程式の$x$にとある数$α$を代入すると、どちらの$y$もある数$β$に定まるようなただ一つのペア$(α,β)$、それこそが点$P(x_P,y_P)$なのです。

これは二つの方程式が同じ解$(x_P,y_P)$を持っていると言えます。
連立方程式を立てて共通する解を探しましょう。
```math
\left\{
\begin{array}{l}
(y-y_A)(x_B-x_A)=(x-x_A)(y_B-y_A) \\
(y-y_C)(x_D-x_C)=(x-x_C)(y_D-y_C) \tag{2}
\end{array}
\right.
```
$x_A$～$x_D$、$y_A$～$y_D$は全部定数なので、結局のところただの連立二元一次方程式を解けばそれで終わりです。

### 連立方程式の解き方を考える
もうちっとだけ続くんじゃ。
```math
\left\{
\begin{array}{l}
a_1x+b_1y+c_1=0 \\
a_2x+b_2y+c_2=0\tag{3}
\end{array}
\right.
```
$(2)$式は定数がごちゃごちゃしていて面倒なので、シンプルな連立方程式を用意しました。
手計算するならいろいろ工夫のしようもありますが、どうせ自分で計算するわけではないので機械的に解きます。

まずは$y$を消去して$x$の値を求めましょう。
$y$の係数の逆数をそれぞれの式の全体にかけます。
```math
\left\{
\begin{array}{l}
\frac{a_1}{b_1}x+y+\frac{c_1}{b_1}=0 \\
\frac{a_2}{b_2}x+y+\frac{c_2}{b_2}=0
\end{array}
\right.
```
上の式から下の式を引きます。
```math
\displaylines{
\begin{align}
&(\frac{a_1}{b_1}x-\frac{a_2}{b_2}x)+(y-y)+(\frac{c_1}{b_1}-\frac{c_2}{b_2})=0 \\
\Longleftrightarrow &\quad (\frac{a_1}{b_1}-\frac{a_2}{b_2})x+(\frac{c_1}{b_1}-\frac{c_2}{b_2})=0 \\
\Longleftrightarrow &\quad \frac{a_1b_2-a_2b_1}{b_1b_2}x+\frac{c_1b_2-c_2b_1}{b_1b_2}=0
\end{align}
}
```
定数項を移項して$x$の係数を$1$にします。
```math
\displaylines{
\begin{align}
&\frac{a_1b_2-a_2b_1}{b_1b_2}x=-\frac{c_1b_2-c_2b_1}{b_1b_2} \\
\Longleftrightarrow &\quad x=-\frac{c_1b_2-c_2b_1}{b_1b_2}×\frac{b_1b_2}{a_1b_2-a_2b_1} \\
\Longleftrightarrow &\quad x=\frac{c_2b_1-c_1b_2}{a_1b_2-a_2b_1} \\
\end{align}
}
```
$x$の値が求まりました！
$a$と$b$を入れ替えてやると同様に$y$の値も求める事ができます。
```math
\displaylines{
y=\frac{c_2a_1-c_1a_2}{b_1a_2-b_2a_1}
}
```
さて、あとは$x_A$～$x_D$、$y_A$～$y_D$から$a_1,a_2,b_1,b_2,c_1,c_2$を求めるのみです。
$(2)$式を$(3)$式に近づけるように変形します。
```math
\displaylines{
\begin{align}
&\left\{
\begin{array}{l}
(y-y_A)(x_B-x_A)-(x-x_A)(y_B-y_A)=0 \\
(y-y_C)(x_D-x_C)-(x-x_C)(y_D-y_C)=0
\end{array}
\right. \\
&\left\{
\begin{array}{l}
\Bigl(y(x_B-x_A)-y_A(x_B-x_A)\Bigr)-\Bigl(x(y_B-y_A)-x_A(y_B-y_A)\Bigr)=0 \\
\Bigl(y(x_D-x_C)-y_C(x_D-x_C)\Bigr)-\Bigl(x(y_D-y_C)-x_C(y_D-y_C)\Bigr)=0
\end{array}
\right. \\
&\left\{
\begin{array}{l}
(y_A-y_B)x+(x_B-x_A)y+\Bigl(x_A(y_B-y_A)-y_A(x_B-x_A)\Bigr)=0 \\
(y_C-y_D)x+(x_D-x_C)y+\Bigl(x_C(y_D-y_C)-y_C(x_D-x_C)\Bigr)=0
\end{array}
\right.
\end{align}
}
```
両式とも$ax+by+c=0$の形になりました。

最終的に点$A,B,C,D$の座標から交点$P$の座標を求めるのに必要な式は以下の通り。
```math
\displaylines{
a_1=y_A-y_B\qquad a_2=y_C-y_D \\
b_1=x_B-x_A\qquad b_2=x_D-x_C \\
c_1=x_A(y_B-y_A)-y_A(x_B-x_A) \\
c_2=x_C(y_D-y_C)-y_C(x_D-x_C) \\
x=\frac{c_2b_1-c_1b_2}{a_1b_2-a_2b_1} \\
y=\frac{c_2a_1-c_1a_2}{b_1a_2-b_2a_1}
}
```

### 実装する
本来の目的です。
実装だけできればよかったのに数式まで理解しようとしたらすごい遠回りをしてしまった。
まあ急がば回れとも言うしね。

とはいえ、必要な数式はすべて立てることができたので、あとはそのまま実装するだけです。
**※以下のコードはまだ完全な実装じゃないです**

```js
function getIntersection(aX, aY, bX, bY, cX, cY, dX, dY) {
    let a1 = aY - bY,
        a2 = cY - dY,
        b1 = bX - aX,
        b2 = dX - cX,
        c1 = aX * (bY - aY) - aY * (bX - aX),
        c2 = cX * (dY - cY) - cY * (dX - cX);

    let result = {};
    result.x = (c2 * b1 - c1 * b2) / (a1 * b2 - a2 * b1);
    result.y = (c2 * a1 - c1 * a2) / (b1 * a2 - b2 * a1);
    return result;
}
```

### 試しに解いてみる

[GeoGebra](https://www.geogebra.org/graphing)でいくつかグラフを作ってみて、実際に正しい値になるか確かめてみます。

##### 問１
$A(10,6),B(4,2),C(-6,6),D(-4,2)$
答え$P=(-2,-2)$
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/497128/79b202d3-d2c3-01d0-5318-0412fc8cbb10.png)
【実行結果】
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/497128/aec49fa3-4202-e091-b1b3-11f1cdd9ea88.png)
よさそう。

##### 問２
$A(2,8),B(2,4),C(-6,2),D(-2,2)$
答え$P=(2,2)$
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/497128/07e66432-6c13-17e9-0a91-8de51cc9ab4a.png)
【実行結果】
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/497128/08d9214c-28b2-635b-05d3-3f7f9c436ebc.png)
$x$軸・$y$軸に平行な線でも問題はなさそうですね。

##### 問３
$A(-2,8),B(2,4),C(-2,4),D(2,0)$
$AB$と$CD$は平行なので交点はできない
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/497128/695726e5-85c5-a13b-08cf-02ae9e38eb5b.png)
【実行結果】
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/497128/b6a2c78f-3032-8cdd-0be7-976868b8dc80.png)
𝙄𝙣𝙛𝙞𝙣𝙞𝙩𝙮.

##### 問４
$A(-6,2),B(-2,2),C(2,2),D(6,2)$
$AB$と$CD$は重なり合っているので交点は無限にできる
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/497128/d16f16c5-86a6-9b59-f510-5b2605c26047.png)
【実行結果】
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/497128/b05812ad-7424-3d32-55f9-d4c6e13c2634.png)
𝑵𝒐𝒕 𝒂 𝑵𝒖𝒎𝒃𝒆𝒓.

### 返り値の考察をする
##### 平行な二直線について
Chromeのデベロッパーツールにて、ブレークポイントを設定してgetIntersection関数内の各変数の値を確認してみます。
まずは結果が **(Infinity, Infinity)** になった問３から見てみましょ。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/497128/e0c1d258-23a9-dfba-307c-f56999dfa582.png)
$x$の分子と分母をそれぞれ計算してみると、
```math
\displaylines{
c_2b_1-c_1b_2=-8×4-(-24)×4=64 \\
a_1b_2-a_2b_1=4×4-4×4=0
}
```
$x=\frac{64}{0}$になったみたい。
$y$の式は$a$と$b$を入れ替えただけなので$y$も同じく$\frac{64}{0}$になります。省略。
JavaScriptでは正の数をゼロで割る[^1]とInfinityが返ってくるので、結果的に返り値は(Infinity, Infinity)となります。

また、JavaScriptでは負の数をゼロで割る[^2]と-Infinityが返ってきます。
$a_2$と$b_2$がマイナスになるように仕組んでやれば、返り値を(-Infinity,-Infinity)にすることもできますね。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/497128/151a456d-dee7-bdd9-0809-16fa525064f6.png)

##### 重なった二直線について
同じく **(NaN, NaN)** が返ってきた問４についても確認。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/497128/57885b96-c83e-e081-05dc-f194d4e473bc.png)
$x$の分子と分母をそれぞれ計算すると、
```math
\displaylines{
c_2b_1-c_1b_2=-8×4-(-8)×4=0 \\
a_1b_2-a_2b_1=0×4-0×4=0
}
```
$x=\frac{0}{0}$で、ゼロのゼロ除算。
$y$の分子と分母も両方$0$となります。
```math
\displaylines{
c_2a_1-c_1a_2=-8×0-(-8)×0=0 \\
b_1a_2-b_2a_1=4×0-4×0=0
}
```
JavaScriptではゼロをゼロで割るとNaNが返ってくるので、結果的に返り値は(NaN, NaN)となります。

### 例外も投げるようにする
𝙄𝙣𝙛𝙞𝙣𝙞𝙩𝙮だろうと𝑵𝒂𝑵だろうと、結局交点を求められないような直線を与えられた場合、$x$や$y$を求める式の分母がゼロになってしまっているわけです。
$a_1b_2-a_2b_1$もしくは$b_1a_2-b_2a_1$が$0$の場合に例外を投げれば解決！

文字の順番が前後していてわかりにくいですが、上二つの式は$a_1b_2=a_2b_1$のときどちらも$0$になります。
ということで、条件文$a_1b_2=a_2b_1$とthrow文を先ほどのコードに付け加えて完成です。

```js
function getIntersection(xA, yA, xB, yB, xC, yC, xD, yD) {
    let a1 = yA - yB,
        a2 = yC - yD,
        b1 = xB - xA,
        b2 = xD - xC,
        c1 = xA * (yB - yA) - yA * (xB - xA),
        c2 = xC * (yD - yC) - yC * (xD - xC);

    if (a1 * b2 == a2 * b1)
        throw new Error("Invalid Coordinates");

    let result = {};
    result.x = (c2 * b1 - c1 * b2) / (a1 * b2 - a2 * b1);
    result.y = (c2 * a1 - c1 * a2) / (b1 * a2 - b2 * a1);
    return result;
}
```

終わり！

[^1]:もしくは負の数をマイナスゼロで割る
[^2]:もしくは正の数をマイナスゼロで割る