図形間の相互関係２

複数の図形間の相互関係をベクトル演算によって解析しよう．

今回は，板書中心です．

二線分の交差判定

線分 \( \Pt{AB} \) と \( \Pt{CD} \) とが交差しているか？

Fig.1 (a) は交差している場合の例，同 (b) は交差してしていない場合の例である．人間なら一目瞭然ではあるが... それをコンピュータに判断させるには？

線分 \( \Pt{AB} \) から見て点 \( \Pt{C} \) と \( \Pt{D} \) とが左右どちら側にあるか？また，線分 \( \Pt{CD} \) から見て点 \( \Pt{A} \) と \( \Pt{B} \) とが左右どちら側にあるか？

正確に判定するには，２〜４回の外積演算が必要となり，計算コストが高い．

無交差のラフな除外

多数の線分間の交差を判定する際，非交差なペアが多く，計算コストを無駄に費やしてしまうことになるだろう．明らかに交差しない場合を低コストな前処理として判定・除外しておけば，正確だが高コストな交差判定の実行回数を，大抵は，大幅に削減できる．

バウンディングボックス（bounding box; BB）：各図形に外接する直方体or長方形
各図形の BB については，頂点座標の各成分の最大値・最小値から決定できますね．
バウンディングスフィア（bounding sphere; BS）：各図形に外接する球or円
各図形の BS については，頂点座標の平均値によって中心座標を，中心からの距離の最大値によって半径を決定できますね．

BB や BS 同士が無交差ならば，当然，元の図形同士も無交差ですね．正確な判定は不要．

BB や BS 同士が交差していても，元の図形同士が必ずしも交差しているとは限りませんよ．この場合だけ，正確な判定が必要．

多角形に対する点の内外判定

多角形 \( \Pt{P_0 P_1 P_2 ... P}_{n-1} \) に対して，指示点 \( \Pt P \) は内部／外部のどちらにあるか？

凸多角形だけに対応可能な手法：辺から見た指示点の方向を利用
辺 \( \Pt{P}_m \Pt{P}_{m+1} \) から見た方向（左側 or 右側）は，外積 \( \overrightarrow{\Pt{P}_m \Pt{P}_{m+1}}\X\overrightarrow{\Pt{P}_m \Pt{P}} \) の \( z \) 成分の正負で判定できますね．
任意多角形（凹凸）に対応可能な手法：
- 指示点から見た辺の角度を利用
  辺 \( \Pt{P}_m \Pt{P}_{m+1} \) の見込み角 \( \theta_m \) の総和 \( \DS\sum_m \theta_m \) が \( 2 \pi \) かゼロかで判定．
  
  数学的にはシンプルで良さげですが，角度 \( \theta_m \) の算出には高コストな実数計算 \( \atan{} \) を伴うので，プログラミング的には使いたくありませんね．
- 指示点から出したビームの交差回数を利用
  指示点から発射されたビーム（半直線）と辺との交差回数が奇数か偶数かで判定．
  
  理論的に，ビームの方向は任意ですが，現実的には，水平とか垂直に限定しておけば，交差判定の計算を低コスト（外積とか使わず）に実現できますよ．
  
  あ...最後はベクトル演算ではなくなってしまいました... こだわらず，効率的な手法の利用が重要，ということで．