三角形と線分の交点 - 機械学習基礎理論独習

アルゴリズム

三角形の頂点の位置ベクトルを ${\bf v}_0,{\bf v}_1,{\bf v}_2$ 、線分の端点の位置ベクトルを ${\bf l}_0,{\bf l}_1$ とします。
三角形の頂点を通る平面の法線ベクトル $\bf n$ を求めます。

$\begin{eqnarray} {\bf n}=({\bf v}_1-{\bf v}_0)\times({\bf v}_2-{\bf v}_0)\tag{1} \end{eqnarray}$

三角形の頂点を通る平面の方程式 $f(x,y,z)=ax+by+cz+d=0$ を求めます。

$\begin{eqnarray} &&a=n_x\\ &&b=n_y\\ &&c=n_z\\ &&d=-a {v_0}_x-b {v_0}_y-c {v_0}_z+d\\ \end{eqnarray}$

交点 ${\bf c}$ は以下のようになります。

$\begin{eqnarray} {\bf c}={\bf l}_0+\frac{-f({\bf l}_0)}{f({\bf l}_1)-f({\bf l}_0)}({\bf l}_1-{\bf l}_0) \end{eqnarray}$

線分の端点が2つとも平面上にある、または
線分の端点が2つとも平面上に無く、 $f({\bf l}_0),f({\bf l}_1)$ が同じ符号であるとき、交点なしとします。
この交点を2次元に変換します。やり方は平面の法線ベクトルの一番大きい成分以外を採用するという方法です。
以降、 ${\bf v}_i,{\bf c}$ は2次元とします。
2次元で交点が三角形の内部あるか判定をします。
三角形の頂点数分以下を計算します。( $ipp$ は $i + 1$ を3で割ったときの余りとします)

$\begin{eqnarray} z_i=({\bf v}_{ipp}-{\bf v}_i)_x \cdot ({\bf c}-{\bf v}_i)_y - ({\bf v}_{ipp}-{\bf v}_i)_y \cdot ({\bf c}-{\bf v}_i)_x \end{eqnarray}$

$z_i=0$ となる $i$ の除いた $z_i$ が全て同じ符号の時に三角形の内部に交点があるとします。

最後に

これも図が無いですね。これは書いたほうが良いかなと思います。いずれ書きます。