Edited at

2直線の交差(交点)

More than 1 year has passed since last update.


概要


直線の数式表現

直線のパラメータ(媒介変数)表現は、次の式のとおりです。

\begin{eqnarray}

\mathbf{r}(t) = \mathbf{p} + t \, \mathbf{u}
\end{eqnarray}

ここで、$\mathbf{p}$:基準点、$\mathbf{u}$:方向ベクトル($|\mathbf{u}| = 1$)、$t$:パラメータ(媒介変数)です。

line_formula


2次元の交差

先の直線のパラメータ表現より、2直線の式を次のとおり定義します。

\begin{eqnarray}

\mathbf{l}(s) & = & \mathbf{p} + s \, \mathbf{u} \\
\mathbf{m}(t) & = & \mathbf{q} + t \, \mathbf{v}
\end{eqnarray}

2直線 $\mathbf{l}, \mathbf{m}$が交差したと仮定し、そのときの各パラメータを $\sigma, \tau$とする。また、直線$\mathbf{m}$と垂直な単位ベクトルを$\mathbf{n}$($\mathbf{n} \perp \mathbf{v} $)とすると交点位置での各パラメータ$\sigma, \tau$は

\begin{eqnarray}

\sigma & = & \frac{\mathbf{n} \cdot (\mathbf{q} - \mathbf{p})}{\mathbf{n} \cdot \mathbf{u}} \\
\tau & = & \frac{\mathbf{v} \cdot (\mathbf{l}(\sigma) - \mathbf{q})}{|\mathbf{v}|^2}
\end{eqnarray}

となります。

Intersect2D.png


導出

この2直線が交差するとして、その交点でのそれぞれのパラメータを$\sigma$、$\tau$とすると、2直線の関係式は

\begin{eqnarray}

\mathbf{l}(\sigma) & = & \mathbf{m}(\tau)
\end{eqnarray}

となります。先のパラメータ表現による直線の式で書き直すと以下のようになります。

\begin{eqnarray}

\mathbf{p} + \sigma \, \mathbf{u} & = & \mathbf{q} + \tau \, \mathbf{v}
\end{eqnarray}

ここで直線$\mathbf{m}$と垂直な単位ベクトルを$\mathbf{n}$($\mathbf{n} \perp \mathbf{v} $)とし、次のように両辺を$\mathbf{n}$と内積をとります。

\begin{eqnarray}

\mathbf{n} \cdot (\mathbf{p} +\sigma \, \mathbf{u}) & = & \mathbf{n} \cdot (\mathbf{q} + \tau \, \mathbf{v}) \\
\end{eqnarray}

$\mathbf{n} \cdot \mathbf{v} = 0$であるから、$\sigma$について解くと

\begin{eqnarray}

\sigma & = & \frac{\mathbf{n} \cdot (\mathbf{q} - \mathbf{p})}{\mathbf{n} \cdot \mathbf{u}} \\
\end{eqnarray}

となり、この$\sigma$を直線 $\mathbf{l}(\sigma)$ と代入すれば、交点位置(座標)が求まります。

$\mathbf{l}(\sigma) = \mathbf{q} + \tau \mathbf{v}$ から $\tau$ も求めることができます。(実用上、$\sigma$だけ求めれば十分な場合が多い。)


3次元の交差

3次元の場合も直線式は、2次元と同様で次のとおりです。

\begin{eqnarray}

\mathbf{l}(s) & = & \mathbf{p} + s \, \mathbf{u} \\
\mathbf{m}(t) & = & \mathbf{q} + t \, \mathbf{v}
\end{eqnarray}

2直線$\mathbf{l}, \mathbf{m}$が最も近い位置でのそれぞれのパラメータを$\sigma, \tau$とするとき

\begin{eqnarray}

\sigma & = & \frac{\mathbf{r} \cdot ( \mathbf{u} - \alpha \, \mathbf{v} )}{\alpha^2 - 1} \\
\tau & = & \frac{\mathbf{r} \cdot ( \alpha \, \mathbf{u} - \mathbf{v} )}{\alpha^2 - 1}
\end{eqnarray}

となり、ただし $\mathbf{r} = \mathbf{p} - \mathbf{q} , \, \alpha = \mathbf{u} \cdot \mathbf{v}$ です。このとき、以下の条件のとき

\begin{eqnarray}

|\mathbf{l(\sigma)} - \mathbf{m(\tau)}| \lt \varepsilon \,\,\, (\varepsilon \ll 1)\\
\end{eqnarray}

2直線は交差関係とします。


導出

3次元の場合、交点を直接求めるということが難しいです(2次元のように交差に関する2つの関係式が定義できないため)。そのため、それぞれの直線で最近傍となる位置を求め、それがトレランス値 $\varepsilon$ より小さければ、交点とするという近似計算で求めます。

次の2つの直線 $\mathbf{l},\mathbf{m}$を

\begin{eqnarray}

\mathbf{l}(s) & = & \mathbf{p} + s \, \mathbf{u} \\
\mathbf{m}(t) & = & \mathbf{q} + t \, \mathbf{v}
\end{eqnarray}

として、2直線 $\mathbf{l}, \mathbf{m}$ の最近傍となる位置のパラメータをそれぞれ $\sigma, \tau$ とすると

2lines_image

最近傍点同志を結んでできるベクトル "$\mathbf{l}(\sigma)-\mathbf{m}(\tau)$" と各直線 $\mathbf{l}, \mathbf{m}$ は直角の関係のため、内積を用いて数式で表現すると

\begin{eqnarray}

\mathbf{u} \cdot \{ \mathbf{l}(\sigma) - \mathbf{m}(\tau) \} & = & 0 \\
\mathbf{v} \cdot \{ \mathbf{l}(\sigma) - \mathbf{m}(\tau) \} & = & 0
\end{eqnarray}

となり、直線のパラメータ表現の式に戻します。

\mathbf{u} \cdot ( \mathbf{p} + \sigma \, \mathbf{u} - \mathbf{q} - \tau \, \mathbf{v} ) = 0 \\

\mathbf{v} \cdot ( \mathbf{p} + \sigma \, \mathbf{u} - \mathbf{q} - \tau \, \mathbf{v} ) = 0

ここで、未知数が $\sigma, \tau$ 2つに対し2つの関係式(方程式)がたてられたので、$\sigma, \tau$ を求めることができます。

$\mathbf{u} \cdot \mathbf{u} = \mathbf{v} \cdot \mathbf{v} = 1$ を考慮すると $\sigma, \tau$ は以下のとおりです。

\begin{eqnarray}

\sigma & = & \frac{\mathbf{r} \cdot ( \mathbf{u} - \alpha \, \mathbf{v} )}{\alpha^2 - 1} \\
\tau & = & \frac{\mathbf{r} \cdot ( \alpha \, \mathbf{u} - \mathbf{v} )}{\alpha^2 - 1} \\
\mathbf{r} & = & \mathbf{p} - \mathbf{q} \\
\alpha & = & \mathbf{u} \cdot \mathbf{v}
\end{eqnarray}

ここまで求めた $\sigma, \tau$ は近傍点となるパラメータのため交差かどうかの条件式を考慮しないといけません。その条件式は、近傍点間距離がトレランス値未満であるとします。

\begin{eqnarray}

|\mathbf{l(\sigma)} - \mathbf{m(\tau)}| \lt \varepsilon \,\,\, (\varepsilon \ll 1)
\end{eqnarray}