計算幾何(2)

program

(問) 二直線の交点を求めよ。ただし直線はそれぞれ a + s b , c + t dと表わされる。
(a,b,c,dは定ベクトル。s,tはパラメータで実数)


こんな初歩的な問題であっても一番スマートな解は自明じゃないことに私は驚く。


高校までの範囲で解くなら a + sb = c + tdと連立させて、
$\left(B D\right)\left(\begin{array}{l}s\\-t\end{array}\right)=C-A$
として左から$\left(B D\right)$の逆行列(もし存在すれば)を掛けて$\left(\begin{array}{l}s\\-t\end{array}\right)=\left(B D\right)^{-1}(C-A)$


である。(sかtかどちらかが求まればあとはa + sbかc + tdが交点である)
こうするしか無いとばかり思っていた。


Geometric Tools for Computer Graphics (The Morgan Kaufmann Series in Computer Graphics)


しかし、『Geometric Tools for Computer Graphics』を読むと外積を用いた方法が紹介されていた。
簡単のため、右辺 = C-A = Δと置く。そうすれば、sb = td + Δである。


いま試しにs(b×d)を計算すると、s(b×d) = (sb)×d = (td + Δ)×d = t d×d + Δ×d = Δ×d (同一ベクトルの外積は0になるので)


つまりs (b×d) = Δ×dで b×dが非0なら、これで両辺を割って s = Δ×d / (b×d)を導ける。


2次元ベクトルの外積は掛算2回と引き算1回。sを求めるのに要する計算コストは、掛算4回、引き算2回、割り算1回である。


最初に提示した逆行列を使ってsを求める場合と計算量自体は変わらないように見えるが(というか式は同一なんだけど)、最初に提示した方法は行列演算クラスを使うことになるだろうから、逆行列を求める過程で自動的にtまで求めてしまう。sだけでいいのにtまで求めてしまうのでその分の計算が余分である。行列演算クラスを用いる以上、sだけ求まった時点であとの計算をはしょることは難しい。


よって、この外積で求める方法のほうが優れていると言える。
こんなに簡単な問題なのにこんなに奥深いとは平面幾何は侮れない。