Erkennung von Dreiecks Kollision im 2D Raum

Verwenden Sie die Linienkreuzung

Ссылка

Bedenken Sie auch die Möglichkeit, dass ein Eckpunkt eine der Seiten des anderen Dreiecks berührt.

Ссылка

Oder sieh dir diesen Link an und scrolle nach unten

Ссылка

Sie können beweisen, dass die zwei Dreiecke nicht kollidieren, indem Sie eine Kante (von den insgesamt 6 Kanten, aus denen die zwei Dreiecke bestehen) als Trennlinie verwenden, wo alle Eckpunkte eines Dreiecks auf der einen Seite liegen Ecken des anderen Dreiecks liegen auf der anderen Seite. Wenn Sie eine solche Kante finden können, dann bedeutet dies, dass die Dreiecke sich nicht schneiden, sonst kollidieren die Dreiecke.

Hier ist eine Matlab-Implementierung der Dreiecks-Kollisionsfunktion. Sie können die Theorie der Funktion sameside hier finden: Ссылка

Kurz gesagt, Hassans Antwort ist am schnellsten.

Ссылка

Dies ist der schnellste Code in Javascript:

Ich habe die obige Geige geschrieben, um ein paar verschiedene Techniken zu testen und die Geschwindigkeit zu vergleichen. Alle Techniken basieren auf einer Kombination von drei verschiedenen Werkzeugen:

1. Baryzentrischer Punkt-in-Dreieck-Test : Konvertiere einen Punkt von einem x, y-Raum in einen u, v-Raum, wobei u, v zwei Seiten des Dreiecks sind. Dann teste, ob der Punkt innerhalb des Dreiecks (0,0) (0,1) (1,0) liegt, was einfach ist.
2. Punkt-in-Dreieck-Test auf derselben Seite : Dieser Test sagt Ihnen, ob ein Winkel mehr oder weniger als 180 Grad beträgt. Wenn das Dreieck a, b, c ist und Ihr Punkt p ist, prüfen Sie, ob die Winkel pab und bac beide mehr oder beide kleiner als 180 sind. Sie müssen dies für ab, bc und ca. Wenn etwas wahr ist, ist der Punkt draußen. Dieser Test ist langsamer als baryzentrisch für einen Punkt.
3. Liniensegmentschnittpunkt : Überprüfen Sie, ob das Liniensegment a, b das Liniensegment c, d schneidet. Um dies zu tun, finden Sie den Punkt, wo sich die zwei Linien kreuzen und dann überprüfen, dass diese Linien in der Bounding Box von a, b und b, c sind. Das ist ungefähr so ​​schnell wie Barycentric.

Das sind die Werkzeuge. Um herauszufinden, ob sich Dreiecke überschneiden, gibt es 3 Möglichkeiten, die ich getestet habe:

1. 8-Linien-Schnittpunkt und 2 Punkt-in-Dreieck-Dreieck : Sie benötigen nur 8 Schnittpunkte und nicht alle 9, da es nicht nur 1 Schnittpunkt geben kann. Danach brauchen Sie 2 Punkt-in-Dreieck, falls ein Dreieck vollständig innerhalb des anderen liegt.
2. 6-Linien-Schnittpunkt und 4-Punkt-in-Dreieck : Wenn Sie es herausziehen, können Sie sehen, dass Sie eine Seite eines der Dreiecke für einen Linienschnitt vollständig ignorieren können und dann einfach alle anderen Dreiecke ausführen Punkte für Punkt-in-Dreieck. Da Linienkreuzung und Baryzentrik ungefähr gleich schnell sind, ist dies nicht viel besser als # 1. Aber wenn Sie die gleiche Seite verwenden, wird es schneller sein, da der gleiche Punkt in Dreiecksrichtung langsamer ist.
3. 9 Punkt-in-Dreieck-Tests auf derselben Seite : Sie können entweder baryzentrisch oder auf derselben Seite verwenden. Für beides modifizieren Sie den Punkt-in-Dreieck, um 3 Punkte gleichzeitig zu testen, und Sie möchten nicht nur testen, dass alle drei außerhalb des Dreiecks liegen. Sie müssen testen, dass sie alle 3 außerhalb von sind auf der gleichen Seite . Da wir viele Informationen erneut verwenden, können wir bei den Berechnungen Zeit sparen. Auch hier wirkt Baryzentrik etwas schneller als die gleiche Seite.