algorithm - 円-円衝突予測

Question

2つの円が互いに交差しているかどうかを確認する方法を知っています。ただし、円の動きが速すぎて、次のフレームでの衝突を回避してしまうことがあります。

この問題に対する私の現在の解決策は、前の位置と現在の位置の間の円と円の衝突を任意の回数チェックすることです。

2つの円が衝突するのにかかる時間を数学的に見つける方法はありますか？その時間の値を取得できれば、その時点の位置に円を移動し、その時点でそれらを衝突させることができます。

編集：一定速度

Answer 1

円の動きは直線的だと思います。Ca = Oa + t*Da円Aの中心の位置がベクトル方程式で与えられるとしましょう。

Ca = (Cax, Cay)は現在の位置
Oa = (Oax, Oay)、は開始位置
t、経過時間
Da = (Dax, Day)は単位時間（速度）あたりの変位です。

サークルBの中心についても同様ですCb = Ob + t*Db。

||Ca - Cb|| = (ra + rb)次に、ここでraとrbがそれぞれ円AとBの半径であるようなtを見つけたいと思います。

両側を二乗する：
||Ca-Cb||^2 = (ra+rb)^2
そして拡大する：
(Oax + t*Dax - Obx - t*Dbx)^2 + (Oay + t*Day - Oby - t*Dby)^2 = (ra + rb)^2

そこから、tについて解くことができる2次多項式を取得する必要があります（存在する場合）。

Answer 2

AndrewDurwardの優れた答えの方程式を解く方法は次のとおりです。

値をプラグインするだけで、一番下までスキップできます。

(Oax + t*Dax - Obx - t*Dbx)^2 + (Oay + t*Day - Oby - t*Dby)^2 = (ra + rb)^2


(Oax * (Oax + t*Dax - Obx - t*Dbx) + t*Dax * (Oax + t*Dax - Obx - t*Dbx)
 - Obx * (Oax + t*Dax - Obx - t*Dbx) - t*Dbx * (Oax + t*Dax - Obx - t*Dbx))
+
(Oay * (Oay + t*Day - Oby - t*Dby) + t*Day * (Oay + t*Day - Oby - t*Dby)
 - Oby * (Oay + t*Day - Oby - t*Dby) - t*Dby * (Oay + t*Day - Oby - t*Dby))
=
(ra + rb)^2


Oax^2 + (Oax * t*Dax) - (Oax * Obx) - (Oax * t*Dbx)
 + (t*Dax * Oax) + (t*Dax)^2 - (t*Dax * Obx) - (t*Dax * t*Dbx)
 - (Obx * Oax) - (Obx * t*Dax) + Obx^2 + (Obx * t*Dbx)
 - (t*Dbx * Oax) - (t*Dbx * t*Dax) + (t*Dbx * Obx) + (t*Dbx)^2
+
Oay^2 + (Oay * t*Day) - (Oay * Oby) - (Oay * t*Dby)
 + (t*Day * Oay) + (t*Day)^2 - (t*Day * Oby) - (t*Day * t*Dby)
 - (Oby * Oay) - (Oby * t*Day) + Oby^2 + (Oby * t*Dby)
 - (t*Dby * Oay) - (t*Dby * t*Day) + (t*Dby * Oby) + (t*Dby)^2
=
(ra + rb)^2


t^2 * (Dax^2 + Dbx^2 - (Dax * Dbx) - (Dbx * Dax)
       + Day^2 + Dby^2 - (Day * Dby) - (Dby * Day))
+
t * ((Oax * Dax) - (Oax * Dbx) + (Dax * Oax) - (Dax * Obx)
      - (Obx * Dax) + (Obx * Dbx) - (Dbx * Oax) + (Dbx * Obx)
      + (Oay * Day) - (Oay * Dby) + (Day * Oay) - (Day * Oby)
      - (Oby * Day) + (Oby * Dby) - (Dby * Oay) + (Dby * Oby))
+
Oax^2 - (Oax * Obx) - (Obx * Oax) + Obx^2
  + Oay^2 - (Oay * Oby) - (Oby * Oay) + Oby^2 - (ra + rb)^2
=
0

これで、標準形の2次方程式になります。

ax2 + bx + c = 0

このように解決しました：

x = (−b ± sqrt(b^2 - 4ac)) / 2a       // this x here is t

どこ -

a = Dax^2 + Dbx^2 + Day^2 + Dby^2 - (2 * Dax * Dbx) - (2 * Day * Dby)

b = (2 * Oax * Dax) - (2 * Oax * Dbx) - (2 * Obx * Dax) + (2 * Obx * Dbx)
     + (2 * Oay * Day) - (2 * Oay * Dby) - (2 * Oby * Day) + (2 * Oby * Dby)

c = Oax^2 + Obx^2 + Oay^2 + Oby^2
    - (2 * Oax * Obx) - (2 * Oay * Oby) - (ra + rb)^2

tが存在する（衝突が発生する）場合-

(a != 0) && (b^2 >= 4ac)

Answer 3

方向ベクトルと速度を使用して衝突を予測できます。これにより、次のステップと、衝突が発生するタイミング（発生する場合）がわかります。

それを検出するには、ライン交差アルゴリズムをチェックする必要があります...