Wie kann ich feststellen, ob sich zwei Dreiecke im euklidischen 2D-Raum schneiden? (d.h. klassische 2D-Geometrie) anhand der (X,Y)-Koordinaten jedes Eckpunkts in jedem Dreieck.
Wie bereits erwähnt, müssen Sie prüfen, ob ein Punkt innerhalb eines Dreiecks liegt. Die einfachste Methode, um zu prüfen, ob ein Punkt innerhalb eines geschlossenen Polygons liegt, besteht darin, vom Punkt aus eine gerade Linie in eine beliebige Richtung zu ziehen und zu zählen, wie oft die Linie einen Scheitelpunkt schneidet. Ist die Antwort ungerade, liegt der Punkt im Polygon, ist sie gerade, liegt er außerhalb.
Die einfachste zu prüfende Gerade ist diejenige, die waagerecht rechts vom Punkt verläuft (oder eine andere senkrechte Richtung). Dies macht die Prüfung auf Scheitelpunktkreuzung fast trivial. Die folgenden Prüfungen sollten ausreichen:
Ist die y-Koordinate des Punktes zwischen den y-Koordinaten der beiden Endpunkte Endpunkte des Scheitelpunkts? Nein, dann nicht kreuzen.
Ist die x-Koordinate des Punktes größer als der am weitesten rechts liegende Endpunkt von des Scheitelpunkts? Ja, dann kreuzen sie sich nicht.
Ist die x-Koordinate des Punktes kleiner als der am weitesten links liegende Endpunkt des Scheitelpunktes? Ja, dann wird gekreuzt.
Wenn die oben genannten Fälle fehlschlagen, können Sie das Kreuzprodukt des Vektors der den Scheitelpunkt repräsentiert, und eines Vektors der vom Ende des Scheitelpunkts zum dem Punkt. Eine negative Antwort bedeutet, dass der Punkt auf einer Seite des Scheitelpunkts liegt, eine positive Antwort auf der anderen Seite des Scheitelpunkts und eine Nullantwort auf dem Scheitelpunkt. Dies funktioniert, weil ein Kreuzprodukt den Sinus zweier Vektoren beinhaltet.
Damit lässt sich nicht feststellen, ob sich zwei Dreiecke schneiden, was ja die Frage war. Man kann nicht nur die Eckpunkte eines Dreiecks testen, da sich Dreiecke auch schneiden können, ohne dass sich Eckpunkte ineinander befinden (z. B. Davidstern).
Was Sie wirklich suchen, ist ein "Punkt im Polygon"-Algorithmus. Wenn einer der Punkte des einen Dreiecks im anderen Dreieck liegt, überschneiden sie sich. Hier ist eine gute Frage zur Überprüfung.
Wie kann ich feststellen, ob ein 2D-Punkt innerhalb eines Polygons liegt?
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
0 Stimmen
Was den wirklich effizientesten Algorithmus anbelangt, so wurde an dieser Frage noch nicht viel gearbeitet - niemand hat eindeutig gezeigt, welche Variante die schnellste ist. Ein Problem ist, dass ein Großteil der Diskussion sich auf Tris im 3D-Raum bezieht. Z.B. realtimecollisiondetection.net/blog/?p=29 PS Solche Probleme werden oft in Form von Punkten auf der "richtigen Seite" eines Liniensegments dargestellt. Beispiel: mochima.com/articles/cuj_geometry_article/ Wie Nick in seinem letzten Absatz darlegt, kommt es in der Praxis vor allem darauf an, wie gut man die Auslese durchführt.