2d Triangle intersection

[Pi_]

Hallo Community

Ich suche jetzt schon einige Tage im internet nach einer 'besten Lösung' zu überprüfen ob sich zwei Dreieke überlappen aber es scheint keine zu geben. Bei einem Dreieck handelt es sich ja um eine sehr primitive Figur, sollte es somit nicht einen einfachen mathematischen Weg geben zu überprüfen ob sich zwei Dreiecke überschneiden?

Es wäre nett mir mir jemand einen Link zu einer sehr performanten Lösung geben könnte oder mir eine schildern könnte.
Ich komme jedenfalls auf keine gute.

Vielen Dank im vorraus,
Pi_

 

[Green Mamba]

2D oder 3D?

 

[Pi_]

2d

 

[aphex.matze]

Ein Klassiker: http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/pubs/tritri.pdf

Der werte Herr hat viel zum Thema geschrieben und veröffentlicht. Ich empfehle das Buch Real-Time Rendering (Akenine-Möller & Haines).

 

[1668mib]

Also ka ob es effektiv ist: Man könnte prüfen, ob (mindestens) einer der Dreieckspunkte im anderen Dreieck liegt...

 

[Bunshichi]

1668mib Lösung ist eher sowas wie ein Standard.

Du prüfst für jede Seite des Dreiecks, ob die drei Punkte der Anderen links oder rechts der Seite liegen.
Aus den 9 Ergebnissen folgt, ob sich Beide schneiden oder nicht.

 

[titanskin]

Also es reicht nicht alleine nur die Eckpunkte zu überprüfen. Dort gibt es ein paar Randfälle.

D.h. 1 Eckpunkt liegt im anderen, oder jeweils 2 Kanten aus den unterschiedlichen Dreiecken schneiden sich, dann gibt es eine Schnittmenge der 2 Dreiecke.

Diese Überprüfung ist in O(1), da man Kanten wie auch Eckpunkte nach obenhin abschätzen kann.

Wenn du nun wissen willst wie man am Besten zwei Strecken kreuzt, so gibt es einen kleinen Trick.

Seien nun p0 = (0,0), p1, p2.

So ist p1 x p2 = det(p1|p2) > 0 wenn p0p1 rechts von p0p2 liegt.

Mit ein wenig Denkarbeit kannst du damit 2 Strecken kreuzen.

Du kannst jedoch auch damit überprüfen ob ein Punkt in einer konvexen Polygon liegt: Prüfe einfach ob für jede Kante der Punkt rechts davon liegt.

 

[kuddlmuddl]

Wenn es um große Zahlen von Dreiecken geht, wo die meisten sich eben dann doch nicht überschneiden arbeitet man üblicherweise mit Bounding-Boxen (2D: Rechtecke, 3D: Quader).
Hier lässt sich durch x,y,z min und max viel schneller prüfen, ob eine Überschneidung überhaupt theoretisch möglich ist. Erst danach berechnet man wirklich mit "komplizierter" Mathematik.

 

[Pi_]

@ titanskin
Wenn ich immer die strecken des einen dreiecks vs die strecken des anderen nehme ist es dann nicht etwas zu aufwendig?

Du kannst jedoch auch damit überprüfen ob ein Punkt in einer konvexen Polygon liegt: Prüfe einfach ob für jede Kante der Punkt rechts davon liegt.

Was konvex ist weiß und ich glaube ich habe verstanden wie du es meinst, aber das gibt doch nur die richtige lösung wen ein punkt eines dreiecks in einem anderen läge soweit ich es verstehe.

@ Bunshichi
Dein Kommentar bezieht sich glaube ich auf das selbe. Wie genau bekomme ich aus den 9 ergebnissen eine Lösung?

Es fällt mir etwas schwer einen genauen Lösungsweg aus den Kommentaren zu entnehmen.

 

[maxwell-cs]

naja, 3 strecken gegen 3 strecken testen macht 9 tests. je nach definition von "intersection" muss man noch den fall abfangen, dass ein dreieck ganz im anderen enthalten ist, was ebenfalls schnell geht.

implementier das mal und schau dann, ob die performance reicht.
wenn nein, die vorgeschlagene boundingbox-heuristik vorschalten.
erst wenn das nicht reicht, kannst du dir gedanken über was schnelleres machen.

edit: wofür brauchst du das überhaupt? wenn du dir gedanken über die performance machst, scheinst du das ja sehr (!) oft aufzurufen. willst du vielleicht von einer menge von dreiecken alle sich schneidenden paare bestimmen? dann ist paarweises testen recht ineffizient..

 

[titanskin]

Was konvex ist weiß und ich glaube ich habe verstanden wie du es meinst, aber das gibt doch nur die richtige lösung wen ein punkt eines dreiecks in einem anderen läge soweit ich es verstehe.

Konvex (ugs.: jede Strecke von 2 Punkten aus der Menge liegt vollständig in der Menge drinnen)

Richtig. Du bist auf dem richtigen Weg. Vllt hilft dir nochmal die Fallunterscheidung:

1. Die Dreiecke schneiden sich gar nicht => kein Eckpunkt liegt im anderen Dreieck, keine Strecken kreuzen sich.
2. Ein Dreieck befindet sich im anderen => Alle Eckpunkte, d.h. mindestens einer, liegt im anderen Dreieck!
3. Die Dreiecke schneiden sich so "halb", d.h. nicht alle Eckpunkte liegen im anderen. => Mindestens ein Punkt wäre im anderen Dreieck
3.1 Hier kann es aber auch passieren, dass kein Eckpunkt im anderen Dreieck liegt, jedoch dass sich die Strecken schneiden.
3.2 (mir fällt kein Fall mehr ein)

D.h. um einen stabilen Algorithmus (der für alle Eingaben) korrekt ist, muss man leider alle Fälle abdecken und dieser beinhaltet leider, dass man mindestens einen Punkt findet der im anderen Dreieck liegt, oder ein Streckenpaar findet, das sich schneidet.
Demnach ist der worst-case jener, bei dem sich die Dreiecke nicht schneiden, da man zwingend alle Kombinationen durchgehen kann.

Naja wie schon angedeutet kann die Laufzeit auf O(1) abschätzen (http://de.wikipedia.org/wiki/Landau-Symbole).
Theoretisch geht es also nicht schneller. Ob es nun praktisch einen schnelleren Algorithmus gibt (dieser geringere Konstanten hat), müsste ich noch mal nachdenken.

Achso zur Prüfung von BoundingBox und co was hier angesprochen wurde: Du findest die zugehörige Datenstruktur unter KD-Tree bzw. Quadtree

 

[Pi_]

Vielen Dank für die ganze Hilfe
Ich habe es geschafft eine erste Version zu laufen zu bringen. Es funktioniert jetzt mit triangle vs triangle segment intersection checks.

Ich werde eine vorab überprüfung hinzufügen um zu sehen ob eine collision überhaupt möglich ist, die segment checks auf die außenlinien der figur beschrenken und überprüfen ob die figur einen außenpunkt in einem dreieck der anderen hat. Das sollte alle möglichen überlappungen abdecken und ein ziehmlich recourcensparender Weg sein.

Achja es ging mir darum zu überprüfen ob sich zwei shapes überlappen aber ich hatte direkt nach dreiecken gefragt.

Danke nochmal für die Hilfe