2D-Kollisionserkennung
Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
| [unmarkierte Version] | [gesichtete Version] |
(→Kollision Rechteck-Kreis (2D)) |
K (Anpassung für MathJax) |
||
| (4 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt) | |||
| Zeile 165: | Zeile 165: | ||
Wenn man nun die zwei Geraden mithilfe dieser Formel beschreibt und sie gleichsetzt (<math>P_a = P_b</math>), bekommt man folgende Gleichungen für <math>x</math> und <math>y</math> der Punkte <math>P_a</math> und <math>P_b</math>: | Wenn man nun die zwei Geraden mithilfe dieser Formel beschreibt und sie gleichsetzt (<math>P_a = P_b</math>), bekommt man folgende Gleichungen für <math>x</math> und <math>y</math> der Punkte <math>P_a</math> und <math>P_b</math>: | ||
| − | : <math> | + | : <math>\begin{align} x_{A_1} + u_a(x_{A_2} - x_{A_1}) & = x_{B_1} + u_b(x_{B_2} - x_{B_1}) \\ y_{A_1} + u_a(y_{A_2} - y_{A_1}) & = y_{B_1} + u_b(y_{B_2} - y_{B_1}) \end{align} </math> |
| − | \begin{align} | + | |
| − | x_{A_1} + u_a(x_{A_2} - x_{A_1}) & = x_{B_1} + u_b(x_{B_2} - x_{B_1}) \\ | + | |
| − | y_{A_1} + u_a(y_{A_2} - y_{A_1}) & = y_{B_1} + u_b(y_{B_2} - y_{B_1}) | + | |
| − | \end{align} | + | |
| − | </math> | + | |
Diese Gleichungen werden nun nach <math>u_a</math> und <math>u_b</math> aufgelöst: | Diese Gleichungen werden nun nach <math>u_a</math> und <math>u_b</math> aufgelöst: | ||
| − | : <math> | + | : <math>\begin{align} u_a & = \frac{(x_{B_2} - x_{B_1})(y_{A_1} - y_{B_1}) - (y_{B_2} - y_{B_1})(x_{A_1} - x_{B_1})}{(y_{B_2} - y_{B_1})(x_{A_2} - x_{A_1})-(x_{B_2} - x_{B_1})(y_{A_2} - y_{A_1})} \\ u_b & = \frac{(x_{A_2} - x_{A_1})(y_{A_1} - y_{B_1}) - (y_{A_2} - y_{A_1})(x_{A_1} - x_{B_1})}{(y_{B_2} - y_{B_1})(x_{A_2} - x_{A_1})-(x_{B_2} - x_{B_1})(y_{A_2} - y_{A_1})} \end{align}</math> |
| − | \begin{align} | + | |
| − | u_a & = \frac{(x_{B_2} - x_{B_1})(y_{A_1} - y_{B_1}) - (y_{B_2} - y_{B_1})(x_{A_1} - x_{B_1})}{(y_{B_2} - y_{B_1})(x_{A_2} - x_{A_1})-(x_{B_2} - x_{B_1})(y_{A_2} - y_{A_1})} \\ | + | |
| − | u_b & = \frac{(x_{A_2} - x_{A_1})(y_{A_1} - y_{B_1}) - (y_{A_2} - y_{A_1})(x_{A_1} - x_{B_1})}{(y_{B_2} - y_{B_1})(x_{A_2} - x_{A_1})-(x_{B_2} - x_{B_1})(y_{A_2} - y_{A_1})} | + | |
| − | \end{align} | + | |
| − | </math> | + | |
Man beachte nun die Nenner der beiden Gleichungen, denn sie sind identisch. Wenn nun der Nenner gleich Null ist, so sind <math>u_a</math> und <math>u_b</math> undefiniert, also sind die beiden Geraden parallel zueinander. Wenn die Geraden dann nicht identisch sind, liegt keine Kollision vor. Der Einfachheit halber ignorieren wir den Fall der identischen Geraden und geben "''keine Kollision''" aus. Beim Rechnen mit Fließkommazahlen muss beachtet werden, dass ein Vergleich mit Null auf Grund von Rechenungenauigkeiten nicht empfehlenswert ist. Darum sollte ein kleiner Grenzwert ε (im Code als Konstante <code>EPSILON</code> dargestellt) gewählt werden, unterhalb dessen die Geraden als parallel angenommen werden. Ein möglicher Wert wäre z.B. <math>10^{-8}</math>. | Man beachte nun die Nenner der beiden Gleichungen, denn sie sind identisch. Wenn nun der Nenner gleich Null ist, so sind <math>u_a</math> und <math>u_b</math> undefiniert, also sind die beiden Geraden parallel zueinander. Wenn die Geraden dann nicht identisch sind, liegt keine Kollision vor. Der Einfachheit halber ignorieren wir den Fall der identischen Geraden und geben "''keine Kollision''" aus. Beim Rechnen mit Fließkommazahlen muss beachtet werden, dass ein Vergleich mit Null auf Grund von Rechenungenauigkeiten nicht empfehlenswert ist. Darum sollte ein kleiner Grenzwert ε (im Code als Konstante <code>EPSILON</code> dargestellt) gewählt werden, unterhalb dessen die Geraden als parallel angenommen werden. Ein möglicher Wert wäre z.B. <math>10^{-8}</math>. | ||
| Zeile 336: | Zeile 326: | ||
Nun setzen wir <math>\vec x(t)</math> in die Kreisgleichung ein. Wir bringen die Gleichung in die richtige Form für die [http://de.wikipedia.org/wiki/Quadratische_Gleichung#p-q-Formel p-q-Formel], so dass wir nach <math>t</math> auflösen können: | Nun setzen wir <math>\vec x(t)</math> in die Kreisgleichung ein. Wir bringen die Gleichung in die richtige Form für die [http://de.wikipedia.org/wiki/Quadratische_Gleichung#p-q-Formel p-q-Formel], so dass wir nach <math>t</math> auflösen können: | ||
| − | : <math>\begin{align} | + | : <math>\begin{align} \left( {\vec x}(t) - \vec c \right) ^2 &= r^2 \\ \left( (\vec o + t \cdot \vec d) - \vec c \right)^2 &= r^2 \\ (\vec o + t \cdot \vec d)^2 - 2 \cdot (\vec o + t \cdot \vec d) \cdot \vec c + {\vec c}^2 &= r^2 \\ {\vec o}^2 + 2t \cdot \vec o \cdot \vec d + t^2 \cdot {\vec d}^2 - 2 \cdot \vec o \cdot \vec c - 2t \cdot \vec d \cdot \vec c + {\vec c}^2 &= r^2 \\ t^2 {\vec d}^2 + t (2 \cdot \vec o \cdot \vec d - 2 \cdot \vec d \cdot \vec c) + {\vec o}^2 - 2 \cdot \vec o \cdot \vec c + {\vec c}^2 - r^2 &= 0 \\ t^2 {\vec d}^2 + t (2 \cdot \vec o \cdot \vec d - 2 \cdot \vec d \cdot \vec c) + (\vec o - \vec c)^2 - r^2 &= 0 \\ t^2 + t \left( \frac{2 \cdot \vec o \cdot \vec d - 2 \cdot \vec d \cdot \vec c}{{\vec d}^2} \right) + \frac{(\vec o - \vec c)^2 - r^2}{{\vec d}^2} &= 0 \end{align}</math> |
| − | \left( {\vec x}(t) - \vec c \right) ^2 &= r^2 \\ | + | |
| − | \left( (\vec o + t \cdot \vec d) - \vec c \right)^2 &= r^2 \\ | + | |
| − | (\vec o + t \cdot \vec d)^2 - 2 \cdot (\vec o + t \cdot \vec d) \cdot \vec c + {\vec c}^2 &= r^2 \\ | + | |
| − | {\vec o}^2 + 2t \cdot \vec o \cdot \vec d + t^2 \cdot {\vec d}^2 - 2 \cdot \vec o \cdot \vec c - 2t \cdot \vec d \cdot \vec c + {\vec c}^2 &= r^2 \\ | + | |
| − | t^2 {\vec d}^2 + t (2 \cdot \vec o \cdot \vec d - 2 \cdot \vec d \cdot \vec c) + {\vec o}^2 - 2 \cdot \vec o \cdot \vec c + {\vec c}^2 - r^2 &= 0 \\ | + | |
| − | t^2 {\vec d}^2 + t (2 \cdot \vec o \cdot \vec d - 2 \cdot \vec d \cdot \vec c) + (\vec o - \vec c)^2 - r^2 &= 0 \\ | + | |
| − | t^2 + t \left( \frac{2 \cdot \vec o \cdot \vec d - 2 \cdot \vec d \cdot \vec c}{{\vec d}^2} \right) + \frac{(\vec o - \vec c)^2 - r^2}{{\vec d}^2} &= 0 | + | |
| − | \end{align}</math> | + | |
Durch Anwendung der p-q-Formel erhalten wir zwei Lösungen für <math>t</math>: | Durch Anwendung der p-q-Formel erhalten wir zwei Lösungen für <math>t</math>: | ||
| − | : <math>\begin{align} | + | : <math>\begin{align} t_1 &= \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} - \sqrt{ \left( \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} \right) ^2 - \frac{(\vec o - \vec c)^2 - r^2}{{\vec d}^2}} \\ t_2 &= \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} + \sqrt{ \left( \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} \right) ^2 - \frac{(\vec o - \vec c)^2 - r^2}{{\vec d}^2}} \end{align}</math> |
| − | t_1 &= \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} - \sqrt{ \left( \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} \right) ^2 - \frac{(\vec o - \vec c)^2 - r^2}{{\vec d}^2}} \\ | + | |
| − | t_2 &= \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} + \sqrt{ \left( \frac{\vec d \cdot \vec c - \vec o \cdot \vec d}{{\vec d}^2} \right) ^2 - \frac{(\vec o - \vec c)^2 - r^2}{{\vec d}^2}} | + | |
| − | \end{align}</math> | + | |
Wenn der Richtungsvektor <math>\vec d</math> der Geraden normiert ist (Länge 1 hat), dann kann die Division durch <math>{\vec d}^2</math> weggelassen werden, was eine etwas effizientere Implementierung ermöglicht. | Wenn der Richtungsvektor <math>\vec d</math> der Geraden normiert ist (Länge 1 hat), dann kann die Division durch <math>{\vec d}^2</math> weggelassen werden, was eine etwas effizientere Implementierung ermöglicht. | ||
| Zeile 459: | Zeile 438: | ||
===Kollision Rechteck-Kreis (2D)=== | ===Kollision Rechteck-Kreis (2D)=== | ||
Ein Rechteck fasst man als 4 Strecken auf. Man berechnet den Minimalen Abstand (und die Position des Basispunkts) des Kreises von allen 4 Seiten, nimmt von den 4 Abständen (bzw. deren Quadrate, um Wurzeln zu vermeiden) das Minimum. Wenn dieses kleiner als r² ist, dann kollidiert der Kreis mit dem Rechteck im dazugehörigen Basispunkt. | Ein Rechteck fasst man als 4 Strecken auf. Man berechnet den Minimalen Abstand (und die Position des Basispunkts) des Kreises von allen 4 Seiten, nimmt von den 4 Abständen (bzw. deren Quadrate, um Wurzeln zu vermeiden) das Minimum. Wenn dieses kleiner als r² ist, dann kollidiert der Kreis mit dem Rechteck im dazugehörigen Basispunkt. | ||
| + | |||
{{Spoiler|<xh4>Implementierung</xh4>| | {{Spoiler|<xh4>Implementierung</xh4>| | ||
| Zeile 505: | Zeile 485: | ||
}} | }} | ||
}} | }} | ||
| + | |||
| + | ====Beliebige Polygone im 2-dimensionalen==== | ||
| + | Derselbe code kann auch für Beliebige konvexe Polygone verwendet werden, wenn man Rect durch eine Polygonklasse ersetzt (und den Modulo-Operator anpasst) | ||
Aktuelle Version vom 28. September 2017, 23:24 Uhr
Klicke hier, um diese Version anzusehen.
