計算幾何(8)
(前回のつづき)
線分同士の交差判定を行なうためには、線分を直線とみなして、まず二直線の交点を求めるほうが簡単である。
直線L = (Z1,Z2) , 直線M = (Z3,Z4) の交点なら L : t Z1 + (1-t) Z2 , M : sZ3 + (1-s)Z3として、s,tを求めて 0<t<1 , 0<s<1の範囲であるかを調べれば良い。
しかしid:yaneurao:20070116のようにしてs,tを求めれば、t=ΔT / Δ , s = ΔS / Δの形になるので、実際はこの割り算を行なう必要はなく、ΔT と Δ , ΔSとΔ との符号比較だけで十分である。よって5回の乗算と符号比較で十分だ。
また十分であると同時に5回の乗算は必要であり(証明は割愛)、5回の乗算で必要十分なのだ。この証明は、公式資料では吉田清範さんが最初に示している。*1
