2D衝突編
その６ 楕円と点の衝突
実に1年4ヶ月ぶりの2D衝突編の更新となりました。円に点が衝突している（含まれている）かどうかは2D衝突編その３で紹介しておりますが、ここで考えるのは「楕円と点」の衝突です。
楕円というのは円を何らかの方向に伸ばした（縮めた）図形です。英語ではエリプス(ellipse)と言います。オーバル(oval)というのも楕円形の意味がありますが、これはどちらかというと卵型の意味が強いようです。「楕円って円みたいなもんでしょ？」と思われるのは大きな間違いです。例えば、ただ円を伸ばしただけなのに、楕円の円周の長さやその面積は解析的に解く事ができなくなります。点との衝突も同じでして、円の中心点と云々というほど簡単な話ではなくなります。
ただ、楕円には1つうれしい性質があります。それは、長径（長い方の径）方向をしゅしゅしゅと縮めて短径と同じ長さにすると円になってしまうという性質です。もちろん短径を長径と同じ長さにしても円になります。楕円を円と同等に考えると、実は点の衝突は一瞬で判定できてしまいます。
この章では楕円と点の衝突についてじっくり説明いたします。
① 楕円の定義
楕円を表す方法は幾つかありますが、ここでは長径と短径で表す事にします。これはX軸Y軸にそれぞれ対応させれば良いかと思います。楕円の制御点はその中心です。楕円の回転は制御点を中心とします。XY軸に平行な楕円形に対するその回転角度をθとして置きましょう。以上の定義を模式的に表したのが下の図です：
② 楕円を円に戻すと衝突がわかる
では衝突判定の原理です。
X軸長がrx、Y軸長がry、そして位置(Cx, Cy）に制御点があってθだけ回転している楕円があるとしましょう。そして、その近辺に判定したい点Pがあるとします。
見て明らかなように、この点は衝突していませんが、楕円のままでこれを判定するのはちょっとめんどくさいのです。そこで今上の絵が上下に良く伸びるゴムの膜にでも描かれているとイメージしまして、うまいこと伸縮を使って楕円を真円にする事を考えてみます。
まず回転しているのが煩わしいので、膜を回転させて軸平行にしてしまいましょう：
この時点も一緒に動く事に注意して下さい。この状態で上下方向に等しく伸ばします：
これで楕円は円になりました。点も一緒に伸びる事をお忘れなく。この円の半径はずばりrxです。そのまま回転させて上下（Y軸方向）に伸ばしただけなので、赤い矢印は何も変わらないためです。この段階で、衝突判定は円と点の関係に落ちましたので、点が衝突しているか否かは言うまでも無く、
で判定できます。distは点P''とC間の距離の事です。
今の変換を行列を使って考えてみると、欲しい式が出てきます。
③ 変換行列の作成
ではこの変換行列を作ってしまいましょう。まず楕円をθだけ逆回転させる前に、制御点を原点に戻す必要があります。いわゆる「オフセット」です。これは単なる平行移動なので、元の点を引き算する行列となります：
「何で3つ目の成分があるの～？」と思われるかもしれませんが、これが無いと平行移動を「掛け算」で表現できません。これで楕円の中心は原点に移動します。
続いて角度θの回転を逆回転させて0度に戻します。これは回転行列に-θを入れれば良いだけです。2Dの回転行列は高校数学でもおなじみのあれです：
cos(-θ)=cos(θ)、sin(-θ)=-sin(θ)である事に注意すれば下の行列が導けます。これで楕円は軸平行に戻りました。最後は真円にするために上下方向（Y軸方向）にスケール変換します。スケールの変換と言うのは単なる数値（スカラー）の掛け算です。掛ける数値は楕円のryとexの比になりますね。例えばrxが10で、ryが2だとすると、ryを5倍しなければ真円になりませんから、縦方向にrx/ry=10/2=5倍スケール変換します：
これで楕円は円になり、点も一緒に移動しました。
以上のオフセット、逆回転、スケール変換の行列を全部まとめる（＝掛け合わせる）と、次のようになります：
この行列変換で「楕円の制御点は原点に移動する」ので、比較点Pと原点の距離を計算すれば比較ができます。ちなみに、上の行列計算を展開して得られる点Pの移動先を計算する式は次の通りです：
こう見ると、何だかわかりやすい形になっている気もします(^-^;。
④ 楕円と点の衝突判定式
上の理屈を基にすると、楕円と点の衝突を判定する関数は例えば次のようになります：
楕円と点の衝突判定式 bool ColEllipsPoint( POINT &p, ELLIPES &Elp )
{
// 点に楕円→真円変換行列を適用
float Ofs_x = p.x - Elp.x;
float Ofs_y = p.y - Elp.y;
float After_x = Ofs_x*cos(Elp.angle) + Ofs_y*sin(Elp.angle);
flpat After_y = Elp.rx/Elp.ry * ( -Ofs_x*sin(Elp.angle) + Ofs_y*cos(Elp.angle) );
// 原点から移動後点までの距離を算出
if( After_x*After_x + After_y*After_y <= Elp.rx*Elp.rx )
return true; // 衝突
return false;
}
POINT構造体とELLIPSE構造体の定義については上ソース内に示す通りなので省略します。
さて、楕円と点の衝突判定をすると、楕円と楕円の判定も当然したくなって来るのですが、これがまた難しい（笑）。ヒントとなるオンライン公開されている論文を見つけましたのでそのURLを示します：
「On-Line Collision-Avoidance Trajectory Planning of Two Planer Robots Based
on Geometric Modeling.(PDF)」
Kao-Shing Hwang and Ming-Dar Tsai. Journal of Information Science Engineering 15, 131-152 (1999).
（幾何学モデルに基づく2つの平面化ロボットのオンライン衝突回避軌道計画）
この論文内に2つの楕円の衝突について式を完全に展開してくれています。機会がありましたら論文を解析して紹介できればと思います。
生物系にはつらいな、これ･･･(T_T)
