球面上の三角形に対する内外判定（内部判定、包含判定）
球面上の三角形の内外判定をしたかったのだが、とりあえず適当に思いついたアルゴリズム。
- 球面三角形を 3 つの単位ベクトル a[0], a[1], a[2] であらわす。ただし、この順で、外から見て半時計回りになっていると仮定。また、それぞれ90度以下の角をなしているとする。
- 点 p が内部にあるかどうか判定したい。
- a[i] と p を通る直線 l が、a[i] の対辺 a[i+1]a[i+2] に交わる点 d[i] を求めると、d[i] :=N( (a[i]×p)×(a[i+1]×a[i+2]) )。
- p が内部にある ⇔ ∀i (a[i]⋅p > a[i]⋅d[i]) が成り立つ
以下、資料。結局、「これは！」っていうアルゴリズム見つからなかった。
