平面における2直線の交点は、直線の方程式を連立して解くことができます。ただ、その場合は傾きによる場合分けをしなければなりません。ふたつの直線をベクトルとして外積で考えると、一般的に交点が導けます。本稿では、この外積から交点がどのようにして求められるか、そのサンプルコードをご紹介します。なお、数学的な解説は「平面上の2直線の交点を外積により求める」をお読みください。

01 2次元平面上のふたつの直線の交点を外積で求める

サンプルとしてつぎのようなコードを掲げました。ふたつの線分の両端をドラッグして、好きな位置に動かすことができます。すると、ふたつの直線の交点に小さな円の印が描かれます。その印は、線分が直接交わっているときはシアンで、そうでないときは赤く示されます。

下図001のふたつの線分ACとBDは、互いに点Pで交わります。このとき、APとCPの比は、三角形ABDとCBDの面積の比に等しくなります。

図001■線分はふたつの三角形の面積の比率で分けられる

三角形のふたつの辺をベクトルとすると、それらの外積の大きさは三角形の面積の2倍になります。ベクトルBDとABの外積はBD×ADで表され、つぎの式が成り立つのです。

△ABD = BD×AD / 2

また、三角形CBDについても同じです。

△CBD = BD×BC / 2

ただし、2次元平面のベクトルの外積は、計算の順序を変えると正負が逆になります。ふたつのベクトルの始点を揃えたとき、時計回り(右ネジ)の順序になるとき外積はプラス、そうでないときはマイナスです。前掲図001のふたつの三角形のベクトルの外積(BD×ADとBD×BC)は、ともに正数になります。

前述のとおり、ふたつの線分ACとBDの交点Pとしたとき、APとCPの比は三角形ABDとCBDの面積の比に等しくなります。そこで、ベクトルの外積を用いると、つぎの式が成り立ちます。ただし、BD×AB + BD×BC≠0とします。BD×AB + BD×BC = 0のときは、ふたつの線分は平行で交点がありません。

AP / AC = (BD×AB / 2) / {(BD×AB / 2) + (BD×BC / 2)} = BD×AB / (BD×AB + BD×BC)

したがって、点AとCの座標をそれぞれ(a_x, a_y)および(c_x, x_y)とし、ベクトルの外積から求めたAP / AC(= BD×AB / (BD×AB + BD×BC))の比率をkとすると、交点P(x, y)の座標はつぎのとおりです。

x = a_x + k×(c_x - a_x)
y = a_y + k×(c_y - a_y)

ここまでの計算を関数(getIntersection())に定めましょう。ふたつのベクトルの始点と終点を4つのPointオブジェクトで渡し、交点座標のPointオブジェクトをプロパティ(intersection)に納めたObjectインスタンスで返します。前掲図001と上記の式にもとづいて、コメントを添えました。なお、外積を求める関数(crossProduct2D())の中身は、この後ご説明します。

function getIntersection(from_0, to_0, from_1, to_1) {   var intersection = new createjs.Point();   // AC   var vector_0 = new createjs.Point(to_0.x - from_0.x, to_0.y - from_0.y);   // BD   var vector_1 = new createjs.Point(to_1.x - from_1.x, to_1.y - from_1.y);   // AB   var vector_2 = new createjs.Point(from_1.x - from_0.x, from_1.y - from_0.y);   // BC   var vector_3 = new createjs.Point(to_0.x - from_1.x, to_0.y - from_1.y);   // BD×AB   var area_0 = crossProduct2D(vector_1, vector_2);   // BD×BC   var area_1 = crossProduct2D(vector_1, vector_3);   // BD×AB + BD×BC   var area_total = area_0 + area_1;   if (Math.abs(area_total) >= 1) {     // k = BD×AB / (BD×AB + BD×BC)     var ratio = area_0 / area_total;     // x = ax + k×(cx - ax)     intersection.x = from_0.x + ratio * vector_0.x;     // y = ay + k×(cy - ay)     intersection.y = from_0.y + ratio * vector_0.y;     return {intersection:intersection, crossed:crossed};   } else {     return null;   } }

ひとつ補っておきます。前述のとおり交点を求めるには、変数(area_total)に与えたふたつの外積の和(BD×AB + BD×BC)が0であってはいけません。さらに実際には、0でなくても値がきわめて小さいと、交点座標の振れ幅が極端になります。そこで、前掲コードの関数(crossProduct2D())では、外積の和が1以上である場合に交点のオブジェクトを返し、そうでないときの戻り値はnullとしました。

2次元平面のベクトルA(a_x, a_y)とB(b_x, b_y)の外積は、つぎの式で表されます。ベクトルAに対してBが右ネジの位置、つまり時計回りにあるとき値は正になります。2次元のベクトルの外積を求める関数(crossProduct2D())は、以下のように定めました。ふたつのベクトルはPointオブジェクトで渡し、外積の数値を返します。

A×B =a_xb_y - a_yb_x

function crossProduct2D(point0, point1) {   return point0.x * point1.y - point0.y * point1.x; }

これで、ふたつの線分の両端の4座標から、交点の座標が求められます。もっとも、ふたつの線分は、前掲図001のように交わるとはかぎりません、その他につぎの図002のふたつの交わり方がありえます。けれども、前述の外積を用いた面積比率による計算は、これらの場合にも当てはまることが確かめられています。詳しくは、「平面上の2直線の交点を外積により求める」をお読みください。

02 ふたつの線分が直接交わるかどうかを調べる

前項01では、ふたつの線分が直接交わらなくても、互いに直線として交点を求めました。そこでつぎに、ふたつの線分そのものが互いに交わるかどうかを調べてみましょう。互いに交わるということは、ひとつのベクトル(BD)から見て、もうひとつのベクトルの両端(AとC)が左右別の側に分かれることを意味します(図003)。

図003■ふたつの線分が直接交わる

そこで、ひとつのベクトルの始点(B)から他のベクトルの両端(AとC)へのふたつのベクトル(BAとBC)を、新たに考えます。初めのベクトル(BD)から見て、ふたつのベクトル(BAとBC)は互いに逆回りの位置です。つまり、それぞれのベクトルと初めのベクトルとの外積を求めれば、互いに符号が逆になります。

もっとも、ひとつの線分(BD)が短くてもうひとつ(AC)に届かない場合がありえます(図002左)。そこで、もうひとつのベクトル(AC)からも同じようにふたつのベクトルとの外積(AC×ABとAC×D)を求めて、その結果も符号が逆になったらふたつの線分は交わっているといえるのです。なお、ふたつの数値の符号が逆になることは、その積が負になることで確かめられます。

ふたつの線分が直接交わるかどうかをブール(論理)値で返す関数(isCrossed())は、つぎのように定めました。ふたつのベクトルの始点と終点を4つのPointオブジェクトで渡します。初めに掲げたサンプルコードでは、直接交わる場合とそれ以外とで、交点に描く丸印の色を変えています。

function getIntersection(from_0, to_0, from_1, to_1) {   var crossed = isCrossed(from_0, to_0, from_1, to_1);   return {intersection:intersection, crossed:crossed}; } function isCrossed(from_0, to_0, from_1, to_1) {   // BD   var vector_0 = new createjs.Point(to_1.x - from_1.x, to_1.y - from_1.y);   // BA   var vector_1 = new createjs.Point(from_0.x - from_1.x, from_0.y - from_1.y);   // BC   var vector_2 = new createjs.Point(to_0.x - from_1.x, to_0.y - from_1.y);   // (BD×BA)(BD×BC) > 0   if (crossProduct2D(vector_0, vector_1) * crossProduct2D(vector_0, vector_2) > 0) {     return false;   // 交わらない   }   // AC   var vector_3 = new createjs.Point(to_0.x - from_0.x, to_0.y - from_0.y);   // AB   var vector_4 = new createjs.Point(from_1.x - from_0.x, from_1.y - from_0.y);   // AD   var vector_5 = new createjs.Point(to_1.x - from_0.x, to_1.y - from_0.y);   // (AC×AB)(AC×AD) > 0   if (crossProduct2D(vector_3, vector_4) * crossProduct2D(vector_3, vector_5) > 0) {     return false;   // 交わらない   } else {     return true;   // 交わる   } }

本稿は、ふたつの線分の交点を2次元平面の外積から求めるコード例についてご説明しました。サンプルの細かい中身は、jsdo.itのコードでお確かめください。また、ベクトルの外積を含む数学的な解説は、「平面上の2直線の交点を外積により求める」をお読みください。

作成者: 野中文雄
更新日: 2014年1月10日 外積の和が0の場合の説明と、コードの修正を追加。
作成日: 2013年12月26日