FN1002001 - 2次元平面で座標が三角形の内側にあるかを調べる

Adobe Flash非公式テクニカルノート

2次元平面で座標が三角形の内側にあるかを調べる

ID: FN1002001

Product: Flash CS4 and above

Platform: All

Version: 10 and above/ActionScript 3.0

2次元平面において、ある座標が予め定められた形状の内側にあるかどうかを知りたいときがあります。その形状を三角形に分けた頂点座標が得られれば、ベクトルの外積を使って調べることができます。

01 ベクトルの外積と座標の位置関係
ベクトルAとBの外積A×Bは、ふたつのベクトルのどちらにも垂直なベクトルを導きます。その向きは、ベクトルAからBに右ネジを回して進む先になります(図001)^[*1]。なお、3次元空間におけるベクトルの外積について詳しくは、「Vector3D.crossProduct()メソッド」をお読みください。

図001■ベクトルの外積

すると、逆に外積A×Bのベクトルの向きを調べれば、位置ベクトルBがAの右にあるか左にあるかを知ることができます。とくに、位置ベクトルAとBが2次元のxy平面上にあるときは、外積A×Bのz座標値の正負でベクトルBのAに対する位置がわかるということです(表001)。

表001■2次元平面における位置ベクトルの外積のz座標値とふたつのベクトルの位置関係

外積A×Bのz座標値	ベクトルAに対するBの位置
正	位置ベクトルBはAの右側
0	位置ベクトルBはAと重なる
負	位置ベクトルBはAの左側

02 ベクトルの外積で座標が三角形の内側にあるかを調べる
2次元平面における三角形の3辺のベクトルそれぞれについて、その始点と調べる座標を結んだベクトルとの外積により、座標が辺のベクトルの右側にあるかどうかを確かめます。時計回りに向けた3辺のベクトルいずれに対しても座標のベクトルが右ネジの位置にあるなら、その座標は三角形の内側になります(図002)。つまり、外積として求めたすべてのベクトルのz座標値が、正(辺上も加えるなら0を含めます)であればよいということです(前掲表001)。

図002■外積で2次元平面上の座標が三角形の内側にあるかどうかを調べる

以下の関数xIsRight()は、2次元平面の位置ベクトルAとBについて、BがAの右もしくはその上にあるかどうかをブール(論理)値で返します。引数には、位置ベクトルA(A_x, A_y)とB(B_x, B_y)のそれぞれのxy座標値を計4つ渡します。

スクリプト001■2次元平面のベクトルふたつの位置関係を返す関数

function xIsRight(ax:Number, ay:Number, bx:Number, by:Number):Boolean {
var a:Vector3D = new Vector3D(ax, ay, 0);
var b:Vector3D = new Vector3D(bx, by, 0);
var crossProduct:Vector3D = a.crossProduct(b);
var bIsRight:Boolean = (crossProduct.z >= 0);
return bIsRight;
}

スクリプト第2～3行目は、受取ったふた組のxy座標値から、z座標値を0としたVector3Dインスタンスを生成して変数(aとb)に納めます。つぎに、第4行目で、ふたつのベクトル(aとb)の外積を求めます(変数crossProduct)。そして、第5行目は外積のz座標値が0以上であるかどうかをブール値の変数(bIsRight)に納め、第6行目でその値を関数から返しています^[*2]。

03 2次元平面におけるベクトルの外積
3次元空間の位置ベクトルA(A_x, A_y, A_z)とB(B_x, B_y, B_z)の外積A×Bは、ふたつの成分を用いてつぎの式で導けます(前出「Vector3D.crossProduct()メソッド」参照)。

A×B = (A_yB_z - A_zB_y, A_zB_x - A_xB_z, A_xB_y - A_yB_x)

2次元のxy平面ではz座標値は0です。つまり、A_z = B_z = 0ですので、外積A×Bのベクトルの成分はつぎのようになります。

A×B = (0, 0, A_xB_y - A_yB_x)

前掲スクリプト001の関数xIsRight()では、ふたつのVector3Dインスタンスを生成したうえで、その外積をVector3D.crossProduct()メソッドにより求めています。しかし、外積のxy座標はともに0と決まっており、ほしいのはz座標値だけです。そうであれば、z座標値の成分計算のみを四則演算で行った方が、ふたつのVector3Dインスタンスを生成するより端的でしょう。すると、関数xIsRight()はつぎのスクリプト002のように書替えられます^[*3][*4]。

スクリプト002■2次元平面のベクトルふたつの位置関係を外積のz座標値の計算により返す関数

function xIsRight(ax:Number, ay:Number, bx:Number, by:Number):Boolean {
var bIsRight:Boolean = (ax * by - ay * bx >= 0);
return bIsRight;
}

[*1] Flashの3次元座標空間である「右手座標系」、つまりz軸が奥に向かって正となる場合です(図003)。「右手座標系」については、「Vector3Dクラス」をご参照ください。

図003■Flash Player 10の3次元直交座標系

* [ヘルプ] > [ActionScript 3.0 言語およびコンポーネントリファレンス] > [Vector3D]より引用

[*2] スクリプト001の関数xIsRight()で座標が三角形の内側にあるかどうか調べるサンプルスクリプトを、wonderflに「Selecting the clicked triangle with Vector3D Class」としてアップロードしました。Graphics.drawTriangles()メソッドにより4つの四角形に分けて描いた矩形をクリックすると、その座標を内側にもつ三角形が赤い線で囲まれます(図004)。

図004■クリックした座標を内側にもつ三角形が赤い線で囲まれる

なお、Graphics.drawTriangles()メソッドとその使い方については、Adobeデベロッパーセンター「三角形分割によるテクスチャマッピング－ Graphics.drawTriangles()メソッド Part 1」と「三角形分割によるテクスチャマッピング－ Graphics.drawTriangles()メソッド Part 2」、および「Graphics.drawTriangles()メソッド」をお読みください。

[*3] この計算であれば、Vector3Dクラスが備わっていないFlash Player 9でも使えます。

前出注[*2]のwonderflのサンプルスクリプトのメソッドxIsRight()を、スクリプト002の定義に書替えて「Selecting the clicked triangle」としてアップロードしました。

[*4] 3次元空間のベクトルとは別に、2次元平面のベクトルA(A_x, A_y)とB(B_x, B_y)の外積A×Bはつぎのように定義されます(「２次元ベクトルの外積の効用(線形代数学の教科内容の改善に向けて)」参照)。その結果はベクトルでなくスカラー(実数)となり、3次元空間における外積のz座標値に等しいことが注目されます。

A×B = |A||B|sinθ = A_xB_y - A_yB_x

作成者: 野中文雄
作成日: 2010年2月26日