点と三角形の当たり判定

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

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

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

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

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

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

ポイントは、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)$