計算幾何(7)

問)平面上の線分と線分との交差判定には最低でも何回の乗算が必要か?


単純そうな問題だが、これの結論を知らない人が多い。(もちろん計算幾何を専門でやっている人にとっては常識だろう。)


2点を通る線分 L = (Z1,Z2) , M = (Z3,Z4) ( Zi = (Xi,Yi) )が交差するための必要十分条件は、点Z3,Z4が線分Lに関して左右に分離されてかつ点Z1,Z2が線分Mに関して左右に分離されていることである。


線分Lに関して正領域にあるか負領域にあるかを判定するのは、CCWを求めたときと同様、外積の符号によって判定できる。


いま、Z1Z3をZ1からZ3へのベクトル、すなわち (Z3-Z1) の意味で、×を外積だとすれば、線分Lに対してZ3が正領域にあるか負領域にあるかを判定するのは、Z1Z2×Z1Z3の符号を見るだけで良い。


線分Lに関してZ3,Z4がそれぞれ正領域と負領域にわかれれば良いので、Z1Z2×Z1Z3 * Z1Z2×Z1Z4 < 0 で判定できる。同様に線分Mに関してZ1,Z2が左右に分離されるためには、Z3Z4×Z3Z1 * Z3Z4×Z3Z2 < 0 で判定できる。


ゲームプログラミングのためのリアルタイム衝突判定

つまり、10回の乗算と2回の符号判定である。乗算回数を極力減らすということなら8回の乗算と4回の符号判定である。


もしあなたが権威ある(?)『ゲームプログラミングのためのリアルタイム衝突判定』を持っているなら、§5.1.9.1の2D線分交差を見て欲しい。上記の結果をあまりエレガントとは言い難い方法で導出して、それを結論としてある。*1


実際世の中には、このように8回の乗算で済ます方法がベストだと思っている人が多いが(ほとんどの本で紹介されているのはこの方法だ)、本当は平面上の線分と線分との交差判定は5回の乗算が必要十分なのである。(つづく)

*1:交点を求めることと交差判定を行なうこととは違うので仕方ない意味もあるが。