線分交差判定（おぼえがき） - alembert の作業日記

２つの線分の交差は、どのようなアルゴリズムで判定しているのだろうかと以前から気になっていたが、今日読んだ『図形処理入門』（著者略）という本ですべて解決した。
どうやら外積の性質をうまく使っているらしかった。線分が交差するには、当然片方の線分の頂点はもう片方の線分をまたいだ位置にあり、もう片方にも同様のことが言えることが必要十分である。この「またぐ」という概念をを表すのに、外積が登場したのだ。

２つの線分 AA' 及び、BB' が交差するには、次の条件が成り立つことが必要十分である。

$(\vec{AA'}\times\vec{AB})\cdot(\vec{AA'}\times\vec{AB'})\lt 0 \; \text{and} \; (\vec{BB'}\times\vec{BA})\cdot(\vec{BB'}\times\vec{BA'})\lt 0$

つまり、例えば「点B, B' が線分 AA' をまたいでいる」ということを線形代数学的に考えれば、「↑AA' が ↑AB あるいは ↑AB' と平行になるように、それぞれ回転角最小の回転をしたとき、その方向は互いに反対となる。」ということである。回転方向が互いに反対であれば、当然外積は反対方向となるから、内積をとると負になるわけである。