ベクトルの外積を用いて二直線の交点を求める

# はじめに

数年に一度必要となるたびに調べて計算していたが、疲れてきたのでここにメモを残す.
問題は、「平面上に与えられた二直線 AB、CD の交点を求めよ」である.

![00_二直線の交点.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2329888/7e46047e-31ca-de8e-9ffe-a4d3f2f73b4d.png)

# ベクトルを用いた問題の書き換え

上の問題は、ベクトルを用いて以下のように書き直すことができる:
$P = A + s \overrightarrow{AB} = C + t \overrightarrow{CD}$
を満たす定数 s、または t を求めよ.

この P が元の問題で求めるべき交点である.

# 補助線を引き、問題をさらに書き換える

```math
\begin{align*}
E = A + \overrightarrow{CD} \\
F = B + \overrightarrow{CD}
\end{align*}
```

として、以下のように補助線を引く:

![02_ふたつの平行四辺形.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2329888/877b0dd0-e0ea-0629-11e8-5d2f1a009457.png)

こうすると、問題は次のようになる:
「平行四辺形 AEDC、AEFB の高さの比 s を求めよ」

これは辺 AE を共有しているからさらに、
「平行四辺形 AEDC、AEFB の面積の比 s = AEDC / AEFB を求めよ」
と書ける.

平行四辺形の(符号付き)面積はベクトルの外積によって求められる.
この図で CD が A よりも右にある場合「高さの比」、「面積の比」という表現は正確でないが、符号付き面積の比を用いれば、CD と A の位置関係によらず交点を求めることができるのだし、イメージとしてはこれで十分ということで許して欲しい.

# 実際に交点を求める

交点は s が求まれば、「ベクトルを用いた問題の書き換え」に書いた式で導ける.

```math
\begin{align*}
& s = \frac {\text{平行四辺形 AEDC の符号付き面積}} {\text{平行四辺形 AEFB の符号付き面積}} \\
& \text{平行四辺形 AEDC の符号付き面積} = \overrightarrow{AC} \times \overrightarrow{CD} \\
& \text{平行四辺形 AEFB の符号付き面積} = \overrightarrow{AB} \times \overrightarrow{CD}
\end{align*}
```

ここで、ベクトルの外積は

```math
\begin{align*}
\textbf {a} &= (x_0,\ y_0) \\
\textbf {b} &= (x_1,\ y_1) \\
\textbf {a} \times \textbf {b} &= x_0 \; y_1 - y_0 \; x_1
\end{align*}
```
である.

# 「線分」の交点

ここまでで、二「直線」の交点を計算できるようになったが、「線分」の交点が欲しい場合もたまにある.
もっともこれは、s と同様にして t を求め、両者が区間 [0..1] に収まっているかどうかで判断できる.
両者が区間 [0..1] に収まっていれば、交点は線分上に存在し、
そうでなければ、交点はどちらかの線分の外に存在するということが分かる.

# デモ

HTML Canvas によるインタラクティブなデモを以下に示す.
二直線を求める部分は intersection 関数である.

```html:demo.html
<!DOCTYPE html>
<html lang='ja'>
<head>
  <meta charset='UTF-8'>
  <title>Canvas Demo</title>
  <style>
    canvas {
      border: 1px solid black;
    }
  </style>
  <script type='text/javascript'>
window.onload = function () {
  class Point {
    constructor(x, y) { this.x = x; this.y = y; }
    vectorTo(p) {
      const dx = p.x - this.x;
      const dy = p.y - this.y;
      return new Vector(dx, dy);
    }
    add(v) {// translate の方がよいだろうか？
      return new Point(this.x + v.x, this.y + v.y);
    }
  }// class Point
  class Vector {
    constructor(x, y) { this.x = x; this.y = y; }
    norm() {
      return Math.sqrt(this.x*this.x + this.y*this.y);
    }
    normalise() {
      const norm = this.norm();
      return new Vector(this.x / norm, this.y / norm);
    }
    scale(s) {
      return new Vector(this.x * s, this.y * s);
    }
    add(v) {
      return new Vector(this.x + v.x, this.y + v.y);
    }
    crossProduct(v) {
      return this.x*v.y - this.y*v.x;
    }
  }// class Vector

  function drawCross(ctx, x, y, size, lineWidth, style) {
    const halfSize = size / 2;
    const sqrt2 = Math.sqrt(2);
    const offset = halfSize / sqrt2;
    ctx.save();
    ctx.lineWidth = lineWidth;
    ctx.strokeStyle = style;
    ctx.beginPath();
    ctx.moveTo(x - offset, y - offset);
    ctx.lineTo(x + offset, y + offset);
    ctx.moveTo(x + offset, y - offset);
    ctx.lineTo(x - offset, y + offset);
    ctx.stroke();
    ctx.restore();
  }

  function drawSquare(ctx, x, y, size, lineWidth, style) {
    const halfSize = size / 2;
    const sqrt2 = Math.sqrt(2);
    const offset = halfSize / sqrt2;
    ctx.save();
    ctx.lineWidth = lineWidth;
    ctx.strokeStyle = style;
    ctx.beginPath();
    ctx.moveTo(x - offset, y - offset);
    ctx.lineTo(x + offset, y - offset);
    ctx.lineTo(x + offset, y + offset);
    ctx.lineTo(x - offset, y + offset);
    ctx.closePath();
    ctx.stroke();
    ctx.restore();
  }

  function intersection(a, b, c, d) {
    // 直線 a-b、c-d の交点を求める
    const vab = a.vectorTo(b);
    const vac = a.vectorTo(c);
    const vcd = c.vectorTo(d);
    const s = vac.crossProduct(vcd) / vab.crossProduct(vcd);
    if(!isFinite(s)) {
      // s が有限の値でない <=> 分母が 0 であった <=> 二直線が平行
      // => 交点が0個、または無限個となるので null を返す
      return null;
    }
    return a.add(vab.scale(s));
  }

  const canvas = document.getElementById('main-canvas');
  const ctx = canvas.getContext('2d');
  const A = new Point( 50, 300);
  const B = new Point(500, 100);
  const C = new Point(150, 200);
  const D = new Point(350, 300);
  const crossSize = 10;
  let draggingPoint = null;

  function draw() {
    ctx.clearRect(0, 0, canvas.width, canvas.height);

    const ab = A.vectorTo(B).normalise().scale(20);
    const cd = C.vectorTo(D).normalise().scale(20);

    // 2本の線分を描画
    ctx.beginPath();
    ctx.moveTo(A.x, A.y);
    ctx.lineTo(B.x, B.y);
    ctx.moveTo(C.x, C.y);
    ctx.lineTo(D.x, D.y);
    ctx.stroke();

    // 各頂点のラベルを書き込む
    ctx.save();
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.font = '16px sanserif';
    const posA = A.add(ab.scale(-1));
    const posB = B.add(ab);
    const posC = C.add(cd.scale(-1));
    const posD = D.add(cd);
    ctx.fillText('A', posA.x, posA.y);
    ctx.fillText('B', posB.x, posB.y);
    ctx.fillText('C', posC.x, posC.y);
    ctx.fillText('D', posD.x, posD.y);
    ctx.restore();

    // 各頂点を装飾する
    drawCross(ctx, A.x, A.y, crossSize, 1, 'orange');
    drawCross(ctx, B.x, B.y, crossSize, 1, 'blue');
    drawCross(ctx, C.x, C.y, crossSize, 1, 'green');
    drawCross(ctx, D.x, D.y, crossSize, 1, 'purple');

    // 二直線の交点を示す
    const isc = intersection(A, B, C, D);
    if(isc !== null) {
      drawSquare(ctx, isc.x, isc.y, crossSize, 1, 'red');
    }
  }

  function getCrossContainsPoint(x, y) {
    for(let p of [A, B, C, D]) {
      if(Math.abs(x - p.x) < crossSize && Math.abs(y - p.y) < crossSize) {
        return p;
      }
    }
    return null;
  }

  canvas.addEventListener('mousedown', function (event) {
    const rect = canvas.getBoundingClientRect();
    const x = event.clientX - rect.left;
    const y = event.clientY - rect.top;
    draggingPoint = getCrossContainsPoint(x, y);
  });

  canvas.addEventListener('mousemove', function (event) {
    if (draggingPoint) {
      const rect = canvas.getBoundingClientRect();
      draggingPoint.x = event.clientX - rect.left;
      draggingPoint.y = event.clientY - rect.top;
      draw();
    }
  });

  canvas.addEventListener('mouseup', function () {
    draggingPoint = null;
  });

  canvas.addEventListener('mouseleave', function () {
    draggingPoint = null;
  });

  draw();
};
  </script>
</head>
<body>
  <div>
    <canvas id='main-canvas' width='1000' height='500'></canvas>
  </div>
</body>
</html>
```