三角形と直線の交差判定

最終更新 2018年 1月28日
  三角形と直線の交差は、

1.   三角形を通る平面を求める。
2.   その平面と直線との交点を求める。
3.   2.得られた交点を三角形の辺ベクトルの線形結合によって表す。
4.   3.得られた線形結合の係数から、交点が三角形に含まれるかどうかを判定する。

という $4$ 段階を経て判定されうる。(解説を省きたい場合にはまとめへスキップ)

  解説

1.   三角形を通る平面を求める。
  問題の記述を簡潔にするため、 三角形 $ABC$ の頂点 $A$ を原点とする座標系を採用し、 点 $A$, $B$, $C$ の位置ベクトルをそれぞれ $\mathbf{a}$, $\mathbf{b}$, $\mathbf{c}$ と表すことにする。 $A$ は原点に置かれているので、
三角形と平面の交点00
である。
三角形と平面の交点の図00
三角形 $ABC$ を通る平面を $P$ とし、 平面の方程式
三角形と平面の交点01
と置く。 ここで、$\mathbf{n}$ は法線ベクトルであり、 $h$ は符号付き距離である。 また、 $\mathbf{x}$ は平面 $P$ 上の任意の位置ベクトルである。
  頂点の位置ベクトル $\mathbf{a}$, $\mathbf{b}$, $\mathbf{c}$ は、 平面 $P$ の上にあるので、
三角形と平面の交点02
を満たす。 ここで、 $\mathbf{a} = 0$ であることから、 第一式より、
三角形と平面の交点03
である。 これより、
三角形と平面の交点04
である。 従って、 法線ベクトル $\mathbf{n}$ は、 $\mathbf{b}$ と $ \mathbf{c}$ の両方と直交するベクトルである。 よって、 $\mathbf{n}$ は $\mathbf{b}$ と $ \mathbf{c}$ の外積の方向を向く (下図) 。
三角形と平面の交点の図01
すなわち、
三角形と平面の交点05
と表されるベクトルである。 ここで、$C$ はベクトルの大きさを決める定数である。
  以上のように、 法線ベクトル $\mathbf{n}$ と符号付き距離 $h$ が求められたので、 三角形 $ABC$ を通る平面の方程式は、
三角形と平面の交点06
と表される。
  この式からも分かるように、 $\mathbf{n}$ に付いていた定数 $C$ は、 $0$ でないならばどんな値であっても構わない。 そこで今後は、 $C=1$ とする。 すなわち、
三角形と平面の交点07
とする。


2.   平面と直線との交点を求める
  判定対象となっている直線を $L$ とし、 $L$ 上の 一点の位置ベクトルを $\mathbf{r}_{0}$、 $L$ の方向ベクトルを $\mathbf{m}$ とすると、 $L$ 上の任意の点 $\mathbf{r}$ は、 パラメータ $t$ によって、
三角形と平面の交点08
と表される。
  平面 $P$ と直線 $L$ の交点を $I$ とし、 その位置ベクトルを $\mathbf{r}^{I}$ と表す。 $\mathbf{r}^{I}$ は直線 $L$ 上にあり、 なおかつ、 平面 $P$ 上にある点の位置ベクトルである (下図)。
三角形と平面の交点の図02
したがって、 $\mathbf{r}^{I}$ は、
三角形と平面の交点09
と、
三角形と平面の交点10
の両方を満たす。 これらより、
三角形と平面の交点11
が成立する。 よって、
三角形と平面の交点12
と $t$ が求まる。
  これより、 交点の位置 $\mathbf{r}^{I}$ は、
三角形と平面の交点13
である。


3.   交点を三角形の辺ベクトルの線形結合によって表す
  ベクトル
三角形と平面の交点14
と、 法線ベクトル
三角形と平面の交点15
を合わせた3つのベクトルは、互いに線形独立である (証明は補足を参考)。
  よって、 任意のベクトルは、 これらの線形結合によって表されうる (次元と線形独立なベクトルは基底を成すを参考)。 従って、 交点 $\mathbf{r}^{I}$ を
三角形と平面の交点16
と表すことが出来る。 ここで現れた係数 $ r_{1}, r_{2}, r_{3}$ の導出するためには、 次のように考察する。
  まず、 基本ベクトル
三角形と平面の交点17
を定義する。 これらは互いに線形独立であるので、 ベクトル $\mathbf{b}, \mathbf{c}, \mathbf{n}$ の それぞれを
三角形と平面の交点18
と表すことができる。
  これらを用いると、 交点 $\mathbf{r}^{I} $ を
三角形と平面の交点19
と表すことができる。 一方、
三角形と平面の交点20
と表すこともできるので、 上の式と各成分を比較することにより、
三角形と平面の交点21
の関係が成立することが分かる。 これを行列を用いてまとめると、
三角形と平面の交点22
となる。 ここで、 行列 $C$ と ベクトル $\mathbf{r}$ を
三角形と平面の交点23
と定義すると、
三角形と平面の交点24
と表せる。
  行列 $C$ は、 定義から分かるように ベクトル $\mathbf{b}$、$\mathbf{c}$、$\mathbf{n}$ を列ベクトルに持つ行列である。 すなわち、
三角形と平面の交点25
である。 ところで、 補足で示されているように、 これらの列ベクトルは互いに線形独立である。 そして、 一般に互いに線形独立な列ベクトルのみを持つ正方行列は逆行列を持つことから、 $C$ には逆行列 $C^{-1}$ が存在する。 そこで、 $(2)$ の両辺に $C^{-1}$ を掛けると、
三角形と平面の交点26
を得る。
  右辺の行列 $C$ とベクトル $\mathbf{r}^{I}$、$\mathbf{a}$ は、 既に与えられているもの(または求められたもの)であるので、 $(3)$ から $(1)$ の係数 $ r_{1}, r_{2}, r_{3}$ が導出される。


4.   係数を用いて交点が三角形に含まれるかどうかを判定する
  $(3)$ で求められた係数 $ r_{1}, r_{2}, r_{3}$ が如何なる関係性を満たすときに、 直線と三角形が交差したと判定されるのかをここで考察する。
  はじめに $r_{3}=0$ であることを示す。 このことは $(3)$ から直接示すことも出来るが、 次の方法によって示すことも出来る。 まず、 $(1)$ から、
三角形と平面の交点27
が成立するが、
三角形と平面の交点28
であるので、
三角形と平面の交点29
である。 これより、
三角形と平面の交点30
である。 また、 左辺の $\mathbf{r}^{I}$ は、 平面 $P$ 上の点であるので、
三角形と平面の交点31
を満たすことから、
三角形と平面の交点32
が成立する。 ここで、$\left( \mathbf{n}, \hspace{1mm} \mathbf{n} \right) =\| \mathbf{n} \|^2 \neq 0$ であることから、
三角形と平面の交点33
が得られる。
  さて、 これと $(1)$ から $\mathbf{r}^{I}$ は、
三角形と平面の交点34
と表される。 ベクトル $\mathbf{r}^{I} $ は、 頂点 $A$ から交点 $I$ に向かうベクトルであるので、 このベクトルが三角形 $ABC$ の中に含まれるための必要十分条件が求まれば、 それが直線 $L$ と三角形 $ABC$ が交差するための必要十分条件になる(下図)。
三角形と平面の交点の図03
そこで、交点 $I$ が三角形 $ABC$ の内部にあると仮定し、 直線 $AI$ と線分 $BC$ の交点を $J$ とする。 $J$ は線分 $BC$ 上の点であるので、 位置ベクトル $\mathbf{r}^{J}$ を
三角形と平面の交点35
と表すことが出来る(下図)。
三角形と平面の交点の図04
これを用いると、 交点 $I$ が線分 $AJ$ 上の点であることから、 位置ベクトル $\mathbf{r}^{I}$ を
三角形と平面の交点36
と表すことが出来る。
  これと $(4)$ を比較すると分かるように、
三角形と平面の交点37
が成立し、 $0 < s < 1$ かつ $0 < \alpha < 1$ であることから、
三角形と平面の交点38
の 3 つの関係が満たされる。 以上から、 交点 $I$ が三角形 $ABC$ の中に入っているならば、 $(5)$ が成立する。
  一方、逆に $(5)$ が成立すると仮定する。 まず、 $ 0 < r_{1} +r_{2} < 1 $ から
三角形と平面の交点39
を満たす $\alpha$ が存在することが分かる。 このとき、
三角形と平面の交点40
が成立するので、
三角形と平面の交点41
を満たす $s$ が存在することが分かる。 これより、
三角形と平面の交点42
となるため、 $(4)$ から $\mathbf{r}^{I} $ は、
三角形と平面の交点43
と表される。
  ここで $ s\mathbf{b} + (1-s) \mathbf{c} $ は、 線分 $BC$ 上にある点の位置ベクトルである。 ゆえに、 $0< \alpha < 1$ であることから、 $\mathbf{r}^{I} $ は、 点 $A$ から三角形内部にある点を指す位置ベクトルであることが分かる。
三角形と平面の交点の図05
  以上から、 $(5)$ は、 交点の位置 $\mathbf{r}^{I}$ が三角形 $ABC$ の中に含まれるための必要十分条件である。 ゆえに、 直線 $L$ と三角形 $ABC$ が交差するための必要十分条件である。


4.   まとめ
  直線 $L$ が頂点位置ベクトル $\mathbf{a}, \mathbf{b}, \mathbf{c}$ を持つ三角形 $ABC$ と交差するための必要十分条件は、 頂点 $A$ を原点とする座標系において、 $ABC$ を通る平面 $P$ の法線ベクトル
三角形と平面の交点44
によって表される交点 $I$ の位置ベクトル
三角形と平面の交点45
と 3行3列の行列
三角形と平面の交点46
による関係式
三角形と平面の交点47
から導かれる係数 $r_{1}$ と $r_{2}$ が
三角形と平面の交点48
を満たすことである。


補足
  3つのベクトル
三角形と平面の交点49
が互いに線形独立であることを示す。
三角形と平面の交点の図05
そこで、
三角形と平面の交点50
と置く。 これより、
三角形と平面の交点51
が成立する。 内積の線形性によって書き換えると、
三角形と平面の交点52
と表される。 ここで、 スカラー三重積の循環性を用いると、
三角形と平面の交点53
であり、 同様に $ (\mathbf{c} , \mathbf{n}) = 0 $ であるので、
三角形と平面の交点54
が成立する。 $\mathbf{n}\neq 0$ であるので、 $\gamma = 0$ を得る。 よって、
三角形と平面の交点55
が成立する。 $\mathbf{b} $ と $\mathbf{c} $ は、 三角形の辺ベクトルであるために、互いに平行でない(互いに独立である)。 よって、 上式が成立するためには、 必ず $\alpha=\beta=0$ でなくてはならない。 以上から、$\alpha=\beta=\gamma=0$ が示されたので、 3つのベクトル $\mathbf{b} , \mathbf{c} , \mathbf{n}$ は、互いに線形独立である。
  従って、 任意のベクトルは、これらの線形結合によって表される。