2D-Kollisionserkennung

Aus Spieleprogrammierer-Wiki
Wechseln zu: Navigation, Suche

Bitte beachte, dass dieser Artikel noch unvollständig ist! Hilf mit, ihn fertigzustellen.
Näheres dazu findest du ggf. auf der Diskussionsseite. Wenn du der Meinung bist, dass der Artikel vollständig ist, kannst du diesen Hinweis entfernen.

In diesem Artikel geht es um 2D-Kollisionserkennung, also die Überprüfung, ob sich zwei Objekte berühren oder schneiden. Für Anwendungen, bei denen dies eine zentrale Rolle spielt, empfiehlt sich auch ggf. der Einsatz einer Physik-Engine. Eine Physik-Engine kann Kollisionen nicht nur sehr effizient erkennen, sondern auch physikalisch korrekt darauf reagieren.

Inhaltsverzeichnis

Erkennung anhand geometrischer Formen

Häufig werden Spielobjekte durch einfache geometrische Formen (Kreise, Rechtecke, Polygone) angenähert, da eine Kollisionserkennung für solche Formen einfacher bzw. schneller durchgeführt werden kann. Dabei nimmt man in Kauf, dass die physikalische Form des Objekts von seiner sichtbaren Form abweicht. Im Folgenden werden Kollisionstests für zweidimensionale Formen behandelt.

Kollision zwischen zwei achsenausgerichteten Rechtecken

Die Prüfung einer Kollision zweier achsenausgerichteten (nicht rotierten) Rechtecken kann sehr effizient durchgeführt werden. Aufgrund der daraus resultierenden hohen Geschwindigkeit kann diese Prüfung komplexeren Prüfungen voran gestellt werden, um zu testen, ob zwei Objekte nah genug aneinander sind, damit eine Kollision möglich ist. Dazu testet man die sie umgebenden Rechtecke (Bounding Rectangles) auf Kollision.

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.

Implementierung

Implementierung in C++
bool rectangleCollision(const Vector& position1, float width1, float height1,
                        const Vector& position2, float width2, float height2)
{
    return position1.x < position2.x + width2  &&
           position2.x < position1.x + width1  &&
           position1.y < position2.y + height2 &&
           position2.y < position1.y + height1;
}
Implementierung in C#
bool rectangleCollision(Vector position1, float width1, float height1,
                        Vector position2, float width2, float height2)
{
    return position1.x < position2.x + width2  &&
           position2.x < position1.x + width1  &&
           position1.y < position2.y + height2 &&
           position2.y < position1.y + height1;
}
Implementierung in Python
def rectangleCollision(position1, width1, height1, position2, width2, height2):
    return position1[0] < position2[0] + width2  and
           position2[0] < position1[0] + width1  and
           position1[1] < position2[1] + height2 and
           position2[1] < position1[1] + height1
Implementierung in Java
boolean rectangleCollision(float[] position1, float width1, float height1,
                           float[] position2, float width2, float height2) {
    return position1[0] < position2[0] + width2  &&
           position2[0] < position1[0] + width1  &&
           position1[1] < position2[1] + height2 &&
           position2[1] < position1[1] + height1;
}

Kollision zwischen zwei Kreisen

Wenn die Distanz zwischen den Mittelpunkten zweier Kreise kleiner ist als die Summe ihrer Radien, so liegt eine Kollision vor. Also benötigen wir zum Prüfen der Kollision die Positionen und Radien der beiden Kreise. Dabei rechnen wir mit Hilfe des Satz des Pythagoras die Distanz zwischen den beiden Kreisen aus und prüfen zum Schluss, ob diese kleiner ist als die Summe beider Radien.

Implementierung

Implementierung in C++
bool circleCollision(const Vector& position1, float radius1,
                     const Vector& position2, float radius2)
{
    const float dx = position1.x - position2.x;
    const float dy = position1.y - position2.y;
    
    // Langsame Version, benötigt Wurzel:
    // return sqrt(dx * dx + dy * dy) <= radius1 + radius2;
    
    // Schnelle Version, vergleicht die Quadrate:
    const float radiusSum = radius1 + radius2;
    return dx * dx + dy * dy <= radiusSum * radiusSum;
}
Implementierung in C#
bool circleCollision(Vector position1, float radius1,
                     Vector position2, float radius2)
{
    float dx = position1.x - position2.x;
    float dy = position1.y - position2.y;
    
    // Langsame Version, benötigt Wurzel:
    // return (Math.Sqrt(dx * dx + dy * dy) <= Convert.ToDouble(radius1) + Convert.ToDouble(radius2));
    
    // Schnelle Version, vergleicht die Quadrate:
    float radiusSum = radius1 + radius2;
    return dx * dx + dy * dy <= radiusSum * radiusSum;
}
Implementierung in Python
def circleCollision(position1, radius1, position2, radius2):
    dx = position1[0] - position2[0]
    dy = position1[1] - position2[1]
    
    # Langsame Version, benötigt Wurzel:
    # return math.sqrt(dx * dx + dy * dy) <= radius1 + radius2
    
    # Schnelle Version, vergleicht die Quadrate:
    radiusSum = radius1 + radius2
    return dx * dx + dy * dy <= radiusSum * radiusSum
Implementierung in Java
boolean circleCollision(float[] position1, float radius1,
                        float[] position2, float radius2) {
    float dx = position1[0] - position2[0];
    float dy = position1[1] - position2[1];
    
    // Langsame Version, benötigt Wurzel:
    // return Math.sqrt(dx * dx + dy * dy) <= radius1 + radius2;
    
    // Schnelle Version, vergleicht die Quadrate:
    float radiusSum = radius1 + radius2;
    return dx * dx + dy * dy <= radiusSum * radiusSum;
}

Kollision zwischen zwei Geraden

Auch wenn eine Kollisionsabfrage zwischen zwei Geraden für ein Spiel eher unüblich ist, werden wir diesen Fall betrachten, denn die Vorgehensweise können wir auch für andere Kollisionsabfragen verwenden. Falls zwei Geraden nicht parallel zueinander sind, so schneiden sie sich irgendwo, und somit liegt eine Kollision vor. In diesem Beispiel werden die Geraden durch zwei Punkte beschrieben (eine Darstellung mit einem Punkt und einer Richtung ist natürlich ebenso möglich). Angenommen zwei Punkte einer Geraden sind bekannt, so ist es möglich, einen beliebigen Punkt auf ihr wie folgt zu beschreiben:

§P_a = A_1 + u_a(A_2 - A_1)§

Wenn man nun die zwei Geraden mithilfe dieser Formel beschreibt und sie gleichsetzt (§P_a = P_b§), bekommt man folgende Gleichungen für §x§ und §y§ der Punkte §P_a§ und §P_b§:

§\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} §

Diese Gleichungen werden nun nach §u_a§ und §u_b§ aufgelöst:

§\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}§

Man beachte nun die Nenner der beiden Gleichungen, denn sie sind identisch. Wenn nun der Nenner gleich Null ist, so sind §u_a§ und §u_b§ 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 EPSILON dargestellt) gewählt werden, unterhalb dessen die Geraden als parallel angenommen werden. Ein möglicher Wert wäre z.B. §10^{-8}§.

Implementierung

Implementierung in C++
bool lineCollision(const Vector& a1, const Vector& a2,
                   const Vector& b1, const Vector& b2)
{
    const float denom = (b2.y - b1.y) * (a2.x - a1.x) -
                        (b2.x - b1.x) * (a2.y - a1.y);
    return abs(denom) > EPSILON;
}
Implementierung in C#
bool lineCollision(Vector a1, Vector a2,
                   Vector b1, Vector b2)
{
    float denom = (b2.y - b1.y) * (a2.x - a1.x) -
                  (b2.x - b1.x) * (a2.y - a1.y);
    return Math.Abs(denom) > EPSILON;
}
Implementierung in Python
def lineCollision(a1, a2, b1, b2):
    denom = (b2[1] - b1[1]) * (a2[0] - a1[0]) -
            (b2[0] - b1[0]) * (a2[1] - a1[1])
    return abs(denom) > EPSILON
Implementierung in Java
boolean lineCollision(float[] a1, float[] a2,
                      float[] b1, float[] b2)
{
    float denom = (b2[1] - b1[1]) * (a2[0] - a1[0]) -
                  (b2[0] - b1[0]) * (a2[1] - a1[1]);
    return Math.abs(denom) > EPSILON;
}

Kollision zwischen zwei Strecken

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.

Implementierung

Implementierung in C++
bool lineSegmentCollision(const Vector& a1, const Vector& a2,
                          const Vector& b1, const Vector& b2)
{
    const float denom = (b2.y - b1.y) * (a2.x - a1.x) -
                        (b2.x - b1.x) * (a2.y - a1.y);
    if (abs(denom) < EPSILON) return false;
    
    const float ua = ((b2.x - b1.x) * (a1.y - b1.y) -
                      (b2.y - b1.y) * (a1.x - b1.x)) / denom;
    const float ub = ((a2.x - a1.x) * (a1.y - b1.y) -
                      (a2.y - a1.y) * (a1.x - b1.x)) / denom;
    return ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1;
}
Implementierung in C#
bool lineSegmentCollision(Vector a1, Vector a2,
                          Vector b1, Vector b2)
{
    float denom = (b2.y - b1.y) * (a2.x - a1.x) -
                  (b2.x - b1.x) * (a2.y - a1.y);
    if (abs(denom) < EPSILON) return false;
    
    float ua = ((b2.x - b1.x) * (a1.y - b1.y) -
                (b2.y - b1.y) * (a1.x - b1.x)) / denom;
    float ub = ((a2.x - a1.x) * (a1.y - b1.y) -
                (a2.y - a1.y) * (a1.x - b1.x)) / denom;
    return ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1;
}
Implementierung in Python
def lineSegmentCollision(a1, a2, b1, b2):
    denom = (b2[1] - b1[1]) * (a2[0] - a1[0]) -
            (b2[0] - b1[0]) * (a2[1] - a1[1])
    if (abs(denom) < EPSILON):
        return false
    
    ua = ((b2[0] - b1[0]) * (a1[1] - b1[1]) -
          (b2[1] - b1[1]) * (a1[0] - b1[0])) / denom
    ub = ((a2[0] - a1[0]) * (a1[1] - b1[1]) -
          (a2[1] - a1[1]) * (a1[0] - b1[0])) / denom
    return ua >= 0 and ua <= 1 and ub >= 0 and ub <= 1
Implementierung in Java
boolean lineSegmentCollision(float[] a1, float[] a2,
                             float[] b1, float[] b2)
{
    float denom = (b2[1] - b1[1]) * (a2[0] - a1[0]) -
                  (b2[0] - b1[0]) * (a2[1] - a1[1]);
    if (Math.abs(denom) < EPSILON) return false;
    
    float ua = ((b2[0] - b1[0]) * (a1[1] - b1[1]) -
                (b2[1] - b1[1]) * (a1[0] - b1[0])) / denom;
    float ub = ((a2[0] - a1[0]) * (a1[1] - b1[1]) -
                (a2[1] - a1[1]) * (a1[0] - b1[0])) / denom;
    return ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1;
}

Kollision zwischen einem Kreis und einer Geraden

Genereller Ansatz

Der im Folgenden beschriebene Ansatz arbeitet mit Vektoren und funktioniert für beliebige Dimensionen (2D: Gerade und Kreis, 3D: Gerade und Kugel). Der Kreis habe den Mittelpunkt mit dem Ortsvektor §\vec c§ und den Radius §r§. Dann lautet die Gleichung für die Ortsvektoren §\vec x§ der Punkte auf dem Kreis:

§(\vec x - \vec c)^2 = r^2§

Sei §\vec o§ der Ortsvektor eines beliebigen Punkts auf der Geraden und §\vec d§ der Richtungsvektor der Geraden. Dann ist die parametrische Form der Geraden gegeben durch:

§{\vec x}(t) = \vec o + t \cdot \vec d§

Nun setzen wir §\vec x(t)§ in die Kreisgleichung ein. Wir bringen die Gleichung in die richtige Form für die p-q-Formel, so dass wir nach §t§ auflösen können:

§\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}§

Durch Anwendung der p-q-Formel erhalten wir zwei Lösungen für §t§:

§\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}§

Wenn der Richtungsvektor §\vec d§ der Geraden normiert ist (Länge 1 hat), dann kann die Division durch §{\vec d}^2§ weggelassen werden, was eine etwas effizientere Implementierung ermöglicht.

Betrachten wir den Ausdruck unter der Wurzel, der bei beiden Lösungen gleich ist. Es gibt drei Fälle, die eintreten können:

  1. Der Ausdruck ist negativ: Die Wurzel einer negativen Zahl ist für reelle Zahlen nicht definiert. In unserem Fall bedeutet das, dass die Gerade den Kreis nicht schneidet.
  2. Der Ausdruck ist 0: In diesem Fall ist §t_1 = t_2§, was bedeutet, dass die Gerade den Kreis berührt (es gibt nur einen gemeinsamen Punkt, dessen Ortsvektor §\vec o + t_1 \cdot \vec d§ ist).
  3. Der Ausdruck ist größer als 0: Die Gerade schneidet den Kreis in den beiden Punkten mit den Ortsvektoren §\vec o + t_1 \cdot \vec d§ und §\vec o + t_2 \cdot \vec d§.
Implementierung
Implementierung in C++
// c:      Mittelpunkt des Kreises
// r:      Radius des Kreises
// o:      Ein Punkt auf der Geraden
// d:      Richtungsvektor der Geraden
// p_outT: Optionaler Zeiger. Falls p_outT != 0 und es gibt eine Kollision,
//         dann enthalten p_outT[0] und p_outT[1] die beiden Lösungen t1 und t2.
//         Die Schnittpunkte sind o + t1 * d bzw. o + t2 * d.
bool circleLineCollision(const Vector& c, float r,
                         const Vector& o, const Vector& d,
                         float* p_outT = 0)
{
    // Kehrwert der Länge von d vorberechnen, um die Berechnung zu beschleunigen (Divisionen sind langsam!).
    const float invDSq = 1.0f / d.lengthSq();
    
    // Term vorberechnen, der mehrfach benötigt wird.
    const float p = (Vector::dot(d, c) - Vector::dot(o, d)) * invDSq;
    
    // Nun kann der Ausdruck unter der Wurzel berechnet werden (Diskriminante).
    const float discriminant = p * p - ((o - c).lengthSq() - r * r) * invDSq;
    
    if (discriminant < 0.0f)
    {
        // Keine Kollision!
        return false;
    }
    else
    {
        // Kollision! Wir gehen davon aus, dass es zwei Schnittpunkte gibt.
        // Der Benutzer kann später selber entscheiden, ob er diese als einen einzigen behandeln möchte,
        // falls sie nah genug beieinander liegen.
        if (p_outT)
        {
            // Die beiden Lösungen für t ausrechnen und ausgeben.
            const float squareRoot = sqrt(discriminant);
            p_outT[0] = p - squareRoot;
            p_outT[1] = p + squareRoot;
        }
        
        return true;
    }
}

Geometrischer Ansatz speziell für 2D

Veranschaulichung des Idealfalls mit senkrechter Geraden.

Im Folgenden wird ein geometrischer Ansatz beschrieben, der für den zweidimensionalen Fall sehr anschaulich ist. Er lässt sich jedoch nicht ohne Weiteres auf mehr Dimensionen übertragen.

Der einfachste Fall für eine Prüfung auf eine Kollision liegt vor, wenn die Gerade senkrecht oder waagerecht ist und der Mittelpunkt des Kreises, nachfolgend §M§ genannt, dem Nullpunkt des Koordinatensystems entspricht oder die Gerade den Nullpunkt des Koordinatensystems schneidet. Ist die Gerade senkrecht, dann gibt es eine Kollision, wenn §-r \le P_x \le r§ zutrifft. Ist die Gerade waagerecht, gibt es eine Kollision, wenn §-r \le P_y \le r§ zutrifft. §r§ steht in dem Fall für den Radius des Kreises, §P_x§ für die x-Koordinate eines beliebigen Punkts auf der Geraden und §P_y§ für die y-Koordinate eines beliebigen Punkts, §P§ auf der Geraden.

Nachfolgend soll der erste Fall als Idealfall genommen werden. In den Fällen, in denen der Kreis vom Nullpunkt versetzt oder die Gerade weder senkrecht noch waagerecht ist, wird zuerst die Umrechnung vorgenommen, sodass die Überprüfung erfolgen kann.

Verschobener Kreis

Wenn die Gerade senkrecht oder waagerecht ist, §M§ aber nicht dem Nullpunkt des Koordinatensystems entspricht, dann muss von dem Punkt §P§ der Geraden, der für die Kollisionsprüfung verwendet werden soll, §M§ abgezogen werden. Diese Berechnung kann unabhängig davon durchgeführt werden, ob die Gerade waagerecht oder senkrecht ist. Da bei einer Subtraktion von §M§ von §M§ das Ergebnis immer der Nullpunkt des Koordinatensystems ist, entfällt diese Berechnung. Auf den über diese Rechnung erhaltenen Punkt kann wieder die jeweilige oben angeführte Überprüfung durchgeführt werden.

Beliebige Gerade

Ist die Gerade nicht senkrecht oder waagerecht, so muss diese erst gedreht werden, damit sie senkrecht oder waagerecht ist. Um einen Punkt um den Mittelpunkt des Koordinatensystems zu drehen, kann man die Berechnungen §P'_x = P_x \cdot cos(\alpha) - P_y \cdot sin(\alpha)§ und §P'_y = P_x \cdot sin(\alpha) + P_y \cdot cos(\alpha)§ verwenden. §P'§ stellt dabei den Punkt nach der Drehung dar. Für diese Drehung muss also nicht der entsprechende Winkel selbst, sondern dessen Ergebnis der Sinus- und Kosinus-Funktion ermittelt werden. Wenn man einen weiteren Punkt der Geraden, nachfolgend §Q§ genannt, nimmt, kann man diese über das dadurch darstellbare rechtwinklige (Steigungs-)Dreieck ermitteln. Die Rechnungen dafür lauten §sin(\alpha) = \tfrac{\text{Gegenkathete}}{\text{Hypotenuse}}§ und §cos(\alpha) =\tfrac{\text{Ankathete}}{\text{Hypotenuse}}§. Da die Drehung gegen den Uhrzeigersinn geht, muss für eine steigende Gerade ein anderer Wert gewählt werden, als für eine fallende Gerade. Für eine steigende Gerade ist die Seite des Dreiecks, die sich durch die x-Koordinaten errechnet, die Gegenkathete und für eine fallende Gerade ist die Seite des Dreiecks, die sich durch die y-Koordinaten errechnet die Gegenkathete.

Fasst man alle Berechnungen zusammen, erhält man die folgende Vorgehensweise. Es wird angenommen, dass zwei Punkte der Gerade §P§ und §Q§ gegeben sind.

Kollision Kreis-Strecke

Insbesondere für Kreis-Rechteckkollision ist es wichtig, den Punkt auf einer Strecke zu finden, der dem Mittelpunk der Kugel am nähesten liegt.

Allgemeiner Ansatz

Wir betrachten eine Strecke durch 2 Punkte §\boldsymbol{x}§ und §\boldsymbol{y}§ und einen Kreis mit radius §r§ und Mittelpunkt §\boldsymbol{m}§ (x,y,m Vektoren im §\mathbb{R}^n§). Der einfachheit halber definieren wir: §\boldsymbol{a} = \boldsymbol{y-x}§ (Richtungsvektor der Geraden durch die Strecke, nicht normalisiert, sondern ist genau so lang wie die Strecke) und §\boldsymbol{b = m-x}§ (Verbindungsvektor vom Startpunkt und dem Mittelpunkt)

Daraus lässt sich der Punkt berechnen, an dem der Mittelpunkt der Geraden §g: \boldsymbol{v} = \boldsymbol{x}+\boldsymbol{a}\cdot t§ am nähesten ist. Nun gilt: §t = \frac{\langle a,b\rangle}{\langle a,a\rangle}§ (§\langle a,b\rangle§ ist das Skalar/Punktprodukt von a unb b) Allerdings ist die Strecke nur der Teil der Geraden, für den §t\in [0,1]§ ist. Also setzt man §t*=\begin{cases}0&t<0\\t& t\in [0,1]\\1& t > 1\end{cases}§ Der Punkt auf der Strecke, der dem Kreis am nähesten ist, ist dann §\boldsymbol{d} = \boldsymbol{x}+\boldsymbol{a}\cdot t*§. Wenn nun §||\boldsymbol{m}-\boldsymbol{x}||^2<r^2§, dann Kollidiert der Kreis im Punkt d mit der Strecke.

Komplexität

Diese Berechnungen benötigen 0 Quadratwurzeln, 3*n Multiplikationen und n Divisionen und lassen sich damit sehr schnell durchführen.

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.


Implementierung

Implementierung in C++
Vector2 PointLineDist(Vector2 point, Vector2 linestart, Vector2 lineend)
{
      Vector2 a = lineend - linestart;
      Vector2 b = point - linestart;
      double t = dot(a, b)/(length(a)²);
      if (t < 0) t = 0;
      if (t > 1) t = 1;
      return linestart + a * t;
}
 
struct CollisionResult
{
      bool isCollided;
      Vector2 collisionPoint;
      float distanceSq;
}
 
// Gibt zurück, ob eine Kollision stattfand und wenn ja, wo, und wie lang der (minimale, quadratische) Abstand zum Rechteck ist.
CollisionResult RectangleCircleKollision(Rect rect, Circle circle)
{
      float minDistSq = HUGE_VAL;
      Vector2 basePoint = Vector2(0,0);
      // Seiten durchgehen, Schleife kann (bzw muss, je nachdem wie Rect aussieht) entrollt werden
      for(int i=0; i<4 ;i++)
      {
            Vector2 base = PointLineDist(circle.mid, rect.points[i], rect.points[(i+1) % 4]);
            if(lengthsq(circle.mid-base)<minDistSq)
            {
                  // Kürzerer Abstand, neu zuweisen.
                  minDistSq = lengthsq(circle.mid - base);
                  basePoint = base;
            }
      }
      return {minDistSq < circle.radius * circle.radius,
              basePoint,
              minDistSq};
}

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)

Meine Werkzeuge
Namensräume
Varianten
Aktionen
Navigation
Werkzeuge