KMO2D
Kolizje między-obiektowe w 2D
KMO2D
Kolizje między-obiektowe w 2D
I. Wstęp
3 lata temu na temat kolizji nie miałem żadnego pojęcia. Przyszedł jednak
czas, gdy postanowiłem napisać pierwszą porządną grę i pojawił się,
wtedy problem. Kolizje, zderzenia i fizyka. Na ich temat informacji w
polskim internecie było tak nie wiele (i dalej chyba się to nie zmieniło), że
nawet służba zdrowia w Polsce jest w lepszym stanie. Poszukiwałem, więc
informacji zagranicą, gdzie znalazłem potężny zbiór wiedzy na ten temat,
jednak zapoznanie się z tym wszystkim zajęło mi sporo czasu, gdyż
czytanie takich rzeczy w obcym języku idzie wolniej niż w ojczystym.
W trakcie przechodzenia przez te wszystkie strony, publikacje, artykuły -
męczenia się z nimi - pomyślałem, że można innym ułatwić trochę drogę i
postanowiłem, że kiedyś napisze coś na temat kolizji. Tak oto powstał ten
artykuł. Mam nadzieję, że znajdziecie tu wszytko czego szukacie i
zapraszam do czytania.
II. Podstawy
Jeśli dopiero zaczynasz naukę i nie wiesz nic na temat wektorów to ten
rozdział jest jak najbardziej dla Ciebie. Jeśli jednak jest przeciwnie to
spokojnie możesz go opuścić. Opisane w nim zagadnienia odnoszą się do
podstawowych treści takich jak dodawanie, odejmowanie czy mnożenie
wektorów.
I. Wektory w prostokątnym układzie współrzędnych
I. Wektor
Co to jest wektor? Najprościej mówiąc wektor jest to uporządkowana para
liczb. Jest zapisywany w postaci:
u=[ x ,y ]
gdzie x i y są jego
współrzędnymi w prostokątnym układzie współrzędnych.
Jeśli zaczepimy wektor w jakimś dowolnym punkcie w układzie to
nazywamy go, wtedy wektorem zaczepionym. Współrzędne takiego
wektora obliczamy w następujący sposób:
AB=[ x
b
−x
a
,y
b
−y
a
]
gdzie
x
a
, y
a
to współrzędne punktu A (początek wektora),
x
b
,y
b
to
współrzędne punktu B (koniec wektora).
II. Działania na wektorach
Wektory można do siebie dodawać i od siebie odejmować w wyniku
czego otrzymujemy nowy wektor. Jest to bardzo prosta operacja
polegająca na zsumowaniu odpowiednich współrzędnych (przy
odejmowaniu zmienia się tylko znak). Matematycznie wygląda to
następująco: mamy dwa wektory
u=[ x
u
, y
u
]
i
v=[ x
v
,y
v
]
, a ich
sumą jest wektor
c=[ x
v
x
u
, y
v
y
u
]
(dodawanie) i
c=[ x
v
−x
u
, y
v
−y
u
]
(odejmowanie).
Następną operacją jaką możemy przeprowadzić na wektorach jest ich
mnożenie przez skalar (można je również dzielić przez skalar - dzielenie to
po prostu odwrotność mnożenia). Mnożenie takie można również nazwać
mnożeniem wektora przez liczbę, gdyż skalar jest jakąś konkretną dla nas
liczbą. Działanie to polega na pomnożeniu każdej ze współrzędnych
wektora przez skalar i otrzymaniu nowego wektora.
Matematyka:
Jeśli mamy wektor
u=[ x
u
, y
u
]
i liczbę
k
to ich iloczyn zapisujemy w
postaci
c=u∗k
czyli
c=[ x
u
∗k ,y
u
∗k ]
. Dzielenie przebiega
analogicznie
c=u/k
czyli
c=[ x
u
/k , y
u
/k]
.
III. Normalizacja i długość wektora
Mnożenie i dzielenie przez skalar, można zastosować przy normalizowaniu
wektora, czyli sprowadzaniu jego długości do wartości równej 1. Aby tego
dokonać należy najpierw znaleźć długość wektora, którą można obliczyć
stosując twierdzenia Pitagorasa:
∣
u
∣
=
x
u
2
y
u
2
.
Posiadając juz długość wektora wystarczy podzielić go przez nią i w ten
sposób otrzymać wektor
c=u/
∣
u
∣
.
IV. Iloczyn skalarny dwóch wektorów
Jednym z kolejnych działań jest iloczyn skalarny dwóch wektorów. Wyraża
się on dwoma wzorami (
u , v
- wektory,
∣
u
∣
,
∣
v
∣
- długości wektorów,
- kąt pomiędzy nimi ):
u⋅v=
∣
u
∣
∗
∣
v
∣
∗cos
z geometrii syntetycznej oraz
u⋅v=u
x
∗v
x
u
y
∗v
y
z geometrii analitycznej
Iloczyn skalarny ma bardzo szerokie zastosowanie, sam przekonasz się jak
często będziesz go używać. Oto przykład:
Mamy wektory
u
i
v
. Chcemy obliczyć cosinus kąta pomiędzy nimi.
Jak? Bardzo prosto, jeśli zauważymy, że we wzorze
u⋅v=
∣
u
∣
∗
∣
v
∣
∗cos
można pozbyć się czynnika
∣
u
∣
∗
∣
v
∣
normalizując długość wektorów
(czynnik
∣
u
∣
∗
∣
v
∣
jest wtedy równy 1) . Wzór przyjmuje postać
u⋅v=cos
gdzie jeśli za
u⋅v
podstawimy
u⋅v=u
x
∗v
x
u
y
∗v
y
to
otrzymamy
cos=u
x
∗v
x
u
y
∗v
y
. Wniosek taki, że po
znormalizowaniu obydwu wektorów, ich iloczyn skalarny daje właśnie
liczbę co do wartości równa
cos
.
V. Wektor prostopadły i równoległy – wyznacznik wektorów
Następnym ważnym pojęciem jest wektor prostopadły. Jeśli mamy
wektor
u
to wektor do niego prostopadły
v
możemy obliczyć ze wzoru
v=[−y
u
, x
u
]
lub
v
2
=[y
u
,−x
u
]
. Każdy wektor ma dwa do siebie
prostopadłe i są one równie szeroko stosowane jaki i iloczyn skalarny.
Jeśli wektory mogą być prostopadłe to mogą pewnie być i równoległe. Jak
to sprawdzić? Wektory są równoległe gdy mają ten sam kierunek
(znajdują się na jednej prostej - w przypadku wektorów zaczepionych
obliczamy przed ich porównaniem współrzędne wektora swobodnego). Co
nam to daje? Wiemy dzięki temu, że wektory są równoległe, gdy pierwszy
pomnożony przez jakąś liczbę rzeczywistą daje drugi lub odwrotnie.
Matematycznie wygląda to następująco:
u∥v ⇔ ∃
k ∈R
u=k∗v ∨ v=k∗u
(wektor u jest równoległy do v, wtedy i tylko wtedy, gdy istnieje takie k
należące do liczb rzeczywistych, że
u=k∗v
lub
v=k∗u
).
Zamiast jednak korzystać z tej zależności, można sprawdzić czy wektory
są równoległe w inny sposób. Można obliczyć wyznacznik wektorów i
jeśli będzie on równy 0, to wektory są równoległe. Jak się oblicza
wyznacznik wektorów? Bardzo prosto. Jeśli mamy wektory
u
i
v
, a
macierz zapisujemy tak:
∣
x
u
y
u
x
v
y
v
∣
to wyznacznik wektorowy obliczamy z
wyznacznika macierzy, czyli następująco:
d u ,v =
∣
x
u
y
u
x
v
y
v
∣
=x
u
y
v
−y
u
x
v
.
Na tym etapie artykułu nie jest ważne co to jest macierz, ani jej
wyznacznik. Na ten temat znajduje się trochę informacji w osobnym
rozdział pt. „Macierze”. Wracajmy jednak do wektorów. Istnieje również
drugi wzór na wartość wyznacznika wektorowego:
∣
d u ,v
∣
=
∣
u
∣
∗
∣
v
∣
∗sinu , v
. Wyznacznik wektorowy ma bardzo
szerokie zastosowanie. Można dzięki niemu obliczy np. sinus kąta
pomiędzy wektorami czy pole trójkąta pomiędzy nimi.
II. Ważne wzory
W dalszej części artykułu bardzo często będziemy korzystać z zawartych w
tym rozdziale informacji.
I. Równanie prostej
Każdy wie jak wygląda linia prosta. Prosta ze względu, iż jest pojęciem
pierwotnym nie posiada definicji. Można ją jednak opisać jako zbiór
punktów spełniających równanie:
AxByC=0
gdzie
A
i
B
to
odpowiednio: współrzędna
x
n
i
y
n
wektora prostopadłego do tej linii
prostej (do normalnej tej prostej),
C
to przesunięcie prostej (to znaczy
odległość prostej od punktu (0,0) osi współrzędnych), a
x
i
y
to
współrzędne punktu ze zbioru. Bardzo ładnie obrazuje nam to rysunek
poniżej:
Aby wyznaczyć współczynniki równania naszej prostej -
A , B ,C
-
potrzebujemy 2 punktów leżących na niej. Współczynniki
A
i
B
obliczamy licząc wektor prostopadły do wektora tworzonego przez nasze 2
punkty, a współczynnik
C
obliczamy przekształcając nasze równanie
AxByC=0
do postaci
−AxBy=C
i podstawiając za
x
i
y
współrzędne któregoś z naszych punktów.
Posiadając równanie konkretnej prostej możemy w prosty sposób
sprawdzić czy dany punkt leży czy nie leży na niej, podstawiając
współrzędne punktu pod odpowiednie zmienne równania czy np. obliczyć
część wspólna dwóch prostych (punkt ich przecięcia, jeśli istnieje). Ważne
jest to, że prosta posiada dwie strony: dodatnią i ujemną (można to
rozumieć jako: coś może być „pod” lub „nad” prostą). Jeśli dla jakiegoś
punktu równanie jest dodatnie to znajduje się on po stronie, na którą
wskazuje wektor normalny tej prostej (analogicznie sytuacja odwrotna).
II. Odległość punktu od prostej
Korzystając z poznanej przed chwilą zależności, możemy wyprowadzić
wzór na odległość punktu od prostej. Nie będę go wyprowadzał sam, tylko
skorzystam z gotowego już wzoru, a dla dociekliwych proponuje wziąć
kartkę, długopis i go przeanalizować. Wzór:
d=
∣
AxByC
∣
A
2
B
2
gdzie d to nasza szukana odległość,
x
i
y
to
współrzędne punktu, a
A , B ,C
to kolejno: współrzędne wektora
prostopadłego do prostej i przesunięcie prostej.
III. Rzuty
Bardzo powszechnie i ogólnie stosowaną przez nas techniką będzie
rzutowanie. Rzutowanie jest to najprościej mówiąc „odzwierciedlenie”
czegoś na czymś np. w rzutowaniu prostopadłym punktu na prostą
otrzymujemy nowy punkt, który leży na tej prostej, a odcinek utworzony
przez oba punkty jest prostopadły do tej prostej.
Opisze tutaj dwa rzutowania: równoległe i prostopadłe (które jest
szczególnym przypadkiem rzutu równoległego).
I. Rzut równoległy punktu na prostą.
Aby dokonać takiego rzutu potrzebujemy punktu i dwóch prostych –
jedną, która wyznaczy nam kierunek rzutu, drugą, na którą będzie
odbywał się rzut punktu. W wyniku takiego rzutowania otrzymamy punkt
będący przecięciem prostej, na która rzutowaliśmy i prostej przechodzącej
przez nasz wcześniejszy punkt, równoległej do prostej wyznaczającej
kierunek.
Gdzie:
n
to prosta wyznaczająca kierunek,
k
prosta, na która
rzutujemy,
P
i
P
1
punkt rzutowany i po rzutowaniu.
Współrzędne punktu po rzutowaniu możemy policzyć następująco:
najpierw obliczamy równanie prostej przechodzącej przez rzutowany punkt
i równoległej do prostej wyznaczającej kierunek (proste równoległe różnią
sie tylko współczynnikiem przesunięcia C), a następnie wyznaczamy punkt
spełniający nowo powstałe równanie i równanie prostej, na którą
rzutujemy. Matematyka: Jeśli punkt rzutowany to
P x
p
, y
p
, równanie
prostej wyznaczającej kierunek to
k : A
k
xB
k
yC
k
=0
, a prostej, na
która rzutujemy
l : A
l
xB
l
yC
l
=0
to:
1. Wyznaczamy równanie prostej równoległej do
k
, przechodzącej
przez punkt
P
(obliczamy nowy współczynnik
C
równania):
C
p
=− A
k
x
p
B
k
y
p
gdzie
C
p
to współczynnik
C
dla nowo
powstałej prostej
r : A
k
xB
k
yC
p
=0
.
2. Wyznaczamy wspólne rozwiązanie dla nowo powstałej prostej i
prostej, na którą rzutujemy:
A
k
xB
k
yC
p
=0
A
l
xB
l
yC
l
=0
.
Po przekształceniu otrzymujemy wzory na współrzędne punktu po
rzutowaniu:
x=
B
k
C
l
−A
l
C
p
A
k
B
l
−A
l
B
k
i
y=
A
l
C
p
−A
k
C
l
A
k
B
l
−A
l
B
k
.
II. Rzut prostopadły punktu na prostą.
Rzut taki oczywiście jest jednym z przypadków rzutu równoległego, więc
wyznaczenie współrzędnych punktu po rzutowaniu można obliczyć z
wcześniej poznanych wzorów. Chciałbym jednak pokazać inny sposób, z
którego my będziemy korzystać w takiej sytuacji.
Istnieje coś takiego jak rzut wektora na wektor. Polega on na
wykorzystaniu pewnej własności iloczynu skalarnego dwóch wektorów.
Załóżmy, że mamy dwa wektory
u
i
v
, z czego
u
chcemy rzutować na
v
. Iloczyn skalarny w przypadku, gdy jeden z wektorów jest wektorem
jednostkowym daje wartości równą długości rzutu wektora
niejednostkowego na wektor jednostkowy. Korzystając z tej własności
iloczynu, możemy wyznaczyć współrzędne wektora
u
po rzutowaniu na
wektor
v
następująco: normalizujemy wektor
v
i mnożymy go przez
wektor
u
, a następnie wartość, która otrzymamy mnoży przez
znormalizowany wektor
v
. Otrzymujemy wektor
u
po rzucie na wektor
v
czyli
u
1
.
Matematyka przedstawia się tak:
d=u⋅
v
∣
v
∣
=
u⋅v
∣
v
∣
- długość rzutu,
u
1
=
v
∣
v
∣
∗d
- wektor po rzutowaniu.
Rzutowanie wektorów możemy wykorzystać przy rzutowaniu prostopadłym
punktu na prosta. Jeśli mamy prosta opisaną za pomocą dwóch punktów i
trzeci punkt, który będziemy rzutować, to można z tych punktów
wyznaczyć wektory tak jak na rysunku poniżej:
Dalej rzutowanie przebiega tak jak przy wektorach z jedna różnicą: należy
dodać do nowo powstałego wektora punkt A (wektor należy zaczepić w
tym punkcie i traktować jak punkt).
III. Najbliższy punkt na prostej i odcinku.
Rzut prostopadły punktu na prostą możemy wykorzystać przy obliczaniu
najbliższego punktu na prostej, a także najbliższego punktu na
odcinku. O tyle jak obliczenie tego pierwszego to po prostu normalny
rzut, to z tym drugim sprawa się komplikuje o jedną rzecz. Punkt po
zrzutowaniu może nie znajdować się pomiędzy końcami odcinka, wiec
zanim obliczymy rzut trzeba sprawdzić ten fakt. Jeśli nie leży, jest to jeden
z końców odcinka, jeśli przeciwnie to jest to punkt po zrzutowaniu. Jak
więc sprawdzić czy punkt leży pomiędzy końcami odcinka? Zauważ, że
przy rzucie wektora na wektor otrzymujemy długość rzutu. „Długość”
rzutu może być ujemna, jeśli wektory maja różne zwroty. Wykorzystajmy,
więc ten fakt.
Rysunek po lewej przedstawia sytuacje, gdy mnożąc wektor
AP
i wektor
AB
otrzymamy wartość ujemną (widać, że najbliższym punktem na
odcinku
AB
dla punktu
P
jest punkt
A
). Rysunek po prawej
przedstawia sytuacje, gdy mnożąc wektor
AP
i wektor
AB
otrzymamy
wartość większą niż długość odcinka
AB
(widać, że najbliższym punktem
na odcinku
AB
dla punktu
P
jest punkt
B
). Szukając, więc
najbliższego punktu na odcinku, należy najpierw sprawdzić czy wynik
iloczynu skalarnego wektorów
AP
i
AB
jest większy od
0
oraz
mniejszy od długości odcinka
AB
. Jeśli spełnia obydwa warunki, to jest
to po prostu rzut punktu na prostą, na której leży nasz odcinek. Jeśli nie i
jest on mniejszy lub równy
0
, to najbliższym punktem jest punkt
A
odcinka, a jeśli jest on większy od
0
, ale mniejszy od długości odcinka
AB
, to jest to punkt
B
odcinka.
Do sprawdzenia czy punkt po zrzutowaniu leży pomiędzy końcami odcinka
AB
, można również wykorzystać właściwości kątów
PAB
i
ABP
.
Nie będę, jednak tłumaczył jak. Pozostawiam to już do wglądu we
własnym zakresie.
IV. Obroty
Obracanie figur nie jest jakoś bezpośrednio związane z kolizjami, jednak
może się przydać. Istnieją dwa obroty: wokół środka układu
współrzędnych oraz wokół punktu (de facto ten pierwszy jest po prostu
przypadkiem tego drugiego). Nie ma się w sumie nad czym za bardzo
rozpisywać - obracanie punktu jest bardzo proste do wyobrażenia i mamy
tylko dwa równie proste wzory.
I. Obrót wokół środka układu współrzędnych
Obrót wokół środka układu współrzędnych wygląda następująco:
gdzie:
B
i
B
1
to punkt przed i po obrocie, a
to kąt o jaki obracamy.
Aby w tym przypadku obliczyć współrzędne punktu po obrocie korzystamy
z tych wzorów:
x
1
=x∗cos−y∗sin
i
y
1
=x∗siny∗cos
gdzie:
to kąt obrotu,
x
1
i
y
1
to współrzędne punkt po obrocie, a
x
i
y
przed nim.
II. Obrót wokół punktu
Obrót wokół punktu nie różni się niczym od obrotu wokół środka układu
współrzędnych, z tym, że zanim przystąpimy do obracania należy cofnąć
wszystkie punkty o współrzędne punktu wokół którego obracamy, a po
obliczeniu obrotu dodać te współrzędne z powrotem.
gdzie:
P
to punkt wokół, którego kręcimy,
B
i
B
1
to punkt przed i po
obrocie,
to kąt o jaki obracamy, a
u
to ten wektor, o który cofamy
(ma współrzędne równe punktowi
P
). Wzory zmienią sie tylko trochę:
x
1
= x−x
u
∗cosx
u
−y−y
u
∗siny
u
i
y
1
=x−x
u
∗sinx
u
y−y
u
∗cosy
u
gdzie:
to kąt obrotu,
x
u
i
y
u
to współrzędne wektora
u
,
x
1
i
y
1
to współrzędne punkt po obrocie, a
x
i
y
przed nim.