Lingkaran di dalam lingkaran tabrakan

Di salah satu proyek saya, saya memiliki area permainan dalam bentuk lingkaran. Di dalam lingkaran ini, lingkaran kecil lainnya bergerak. Yang ingin saya lakukan adalah menjaga lingkaran kecil agar tidak bergerak di luar lingkaran yang lebih besar. Di bawah ini Anda dapat melihat bahwa dalam bingkai 2 lingkaran kecil sebagian di luar, saya perlu cara untuk memindahkannya kembali tepat sebelum akan pindah ke luar. Bagaimana ini bisa dilakukan?

Juga, saya membutuhkan titik tumbukan di sepanjang busur lingkaran besar sehingga saya dapat memperbarui kecepatan lingkaran kecil itu. Bagaimana cara menghitung poin ini?

Apa yang ingin saya lakukan adalah sebelum memindahkan lingkaran kecil, saya memprediksi posisi berikutnya dan jika berada di luar saya menemukan waktu tabrakan antara t = 0 dan t = 1 (t = 1 langkah waktu penuh). Jika saya memiliki waktu t tabrakan maka saya hanya memindahkan lingkaran kecil selama t bukannya langkah waktu penuh. Tetapi sekali lagi, masalahnya adalah saya tidak tahu cara mendeteksi pada saat itu tabrakan terjadi ketika datang ke dua lingkaran dan satu berada di dalam yang lain.

EDIT:

Contoh titik tumbukan (hijau) yang ingin saya temukan. Mungkin gambarnya sedikit salah tetapi Anda mendapatkan idenya.

Mari kita asumsikan lingkaran besar memiliki pusat Adan jari R- jari dan lingkaran kecil memiliki pusat Bdan jari r- jari bergerak menuju lokasi C.

Ada cara yang elegan untuk menyelesaikan masalah ini, menggunakan jumlah Minkovski (pengurangan, sebenarnya): ganti cakram jari R- jari dengan cakram jari-jari R-r, dan cakram jari r- jari dengan cakram jari-jari 0, yaitu. titik sederhana yang terletak di B. Masalahnya menjadi masalah persimpangan garis-lingkaran.

Anda kemudian hanya perlu memeriksa apakah jarak AClebih kecil dari R-r. Jika ya, lingkaran tidak bertabrakan. Jika lebih besar, hanya menemukan titik Dpada BCpada jarak R-rdari Adan ini adalah lokasi baru pusat lingkaran kecil Anda. Ini sama dengan menemukan ksedemikian rupa sehingga:

  vec(BD) = k*vec(BC)
and
  norm(vec(AD)) = R-r

Mengganti vec(AD)dengan vec(AB) + vec(BD)memberi:

AB² + k² BC² + 2k vec(AB).vec(BC) = (R-r)²

Asalkan posisi awal berada di dalam lingkaran besar, persamaan kuadrat ini kmemiliki satu akar positif. Berikut ini cara menyelesaikan persamaan, dalam pseudocode:

b = - vec(AB).vec(BC) / BC²    // dot product
c = (AB² - (R-r)²) / BC²
d = b*b - c
k = b - sqrt(d)
if (k < 0)
    k = b + sqrt(d)
if (k < 0)
    // no solution! we must be slightly out of the large circle

Dengan nilai ini k, pusat baru lingkaran kecil adalah Dsedemikian rupa BD = kBC.

Sunting : tambahkan solusi persamaan kuadrat

Katakanlah lingkaran besar itu lingkaran A dan lingkaran kecil itu lingkaran B.

Periksa untuk melihat apakah B ada di dalam A:

distance = sqrt((B.x - A.x)^2 + (B.y - A.y)^2))
if(distance > A.Radius + B.Radius) { // B is outside A }

Jika dalam frame n-1B berada di dalam A dan dalam frame nB di luar A dan waktu antara frame tidak terlalu besar (alias B tidak bergerak terlalu cepat) kita dapat memperkirakan titik tabrakan dengan hanya menemukan koordinat Cartesian dari B relatif ke A:

collision.X = B.X - A.X;
collision.Y = B.Y - A.Y;

Kami kemudian dapat mengonversi poin ini ke sudut:

collision.Normalize(); //not 100% certain if this step is necessary     
radians = atan2(collision.Y, collision.X)

Jika Anda ingin tahu lebih tepat pada apa tB di luar A untuk pertama kalinya Anda bisa melakukan persimpangan lingkaran-ray setiap frame dan kemudian membandingkan jika jarak dari B ke titik tabrakan lebih besar maka jarak B dapat melakukan perjalanan mengingat itu kecepatan saat ini. Jika demikian, Anda dapat menghitung waktu tumbukan yang tepat.

Biarkan (Xa, Ya) posisi lingkaran besar dan jari-jari R, dan (Xb, Yb) posisi lingkaran kecil dan jari-jari r.

Anda dapat memeriksa apakah kedua lingkaran ini bertabrakan jika

DistanceTest = sqrt(((Xa - Xb) ^ 2) + ((Ya - Yb) ^ 2)) >= (R - r)

Untuk mengetahui posisi tabrakan, temukan momen waktu yang tepat ketika lingkaran bertabrakan, dengan menggunakan pencarian biner tetapi dengan sejumlah langkah tetap. Bergantung pada bagaimana permainan Anda dibuat, Anda dapat mengoptimalkan bagian kode ini (saya memberikan solusi ini untuk tidak tergantung pada bagaimana bola kecil berperilaku. Jika memiliki akselerasi konstan, atau kecepatan konstan, bagian kode ini dapat dioptimalkan dan diganti dengan formula sederhana).

left = 0 //the frame with no collision
right = 1 //the frame after collision
steps = 8 //or some other value, depending on how accurate you want it to be
while (steps > 0)
    checktime = left + (right - left) / 2
    if DistanceTest(checktime) is inside circle //if at the moment in the middle of the interval [left;right] the small circle is still inside the bigger one
        then left = checktime //the collision is after this moment of time
        else right = checktime //the collision is before
    steps -= 1
finaltime = left + (right - left) / 2 // the moment of time will be somewhere in between, so we take the moment in the middle of interval to have a small overall error

Setelah Anda mengetahui waktu tumbukan, hitung posisi kedua lingkaran pada waktu terakhir dan titik tumbukan akhir adalah

CollisionX = (Xb - Xa)*R/(R-r) + Xa
CollisionY = (Yb - Ya)*R/(R-r) + Ya

Saya telah mengimplementasikan demo bola memantul di jsfiddle menggunakan algoritma yang dijelaskan oleh Sam Hocevar :

http://jsfiddle.net/klenwell/3ZdXf/

Inilah javascript yang mengidentifikasi titik kontak:

find_contact_point: function(world, ball) {
    // see https://gamedev.stackexchange.com/a/29658
    var A = world.point();
    var B = ball.point().subtract(ball.velocity());
    var C = ball.point();
    var R = world.r;
    var r = ball.r;

    var AB = B.subtract(A);
    var BC = C.subtract(B);
    var AB_len = AB.get_length();
    var BC_len = BC.get_length();

    var b = AB.dot(BC) / Math.pow(BC_len, 2) * -1;
    var c = (Math.pow(AB_len, 2) - Math.pow(R - r, 2)) / Math.pow(BC_len, 2);
    var d = b * b - c;
    var k = b - Math.sqrt(d);

    if ( k < 0 ) {
        k = b + Math.sqrt(d);
    }

    var BD = C.subtract(B);
    var BD_len = BC_len * k;
    BD.set_length(BD_len);

    var D = B.add(BD);
    return D;
}