点と三角形の当たり判定

今回は点と三角形の当たり判定の計算方法についてです。

point-triangle

基本的な考え方は、下図の様に点Pから三角形の各頂点ABCに向かうベクトル間のなす角を調べることで行います。

triangle-abc-in

(ただし、0^\circ \angle AB, \angle BC, \angle CA < 360^\circ)

上図の∠AB、∠BC、∠CAは三角形の内部に点Pがある限り180°以上になることは有り得ません。
もし180°以上の角が存在していたら、点Pは三角形の外側にあると判定することが出来ます。

triangle-abc-out

上で示した例は、頂点ABCが反時計回りに配置されているパターンです。
しかし、実際には時計回りになる場合も有り得ます。

triangle-acb-in

この場合、点Pが三角形の内部にある場合は∠AB、∠BC、∠CAがすべて180°より大きくなります。
点Pが三角形の外側にある場合は180°以下の角が存在することになります。

triangle-acb-out

ポイントは、180°以下になる角が存在してもすべての角が180°以下にはならないところです。
頂点が反時計回りの場合も180°以上の角が存在してもすべての角が180°以上にはなりません。

したがって、点Pが三角形の内側にあるための∠AB、∠BC、∠CAの条件は次式のようになります。

(\angle AB < 180^\circ \land \angle BC < 180^\circ \land \angle CA < 180^\circ) \lor (\angle AB > 180^\circ \land \angle BC > 180^\circ \land \angle CA > 180^\circ)

この条件式は、以下のような\sinを用いた式に変換できます。

(\sin \angle AB > 0 \land \sin \angle BC > 0 \land \sin \angle CA > 0) \lor
(\sin \angle AB < 0 \land \sin \angle BC < 0 \land \sin \angle CA < 0)

この\sinを求めるためにはどうすれば良いでしょうか?

答えは外積を使うことです。

ベクトル\vec{a}\vec{b}の外積\vec{a} \times \vec{b}は、\vec{a}\vec{b}のなす角\thetaを用いて以下の様に表現されます。

\vec{a} \times \vec{b} = |\vec{a}| |\vec{b}| \sin \theta

 
また、\vec{a} = \left(      \begin{array}{c}        x_a \\        y_a      \end{array}    \right)\vec{b} = \left(      \begin{array}{c}        x_b \\        y_b      \end{array}    \right)とすると、以下の様に表現できます。

\vec{a} \times \vec{b} = x_a y_b - y_a x_b

 
∠AB、∠BC、∠CAの条件式を以下のように変形します。

(|\vec{PA}||\vec{PB}| \sin \angle AB > 0 \land |\vec{PB}||\vec{PC}| \sin \angle BC > 0 \land |\vec{PC}||\vec{PA}| \sin \angle CA > 0) \lor
(|\vec{PA}||\vec{PB}| \sin \angle AB < 0 \land |\vec{PB}||\vec{PC}| \sin \angle BC < 0 \land |\vec{PC}||\vec{PA}| \sin \angle CA < 0)

これはベクトル\vec{PA}\vec{PB}\vec{PC}の外積で表現できます。

(\vec{PA} \times \vec{PB} > 0 \land \vec{PB} \times \vec{PC} > 0 \land \vec{PA} \times \vec{PC} > 0) \lor
(\vec{PA} \times \vec{PB} < 0 \land \vec{PB} \times \vec{PC} < 0 \land \vec{PA} \times \vec{PC} < 0)

この条件式の結果が真なら「当たり」、そうでなければ「はずれ」となります。

点と三角形の当たり判定は点と円の当たり判定以上に乗算が増えるので処理が重くなります。
AABBを用いたブロードフェーズと組み合わせて使用するのが望ましいかもしれません。

当たり判定の高速化 ‐ ブロードフェーズとナローフェーズ