はじめに
数年に一度必要となるたびに調べて計算していたが、疲れてきたのでここにメモを残す.
問題は、「平面上に与えられた二直線 AB、CD の交点を求めよ」である.
ベクトルを用いた問題の書き換え
上の問題は、ベクトルを用いて以下のように書き直すことができる:
$P = A + s \overrightarrow{AB} = C + t \overrightarrow{CD}$
を満たす定数 s、または t を求めよ.
この P が元の問題で求めるべき交点である.
補助線を引き、問題をさらに書き換える
\begin{align*}
E = A + \overrightarrow{CD} \\
F = B + \overrightarrow{CD}
\end{align*}
として、以下のように補助線を引く:
こうすると、問題は次のようになる:
「平行四辺形 AEDC、AEFB の高さの比 s を求めよ」
これは辺 AE を共有しているからさらに、
「平行四辺形 AEDC、AEFB の面積の比 s = AEDC / AEFB を求めよ」
と書ける.
平行四辺形の(符号付き)面積はベクトルの外積によって求められる.
この図で CD が A よりも右にある場合「高さの比」、「面積の比」という表現は正確でないが、符号付き面積の比を用いれば、CD と A の位置関係によらず交点を求めることができるのだし、イメージとしてはこれで十分ということで許して欲しい.
実際に交点を求める
交点は s が求まれば、「ベクトルを用いた問題の書き換え」に書いた式で導ける.
\begin{align*}
& s = \frac {\text{平行四辺形 AEDC の符号付き面積}} {\text{平行四辺形 AEFB の符号付き面積}} \\
& \text{平行四辺形 AEDC の符号付き面積} = \overrightarrow{AC} \times \overrightarrow{CD} \\
& \text{平行四辺形 AEFB の符号付き面積} = \overrightarrow{AB} \times \overrightarrow{CD}
\end{align*}
ここで、ベクトルの外積は
\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 関数である.
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>