Autor Wątek: Obliczenie punktu zderzenie 2 kul..  (Przeczytany 3295 razy)

Offline siwy

  • Użytkownik

# Sierpień 01, 2007, 22:08:01
Chcialem obliczyc dokladne miejsce zetkniecia sie 2 kul w ukladzie kartezjanskim (X,Y). Moge obliczyc predkosc kuli i kierunek, w ktorym sie porusza oraz znam jej promien.

PSEUDOKOD:

class kula
{
PolozenieXY[2];
PoprzedniePolozenieXY[2];
Promien;
};


z tych danych licze sobie predkosc i kierunek - zakladam ze kule poruszaja sie ze stala predkoscia po lini prostej.
Chcialbym obliczyc dokladny punkt zderzenia sie kul na podstawie danych poczatkowych (miejsce 2 kul kierunki w ktorych sie poruszaja oraz predkosci) i chcialbym wiedziec jeszcze jakie wspolzedne maja srodku obu kul w chwili zderzenia :)..

Za wszelka pomoc dzienkuje :)
pozdrawiam siwy :P..
PS. naprawde nic ciekawego nie bylo w google z tego co widzialem :PP

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Shelim

  • Użytkownik
    • Homepage

# Sierpień 01, 2007, 22:51:14
Punkt zderzenia leży na prostej łączącej środki obu kul w odległości od środka dowolnej kuli równej promieniowi tej kuli :)

Offline siwy

  • Użytkownik

# Sierpień 01, 2007, 23:11:46
Punkt zderzenia leży na prostej łączącej środki obu kul w odległości od środka dowolnej kuli równej promieniowi tej kuli :)
No fajnie fajnie :D.. Ale to chyba kazdy wie bo to raczej wiedza z podstawowki.... Ja wiem kiedy nastepuje zderzenie - jakie warunki musza byc spelnione.. Ale nie wiem jak obliczyc ten punkt oraz punkty srodkow kul w momecie zderzenia (to bedzie mi potrzebne do dalszych obliczen :P), przy danych wejsciowych jakie podalem w otwierajacym ten temat poscie.

Offline Xion

  • Redaktor
    • xion.log

# Sierpień 01, 2007, 23:14:52
Jeżeli x1(t) opisuje położenie pierwszej kuli, a x2(t) drugiej, to wystarczy rozwiązać równanie:

dist(x1(t), x2(t)) == r1 + r2,

gdzie dist() jest odległością między punktami, a r1 i r2 to promienie obu kul. Mając wyliczony czas t można wyliczyć pozycje środków obu kul w momencie zderzenia i skorzystać z rady Korialtrasha do policzenia punktu zetknięcia kul.

Offline siwy

  • Użytkownik

# Sierpień 01, 2007, 23:24:37
Jeżeli x1(t) opisuje położenie pierwszej kuli, a x2(t) drugiej, to wystarczy rozwiązać równanie:

dist(x1(t), x2(t)) == r1 + r2,

gdzie dist() jest odległością między punktami, a r1 i r2 to promienie obu kul. Mając wyliczony czas t można wyliczyć pozycje środków obu kul w momencie zderzenia i skorzystać z rady Korialtrasha do policzenia punktu zetknięcia kul.

I jak to wlasnie wyliczyc :P... Gdybym juz mial ten t - czas i funkcje opisujace polozenie kuli w zaleznosci od czasu :)...
Jak znasz na to metode Xion to bardzo prosze :).. Z poczatku nie chcialem w to wszystko mieszac czasu ale jak juz padlo :P

// Dla twojej metody Xion trzeba by bylo wymyslac funkcje ruchu dla obu kul i szukac odpowiedniego t i wydaje mi sie ze funkcja szukajaca te t nie mogla by byc funkcja liniowa ale chyba jak juz logarytmiczna :)... Ale moze warto pokombinowac :P...
OFFTOPOWO: Gdyby mialo byc obliczone wiecej zderzen chyba by troszke komputer spowolnilo:P....
« Ostatnia zmiana: Sierpień 01, 2007, 23:38:28 wysłana przez siwy »

Offline Shelim

  • Użytkownik
    • Homepage

# Sierpień 02, 2007, 01:57:44
Chcesz gotowca? Proszę bardzo:

#include <iostream.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

struct POINT
{
    double x, y;
};

struct kula
{
POINT position;
unsigned int r;
};

kula kula1, kula2;

bool CalculateCollisionPoint(kula kula1, kula kula2, POINT *point) // zwraca true jeżeli kule kolidują i umieszcza punkt kolizji w point
{
    if(
        (kula2.position.x-kula1.position.x)*(kula2.position.x-kula1.position.x)
        +
        (kula2.position.y-kula1.position.y)*(kula2.position.y-kula1.position.y)
        >
        (kula1.r+kula2.r)*(kula1.r+kula2.r)
    )
        return false;
    point->x = (kula2.position.x-kula1.position.x)*kula1.r/(kula1.r+kula2.r)+kula1.position.x;
    point->y = (kula2.position.y-kula1.position.y)*kula1.r/(kula1.r+kula2.r)+kula1.position.y;
    return true;
}

int main()
{
    srand(time(NULL));
    while(true)
    {
        cout << "Losowac (y/n)?";
        char c;
        cin >> c;
        if(c=='y' || c=='Y')
        {
            kula1.position.x = rand()%640;
            kula1.position.y = rand()%480;
            kula1.r = rand()%50+100;
            kula2.position.x = rand()%640;
            kula2.position.y = rand()%480;
            kula2.r = rand()%50+100;
            cout << "kula1.position.x = " << kula1.position.x << endl
                 << "kula1.position.y = " << kula1.position.y << endl
                 << "kula1.r = " << kula1.r << endl
                 << "kula2.position.x = " << kula2.position.x << endl
                 << "kula2.position.y = " << kula2.position.y << endl
                 << "kula2.r = " << kula2.r << endl;
            POINT point;
            if(CalculateCollisionPoint(kula1, kula2, &point))
                cout << "Punkt kolizji: (" << point.x << ", " << point.y << ")" << endl;
            else
                cout << "Kule nie koliduja" << endl;
        }
        else
            break;
    }
     return 0;
}

Sprawdzone w Code::Blocks, działa dobrze :)

Na przyszłość, do algorytmów z geometrii przydaje się kartka papieru i ołówek ;) Zastosowałem tutaj twierdzenie Pitagorasa i Talesa :)

RageX

  • Gość
# Sierpień 02, 2007, 04:50:06
To ja nie zaglądając w cudze kody dodam:
Na przyszłość wykonuj ruch po wykonaniu testu i znaniu pozycji najbliższej kolizji. Tak rada praktyczna...

A co do obliczeń... siedziałem "troszkę" nad kolizją swept sfery i sobie ją narazie odpuściłem na etapie kolizji z krawędzią. Ale kolizje kul, kół ze sobą - banał. :P

A teraz jak znaleźć pozycję kolizji (nie wnikam w procedurę kolizji, bardziej mi zależy na logicznym wytłumaczeniu poszczególnych działań, skąd co się bierze, staram się dać wędke):

pitagoras i tyle.
Rzutuje dot produktem pozycje kuli, koła nr2 na wektor velocity. Mnoże ten wektor o tą długość, mam punkt który jest najbliższy środkowi kuli nr2.
To teraz tak...

punkty:
A = środek kuli nr1(tej która jest w ruchu[teoretycznie, bo róznie to sie stosuje, ale nie wnikam])
A' = nasza szukana pozycja kuli w której promienie kul są równe.
B = nasz świeżo powstały punkt z rzutowania
C = środek kuli nr2

Dzięki rzutowaniu, mamy teraz taką fajną własność, kąt ABC, jest kątem prostym...
Odcinek BC jest stały, ruch kuli nr1, nie zmieni długości tego odcinka.
Nasz odcinek AC znamy, ale szukamy A'C - nowego położenia kuli.
Długość A'C jest równa sumie promieni obu kul. To teraz liczymy:

A'C(przeciwprostokątna, suma promieni)
BC(przyprostokątna, odległość naszej kuli nr2 od wektora przesunięcia)
A'B(szukana przyprostokątna)
Pitagoras się kłania.

Offline siwy

  • Użytkownik

# Sierpień 02, 2007, 09:16:47
Chcesz gotowca? Proszę bardzo:

#include <iostream.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

struct POINT
{
    double x, y;
};

struct kula
{
POINT position;
unsigned int r;
};

kula kula1, kula2;

bool CalculateCollisionPoint(kula kula1, kula kula2, POINT *point) // zwraca true jeżeli kule kolidują i umieszcza punkt kolizji w point
{
    if(
        (kula2.position.x-kula1.position.x)*(kula2.position.x-kula1.position.x)
        +
        (kula2.position.y-kula1.position.y)*(kula2.position.y-kula1.position.y)
        >
        (kula1.r+kula2.r)*(kula1.r+kula2.r)
    )
        return false;
    point->x = (kula2.position.x-kula1.position.x)*kula1.r/(kula1.r+kula2.r)+kula1.position.x;
    point->y = (kula2.position.y-kula1.position.y)*kula1.r/(kula1.r+kula2.r)+kula1.position.y;
    return true;
}

int main()
{
    srand(time(NULL));
    while(true)
    {
        cout << "Losowac (y/n)?";
        char c;
        cin >> c;
        if(c=='y' || c=='Y')
        {
            kula1.position.x = rand()%640;
            kula1.position.y = rand()%480;
            kula1.r = rand()%50+100;
            kula2.position.x = rand()%640;
            kula2.position.y = rand()%480;
            kula2.r = rand()%50+100;
            cout << "kula1.position.x = " << kula1.position.x << endl
                 << "kula1.position.y = " << kula1.position.y << endl
                 << "kula1.r = " << kula1.r << endl
                 << "kula2.position.x = " << kula2.position.x << endl
                 << "kula2.position.y = " << kula2.position.y << endl
                 << "kula2.r = " << kula2.r << endl;
            POINT point;
            if(CalculateCollisionPoint(kula1, kula2, &point))
                cout << "Punkt kolizji: (" << point.x << ", " << point.y << ")" << endl;
            else
                cout << "Kule nie koliduja" << endl;
        }
        else
            break;
    }
     return 0;
}

Sprawdzone w Code::Blocks, działa dobrze :)

Na przyszłość, do algorytmów z geometrii przydaje się kartka papieru i ołówek ;) Zastosowałem tutaj twierdzenie Pitagorasa i Talesa :)

To co mowisz jest prawda i Twoj kod jest dobry ale zeby w twoim kodzie wykryc kolizje kule musza nachodzic na siebie (kolidowac). Ja chce zrobic cos innego przewidziec kolizje do przodu mam swoje dane wejsciowe w postaci (predkosc kierunek i promien oraz pozycja poczatkowa kul) i chce na ich podstawie obliczyc wlasnie czy kolizja zajdzie czy nie :).. Nie wiem czy wogole sa gdzies na to jakies wzory albo jakies prawa nie wiem dlatego pytam. Ja dopiero skonczylem ogolniak i maturke napisalem wiec z takich rzeczy jeszcze nic nie wiem :(((..

EDIT\\ Wydaje mi sie ze najlepiej zrozumial mnie Xion jednoczesnie podajac chyba narazie najlepsze rozwiazanie :) thx Xion - jeszcze trzeba ulozyc jakis algorytm zwiezly aby ladnie chodzilo :P..
« Ostatnia zmiana: Sierpień 02, 2007, 09:19:29 wysłana przez siwy »

Offline Xion

  • Redaktor
    • xion.log

# Sierpień 02, 2007, 10:02:09
Jak się ma:
Cytuj
zakladam ze kule poruszaja sie ze stala predkoscia po lini prostej.
do:
Cytuj
Dla twojej metody Xion trzeba by bylo wymyslac funkcje ruchu dla obu kul i szukac odpowiedniego t i wydaje mi sie ze funkcja szukajaca te t nie mogla by byc funkcja liniowa ale chyba jak juz logarytmiczna
?

Przecież jeśli one faktycznie poruszają się w linii prostej ze stałą prędkością, to nie ma tu co wymyślać, bo ich położenie to po prostu:

x(t) = x0 + v * t

a wtedy podane przez mnie równanie jest kwadratowe względem t.

Offline siwy

  • Użytkownik

# Sierpień 02, 2007, 10:38:15
Jak się ma:
Cytuj
zakladam ze kule poruszaja sie ze stala predkoscia po lini prostej.
do:
Cytuj
Dla twojej metody Xion trzeba by bylo wymyslac funkcje ruchu dla obu kul i szukac odpowiedniego t i wydaje mi sie ze funkcja szukajaca te t nie mogla by byc funkcja liniowa ale chyba jak juz logarytmiczna
?

Przecież jeśli one faktycznie poruszają się w linii prostej ze stałą prędkością, to nie ma tu co wymyślać, bo ich położenie to po prostu:

x(t) = x0 + v * t

a wtedy podane przez mnie równanie jest kwadratowe względem t.

Czyli - rozaptruje 2 kule:

PolozenieKuli1[2];
PolozenieKuli2[2];

PolozenieKuli1[0]=x0kuli1+Vxkuli1*t;
PolozenieKuli1[1]=y0kuli1+Vykuli1*t;

PolozenieKuli2[0]=x0kuli2+Vxkuli2*t;
PolozenieKuli2[1]=y0kuli2+Vykuli2*t;

I teraz sprawdzam D - odleglosc miedzy kula 1 i 2 dla poszczegolnych t i gdy wychodzi mi ze te moje D*D == rkuli1*rkuli1 + rkuli2*rkuli2 to jest kolizja :)... Touaj gorzej z optymalizacja :P... Zeby mniej wiecej wiedziec jakie t podstawiac :P..

RageX

  • Gość
# Sierpień 02, 2007, 11:48:09
kurka...na podstawie tego co podałem też można sprawdzić kolizje, wystarczy sprawdzić czy odległość od kolizji jest dłuższa, bądź nie od wektora... a całe t to w zasadzie długość wektora. Ehh, jak nie kumasz co napisałem, to nie pisz, że to nie to o co ci chodzi, po prostu napisz że nie kumasz, albo że ty nie chcesz tego rozumieć, chcesz kodu... a przynajmniej ja tak twoją odpowiedź na moje nocne wypociny zrozumiałem.

Offline siwy

  • Użytkownik

# Sierpień 02, 2007, 11:59:16
kurka...na podstawie tego co podałem też można sprawdzić kolizje, wystarczy sprawdzić czy odległość od kolizji jest dłuższa, bądź nie od wektora... a całe t to w zasadzie długość wektora. Ehh, jak nie kumasz co napisałem, to nie pisz, że to nie to o co ci chodzi, po prostu napisz że nie kumasz, albo że ty nie chcesz tego rozumieć, chcesz kodu... a przynajmniej ja tak twoją odpowiedź na moje nocne wypociny zrozumiałem.

Nie umiem tego sobie wyobrazic :(( moze jakis rysuneczek bys rzucil :P...

Offline skoti

  • Użytkownik

# Sierpień 02, 2007, 13:00:06
kurka...na podstawie tego co podałem też można sprawdzić kolizje, wystarczy sprawdzić czy odległość od kolizji jest dłuższa, bądź nie od wektora... a całe t to w zasadzie długość wektora. Ehh, jak nie kumasz co napisałem, to nie pisz, że to nie to o co ci chodzi, po prostu napisz że nie kumasz, albo że ty nie chcesz tego rozumieć, chcesz kodu... a przynajmniej ja tak twoją odpowiedź na moje nocne wypociny zrozumiałem.
Wydaje mi się że nie chodzi mu o to żeby sprawdzać kolizję z większymi promieniami żeby wcześniej wykryć kolizję tylko poprostu mało rozumie z Twojego kodu ;p



@siwy: jak masz wektor prędkości to dodaj go do każdej pozycji kul przed sprawdzeniem sprawdzaniem kolizji (w ten sposób "przewidzisz" czy po przesunięciu się zdeżą).
Czyli zamiast:
    if(
        (kula2.position.x-kula1.position.x)*(kula2.position.x-kula1.position.x)
        +
        (kula2.position.y-kula1.position.y)*(kula2.position.y-kula1.position.y)
        >
        (kula1.r+kula2.r)*(kula1.r+kula2.r)
    )
Robisz takie coś
POINT punkt = kula2.position+kula2.predkosc - kula1.position+kula1.predkosc;
if( (punkt.x*punkt.x +punkt.y*punkt.y) > (kula1.r+kula2.r)*(kula1.r+kula2.r))

Offline Xion

  • Redaktor
    • xion.log

# Sierpień 02, 2007, 13:43:15
Cytuj
I teraz sprawdzam D - odleglosc miedzy kula 1 i 2 dla poszczegolnych t i gdy wychodzi mi ze te moje D*D == rkuli1*rkuli1 + rkuli2*rkuli2 to jest kolizja Smiley... Touaj gorzej z optymalizacja Tongue... Zeby mniej wiecej wiedziec jakie t podstawiac Tongue..
Że co?! Przecież nie trzeba niczego 'podstawiać i sprawdzać'. Rozwiązać równanie to rozwiązać równanie...

dist(x1(t), x2(t)) == r1 + r2  dla xi(t) = x0i + vi * t,  i = 1 || i =2
sqrt((x01 + v1*t)^2 + (x02 + v2*t)^2) = r1 + r2
(x01 + v1*t)^2 + (x02 + v2*t)^2 = (r1 + r2)^2
x01^2 + 2*v1*t + (v1*t)^2 + x02^2 + 2*v2*t + (v2*t)^2 = (r1 + r2)^2

czyli:

t^2 * (v1^2 + v2^2) + t * 2*(v1+v2) + (x01^2 + x02^2 - (r1 + r2)^2) = 0

Jak mówiłem - równanie kwadratowe; rozwiązać je, wziąć dodatnie rozwiązanie i masz t dla którego zachodzi zderzenie. Podstawić do x1(t) i x2(t) i masz położenia obu kul w momencie zderzenia. Żadnego próbowania na ślepo, czysta matma ;p

Offline siwy

  • Użytkownik

# Sierpień 02, 2007, 13:52:11
Cytuj
I teraz sprawdzam D - odleglosc miedzy kula 1 i 2 dla poszczegolnych t i gdy wychodzi mi ze te moje D*D == rkuli1*rkuli1 + rkuli2*rkuli2 to jest kolizja Smiley... Touaj gorzej z optymalizacja Tongue... Zeby mniej wiecej wiedziec jakie t podstawiac Tongue..
Że co?! Przecież nie trzeba niczego 'podstawiać i sprawdzać'. Rozwiązać równanie to rozwiązać równanie...

dist(x1(t), x2(t)) == r1 + r2  dla xi(t) = x0i + vi * t,  i = 1 || i =2
sqrt((x01 + v1*t)^2 + (x02 + v2*t)^2) = r1 + r2
(x01 + v1*t)^2 + (x02 + v2*t)^2 = (r1 + r2)^2
x01^2 + 2*v1*t + (v1*t)^2 + x02^2 + 2*v2*t + (v2*t)^2 = (r1 + r2)^2

czyli:

t^2 * (v1^2 + v2^2) + t * 2*(v1+v2) + (x01^2 + x02^2 - (r1 + r2)^2) = 0

Jak mówiłem - równanie kwadratowe; rozwiązać je, wziąć dodatnie rozwiązanie i masz t dla którego zachodzi zderzenie. Podstawić do x1(t) i x2(t) i masz położenia obu kul w momencie zderzenia. Żadnego próbowania na ślepo, czysta matma ;p

DZIEKI XION :****** :D:D 

EDIT\\ Oki no to sie wszystko zgadza gdy kule poruszaja sie po lini prostej i obie kule sa na tej samej prostej.. Ja chcialem takie zalozenie moze nie dokonca mnie zrozumiales Xion ze Jednak kule jest na jednej prostej a druga kula na drugiej prostej i obie kule sie poruszaja ze stala preskoscia z tym ze predkosc kazdej z kul moze byc inna :).. Dlatego tutaj by jeszcze trezba bylo Y jakos wyliczyc :).. Ale to juz sam pokombinuje..

Co do wydluzania o wektor ruchu kuli i sprawdzaniu w ten sposob czy zajdzie kolizja to juz to znalem ale nie zrozumialem o co chodzilo ://.. Mi jest poptrzebne obliczenie wczesniejsze poniewaz moze sie zdarzyc ze kule z jednaj klatki na druga bede po roznych stronach siebie a kolizja nie zostanie wykryta bo nie bedzie momentu kiedy kule beda na siebie nachodzic :)..
« Ostatnia zmiana: Sierpień 02, 2007, 14:38:50 wysłana przez siwy »