動く円と動く線分の衝突判定

[SUE]

毎度お世話になっております。今回はかなり数学寄りの質問です。

僕が今行いたいのは、図のような、２次元で直線的に動く円と両端が自由に動く線分とが初めて接する点を求めることです。そこでまず、このサイト等を参考に考えてみました。文字の置き方・言葉の使い方は優しく指摘してください。

0≦t≦1とし、線分のベクタをLtで表す。同様に、円の中心をOtと表す。またOtからLtへの垂線のベクタをHtとおく。
このとき、|Ht| = 円の半径rとなるtの内、最も小さいものが求めるべき点である。

・・・などと考えてみたのですが、途中で楕円が出てきたりして自分の数学力では無理がありました。どうすれば求まるのでしょうか。

ただし、あくまでこれは理想であって、ゲーム中にこれを計算するのは無理がある・あるいは3次式をどうしても解く必要がある（僕がついていけないので）ということであれば、
妥協案（円を点にしたり、線分は動かないとしたり）を幾つか示していただいて、その中から選びたいと思います。もちろん題のとおりであれば最高ですが・・・

[beatle]

円と線分が衝突するかどうかなら、もっと簡単に、円の中心と線分との距離が円の半径以下かどうか、を判定すればいいと思います。
点と直線の距離は割と簡単に求まります。
このやり方は、線分が、直線と円の接点に届かないくらい偏ってるとか短いとき、対応できませんね。（実際には衝突してないのに衝突判定が出てしまう）

[nullptr]

参照されているサイトの
http://marupeke296.com/COL_2D_No5_PolygonToCircle.html
を参考にすればいいのではないでしょうか

[GRAM]

実例を挙げるのに若干苦労しましたが、直線で考えたとしても、
簡単な思考実験により最低でも時間tの4次式になると考えられます。
（画像参照）
（ちょっとした手計算ではｔの6次の項が出てきたので、もっと複雑な解があるのかもしれません。）


ということで、両方移動している限りではちょっと難しいでしょう。
ある瞬間を絵にとって、当たっているかを判定するだけなら問題はもっとずっと簡単です。
http://dixq.net/forum/blog.php?u=240&b=2728
この辺で自分が返信したやり方があります。

[SUE]

>>beatleさん
>>loweさん
返信ありがとうございます。ですが、静止した物体の場合は僕も承知しておりました。それが動いた場合を考えたかったのですが、説明不足で申し訳ありません。
リベンジにと思い書き加えた図を添付しました。

>>GRAMさん
計算までありがとうございます。やはり無理がありそうですか。図のPtを見る限り曲線になるのかなーとは思っていましたが、そこまで複雑だとは思っていませんでした。

一つお聞きしてもいいでしょうか。図の線分の左側の端を点Ｑ，逆をＲとします。ここでＱをＱ_０で固定し、ＲとＯの動きからベクタAを引く・・・という方法は使えますか。
使えるならＬの掃く領域が三角形になり簡単になるような・・・ですが、これでも三次式は必須になりそうな気がします。どうでしょうか。

無理ならば、とりあえず線分を静止させた方法を考えます。

[GRAM]

一つお聞きしてもいいでしょうか。図の線分の左側の端を点Ｑ，逆をＲとします。ここでＱをＱ_０で固定し、ＲとＯの動きからベクタAを引く・・・という方法は使えますか。
使えるならＬの掃く領域が三角形になり簡単になるような・・・ですが、これでも三次式は必須になりそうな気がします。どうでしょうか。

無理ならば、とりあえず線分を静止させた方法を考えます。

いっそのことなので、計算手法を提示しておきます。
円の中心の速度ベクトルvrを各線分の端点より減算し、
さらに、円の中心が座標系の中心に来るよう平行移動を行います。

この時点で問題は

「移動する線分と原点との距離がある値ｒになるときの時刻tを求める」というものに落とし込めます。

さらに線分では難しいので、問題を簡単にするため、線分を移動直線にとして計算します。
（つまり、移動する2点を通る直線と、原点との距離がrになるときの時刻tを求める）

端点の一つをP、もう一つをQとし、
それぞれの移動速度をvp,vqとすれば、

それぞれの最初にいた位置をP0,Q0として、

P=P0+t*vp, Q=Q0+t*vqとなり、

PQと原点Oとの距離Dは、P,Qが一時独立であることからD=aP+bQ、(a+b=1)　D・PQ=0より
定まります。

あとはD²=距離(=円の半径)R²となるような時刻tを求めればいいわけで、

これは、未知数a,b,t式が３つあることから方程式を組むことができます。
まぁこれを解くのが大変なんですけどね

ちなみにSUEさんの図だと、一般的な場合ではありません。
円を線分が「1度しか」通過しないような特殊な場合だけでは、すべてのパターンを列挙したことにならないのです・・・
（自分の奴は2回通過しています。ほかにもあるかもしれませんが、「接する」という条件にあう時刻が「少なくとも4つある場合がある」
という事実だけで、問題が「4次式以上の方程式」に帰結されることがわかります）

[SUE]

ううむ・・・なんとなく判りました（←判ってない）。
とにかくこのやり方は無理そうですね。別の方法を考えます・・・が、よろしければ計算が楽になるヒントを頂けると喜びます。

それでは、トピックのタイトルから外れてしまうのでこれで一旦解決とします。わざわざ有り難うございました。