2D-Kollisionserkennung
Aus Spieleprogrammierer-Wiki
(Unterschied zwischen Versionen)
| [unmarkierte Version] | [unmarkierte Version] |
K (→Kollision zwischen einem Kreis und einer Geraden: Überschriftentife angepasst) |
K (→Erkennung anhand geometrischer Figuren: Kapselung der Implementierung durch Spoiler) |
||
| Zeile 17: | Zeile 17: | ||
Wenn mindestens eine Kante eines Rechtecks ein anderes Rechteck überschneidet, dann liegt eine Kollision vor. Es werden die Positionen der einzelnen Eckpunkte der Rechtecke benötigt. In den Implementierungsbeispielen werden Rechtecke durch die Position der linken oberen Ecke, die Breite und die Höhe beschrieben. | Wenn mindestens eine Kante eines Rechtecks ein anderes Rechteck überschneidet, dann liegt eine Kollision vor. Es werden die Positionen der einzelnen Eckpunkte der Rechtecke benötigt. In den Implementierungsbeispielen werden Rechtecke durch die Position der linken oberen Ecke, die Breite und die Höhe beschrieben. | ||
| + | {{Spoiler|<xh4>Implementierung</xh4>| | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C++</xh5> |
| | | | ||
<sourcecode lang="cpp" tab="4"> | <sourcecode lang="cpp" tab="4"> | ||
| Zeile 33: | Zeile 34: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C#</xh5> |
| | | | ||
<sourcecode lang="csharp" tab="4"> | <sourcecode lang="csharp" tab="4"> | ||
| Zeile 48: | Zeile 49: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Python</xh5> |
| | | | ||
<sourcecode lang="python" tab="4"> | <sourcecode lang="python" tab="4"> | ||
| Zeile 60: | Zeile 61: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Java</xh5> |
| | | | ||
<sourcecode lang="java" tab="4"> | <sourcecode lang="java" tab="4"> | ||
| Zeile 71: | Zeile 72: | ||
} | } | ||
</sourcecode> | </sourcecode> | ||
| + | }} | ||
}} | }} | ||
| Zeile 78: | Zeile 80: | ||
Dabei rechnen wir mit Hilfe des [http://de.wikipedia.org/wiki/Satz_des_Pythagoras Satz des Pythagoras] die Distanz zwischen den beiden Kreisen aus und prüfen zum Schluss, ob diese kleiner ist als die Summe beider Radien. | Dabei rechnen wir mit Hilfe des [http://de.wikipedia.org/wiki/Satz_des_Pythagoras Satz des Pythagoras] die Distanz zwischen den beiden Kreisen aus und prüfen zum Schluss, ob diese kleiner ist als die Summe beider Radien. | ||
| + | {{Spoiler|<xh4>Implementierung</xh4>| | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C++</xh5> |
| | | | ||
<sourcecode lang="cpp" tab="4"> | <sourcecode lang="cpp" tab="4"> | ||
| Zeile 99: | Zeile 102: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C#</xh5> |
| | | | ||
<sourcecode lang="csharp" tab="4"> | <sourcecode lang="csharp" tab="4"> | ||
| Zeile 119: | Zeile 122: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Python</xh5> |
| | | | ||
<sourcecode lang="python" tab="4"> | <sourcecode lang="python" tab="4"> | ||
| Zeile 136: | Zeile 139: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Java</xh5> |
| | | | ||
<sourcecode lang="java" tab="4"> | <sourcecode lang="java" tab="4"> | ||
| Zeile 152: | Zeile 155: | ||
} | } | ||
</sourcecode> | </sourcecode> | ||
| + | }} | ||
}} | }} | ||
| Zeile 179: | Zeile 183: | ||
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>. | ||
| + | {{Spoiler|<xh4>Implementierung</xh4>| | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C++</xh5> |
| | | | ||
<sourcecode lang="cpp" tab="4"> | <sourcecode lang="cpp" tab="4"> | ||
| Zeile 194: | Zeile 199: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C#</xh5> |
| | | | ||
<sourcecode lang="csharp" tab="4"> | <sourcecode lang="csharp" tab="4"> | ||
| Zeile 208: | Zeile 213: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Python</xh5> |
| | | | ||
<sourcecode lang="python" tab="4"> | <sourcecode lang="python" tab="4"> | ||
| Zeile 219: | Zeile 224: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Java</xh5> |
| | | | ||
<sourcecode lang="java" tab="4"> | <sourcecode lang="java" tab="4"> | ||
| Zeile 230: | Zeile 235: | ||
} | } | ||
</sourcecode> | </sourcecode> | ||
| + | }} | ||
}} | }} | ||
| Zeile 236: | Zeile 242: | ||
Die Kollisionserkennung zwischen zwei Strecken erfolgt ähnlich wie bei den Geraden, nur mit einem kleinen Zusatz, denn Strecken haben einen Start- und Endpunkt. Deswegen werden Strecken auch als Geradenabschnitt bezeichnet. Es wird also wieder überprüft, ob die beiden Strecken parallel zu einander sind. Wenn dies der Fall ist und die Strecken sich auch nicht überlappen, liegt keine Kollision vor. Ansonsten muss noch überprüft werden, ob sich die Strecken in den angegebenen Abschnitten schneiden. Nur wenn das zutrifft, liegt eine Kollision vor. | Die Kollisionserkennung zwischen zwei Strecken erfolgt ähnlich wie bei den Geraden, nur mit einem kleinen Zusatz, denn Strecken haben einen Start- und Endpunkt. Deswegen werden Strecken auch als Geradenabschnitt bezeichnet. Es wird also wieder überprüft, ob die beiden Strecken parallel zu einander sind. Wenn dies der Fall ist und die Strecken sich auch nicht überlappen, liegt keine Kollision vor. Ansonsten muss noch überprüft werden, ob sich die Strecken in den angegebenen Abschnitten schneiden. Nur wenn das zutrifft, liegt eine Kollision vor. | ||
| + | {{Spoiler|<xh4>Implementierung</xh4>| | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C++</xh5> |
| | | | ||
<sourcecode lang="cpp" tab="4"> | <sourcecode lang="cpp" tab="4"> | ||
| Zeile 257: | Zeile 264: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in C#</xh5> |
| | | | ||
<sourcecode lang="csharp" tab="4"> | <sourcecode lang="csharp" tab="4"> | ||
| Zeile 277: | Zeile 284: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Python</xh5> |
| | | | ||
<sourcecode lang="python" tab="4"> | <sourcecode lang="python" tab="4"> | ||
| Zeile 295: | Zeile 302: | ||
{{Spoiler| | {{Spoiler| | ||
| − | < | + | <xh5>Implementierung in Java</xh5> |
| | | | ||
<sourcecode lang="java" tab="4"> | <sourcecode lang="java" tab="4"> | ||
| Zeile 312: | Zeile 319: | ||
} | } | ||
</sourcecode> | </sourcecode> | ||
| + | }} | ||
}} | }} | ||
Version vom 17. November 2011, 10:40 Uhr
Klicke hier, um diese Version anzusehen.
