Mac用プロットライブラリ-25「重なりチェックのアルゴリズム」

前回は2次元オブジェクトが重なっているかどうか、をどうやってチェックするか大まかなフローを考えた。これをもとにもう少し具体的なアルゴリズムを考えてみる。

AABBのアルゴリズム

オブジェクトに外接する長方形R_nを

とする。つまり座標に沿った辺の範囲で指定されているとする。二つの長方形R_nとR_mが重ならない条件は、

ようするに、どちらかの座標軸に沿った区間がオーバーラップしなければ長方形は重なっていないと判断できる。これはこのままプログラムに書けるほど簡単。

交差判定法

ある頂点Pが多角形オブジェクトに内包されているかどうかを、交差判定法に従って頂点からx軸の正の方向に線を引いて辺と交差するかどうかを調べることにする。

図-26のように多角形の隣り合う二つの頂点A、Bの座標の値を取る（この座標を結ぶ線分が辺になっているはず） それぞれの座標を

とする。点Pから右側（xの正の方向）に向かう線分P₊がこの辺と交差するかどうかを調べる。

辺ABの式を媒介変数を使って

と書く。σが媒介変数で

のとき、式-13の点は辺の上にある。

これを使ってまず

をσに関して解く。 つまり

として

1. B_y-A_y= 0のとき、辺はy軸に平行なので分子のP_y-A_yが0かどうかを調べる。0で無ければ交差しない。0ならばA_x≤ P_x ≤ B_x（あるいはB_x≤ P_x ≤ A_x）であるかを調べる。範囲にあれば点Pは辺の上にある
2. 式-16のσの値が
   1. σ<0、あるいはσ>1なら上下方向にはずれているので交差しない
   2. 0≤σ≤1ならこのσを使って式-13のx座標を計算する。その値をC_xとする。つまり、
      
      としたとき
      1. C_x < P_xなら辺ABは点Pの左側（x軸の負の方向）にあるのでP₊とは交差しない
      2. C_x ≥ P_xなら交差する

となる。

これはめんどくさいけどわかりやすい。でも多くの場合に割り算が発生する。できればなるべく計算を減らしたい。

なるべく計算量が少なくなるように

そこでもう少し場合分けをしてみる。

1. A、Bのx座標が両方ともPのx座標よりも小さい場合
   
   交差無し（図-27）
   
2. 少なくともどちらか一方のx座標がPのx座標よりも大きい場合で、y座標が両方とも大きい、あるいは両方とも小さい場合
   
   は交差無し（図-28）。ここで、max(a,b)、min(a,b)はa、bの大きい方、小さい方をとると言う意味である。
   
3. A_x、B_x両方がP_xより大きく、yは一方が小さく一方が大きい場合
   
   は交差有り（図-29）
4. xもyもA、Bの区間にPが挟まれる場合
   
   これは、残りの場合のはずだけど、式-17を計算して
   1. C_x < P_xなら交差しない
   2. C_x ≥ P_xなら交差する

とする。 ただし、

1. AまたはBの少なくともどちらか一方のx座標がPのx座標と等しい場合が見つかったらその時点で内包していると見なして終わる
2. 多角形オブジェクトが開領域の場合、暫定的に頂点を追加して上の手順を行う

とする。

本来なら描画する線（NSBezierPath）の幅を含めて考えなければいけないが、あまり太い線は描かないとしてとりあえず無視することにする。後から見て表現がおかしいようなら修正する。

多角形オブジェクトが開領域と言うのは今回の場合、オブジェクトの一部が視野の外に出ているときしかないので、視野で切り取られた端の点を頂点として追加する。これは描画のときはこの点があってもなくても最終的にクリップされるので「暫定的な頂点」として計算する必要がある。

ああ、めんどくさい。