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

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アバター
SUE
記事: 41
登録日時: 7年前

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

#1

投稿記事 by SUE » 7年前

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

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

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

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

ただし、あくまでこれは理想であって、ゲーム中にこれを計算するのは無理がある・あるいは3次式をどうしても解く必要がある(僕がついていけないので)ということであれば、
妥協案(円を点にしたり、線分は動かないとしたり)を幾つか示していただいて、その中から選びたいと思います。もちろん題のとおりであれば最高ですが・・・
添付ファイル
figure.png
figure.png (1.94 KiB) 閲覧数: 1334 回
pop'n music 20 fantasia ポップンクエストPhase MAX Ⅱ ムラクモ/少年は空を辿る【Power Of Nature】

beatle
記事: 1280
登録日時: 8年前
住所: 埼玉
連絡を取る:

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

#2

投稿記事 by beatle » 7年前

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

アバター
nullptr
記事: 239
登録日時: 7年前

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

#3

投稿記事 by nullptr » 7年前

参照されているサイトの
http://marupeke296.com/COL_2D_No5_PolygonToCircle.html
を参考にすればいいのではないでしょうか
 
 
✜ で C ご ✜
: す + 注 :
¦ か + 文 ¦
?
Is the は :
order C++? ✜
     糸冬   
  ――――――――
  制作・著作 NHK
 
 

アバター
GRAM
記事: 164
登録日時: 9年前
住所: 大阪

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

#4

投稿記事 by GRAM » 7年前

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


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

アバター
SUE
記事: 41
登録日時: 7年前

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

#5

投稿記事 by SUE » 7年前

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

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

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

無理ならば、とりあえず線分を静止させた方法を考えます。
添付ファイル
figure.png
figure.png (3.82 KiB) 閲覧数: 1230 回
pop'n music 20 fantasia ポップンクエストPhase MAX Ⅱ ムラクモ/少年は空を辿る【Power Of Nature】

アバター
GRAM
記事: 164
登録日時: 9年前
住所: 大阪

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

#6

投稿記事 by GRAM » 7年前

SUE さんが書きました: 一つお聞きしてもいいでしょうか。図の線分の左側の端を点Q,逆をRとします。ここでQをQで固定し、RとOの動きからベクタAを引く・・・という方法は使えますか。
使えるならLの掃く領域が三角形になり簡単になるような・・・ですが、これでも三次式は必須になりそうな気がします。どうでしょうか。

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

この時点で問題は

「移動する線分と原点との距離がある値rになるときの時刻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より
定まります。

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

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

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

アバター
SUE
記事: 41
登録日時: 7年前

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

#7

投稿記事 by SUE » 7年前

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

それでは、トピックのタイトルから外れてしまうのでこれで一旦解決とします。わざわざ有り難うございました。
pop'n music 20 fantasia ポップンクエストPhase MAX Ⅱ ムラクモ/少年は空を辿る【Power Of Nature】

閉鎖

“C言語何でも質問掲示板” へ戻る