# Dreieck-Dreieck Kollision (triangle-triangle intersection)



## Rubber (13. Dez 2016)

Hey,
ich wollte fragen ob jemand von euch ein snippet rum liegen hat.
Meine google Recherchen haben mich leider meist nur auf c-snippets geführt.
(mit der effektivste algorhitmus ist wohl der hier: http://fileadmin.cs.lth.se/cs/personal/tomas_akenine-moller/code/tritri_isectline.txt bzw http://fileadmin.cs.lth.se/cs/personal/tomas_akenine-moller/code/opttritri.txt)

Leider sind meine c-Kenntnisse nicht so ausgereift.


----------



## mariane (13. Dez 2016)

rumliegen, ... mal schauen,  .., nö.

Wenn ich das richtig verstehe, ist gefragt ob sich zwei Dreiecke schneiden.
Dann wäre meine Antwort, sie schneiden sich wenn ein Punkt (des ersten Dreiecks) innerhalb eines (des zweiten) Dreieck liegt. Also ganz allg. gesagt: ist ein Punkt innerhalb oder außerhalb eines beliebig geformeten geschlossenen Polygonzuges.
Dazu zieht man Linien von Eckpunkt zu Eckpunkt und schaut, wieviele dieser Linien von einer Linie geschnitten werden, die in eine beliebige Richtung am Punkt beginnend fortläuft. Ungerade Anzahl an geschnittenen Linen heißt innerhalb, gerade bzw. kein schneiden außerhalb der vom Polygon gebildeten Fläche. Das geht natürlich auch bei Dreiecken.


----------



## Rubber (13. Dez 2016)

Hey,
danke schonmal für deine Antwort.
Hauptsächlich ist meine Frage aber tatsächlich ob das jemand schon fertig hat 
(Gerade im Bereich Simulation und Spiel kommt das ja häufiger mal vor, so dass ich dachte es hat vielleicht jemand schon mal gemacht und ich spare es mir das rad neu zu erfinden. Zumal in c diverse snippets existieren und es mich wundert, dass ich nichts in java finde)

Was ich noch vergessen hatte zu erwähnen ist, dass es mir um den *3 Dimensionalen Raum* geht.
Wenn sich keiner meldet, der es zufällig rum liegen hat, werde ich es wohl nach http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/pubs/tritri.pdf selber machen.


----------



## InfectedBytes (13. Dez 2016)

Gerade für den Anfang würde ich dir empfehlen sowas erst recht selber zu machen, allein schon um mehr Übung zu haben.


----------



## JCODA (13. Dez 2016)

mariane hat gesagt.:


> Wenn ich das richtig verstehe, ist gefragt ob sich zwei Dreiecke schneiden.
> Dann wäre meine Antwort, sie schneiden sich wenn ein Punkt (des ersten Dreiecks) innerhalb eines (des zweiten) Dreieck liegt. Also ganz allg. gesagt: ist ein Punkt innerhalb oder außerhalb eines beliebig geformeten geschlossenen Polygonzuges.



Das stimmt leider nicht: 
https://puu.sh/sO8l5/33a0d26aa8.png
Ich alte mich bei sowas meistens an folgendes: einmal implementieren, testen, verstehen, danach Library verwenden, die machen das meist viel effizienter. Speziell für dieses Problem hab ich aber keinen Library in der Hinterhand.


----------



## stg (13. Dez 2016)

Was ist denn ein Dreieck im 3-dim Raum?


----------



## Tobse (13. Dez 2016)

stg hat gesagt.:


> Was ist denn ein Dreieck im 3-dim Raum?


Eine Teilmenge einer Ebene, welche, wenn man sie auf den Zwei-Dimensionalen Raum überträgt, die Eigenschaften eines Dreiecks hat.

Anders gesagt drei Punkte mit je drei Koordinaten.


----------



## InfectedBytes (13. Dez 2016)

stg hat gesagt.:


> Was ist denn ein Dreieck im 3-dim Raum?


Das gleiche wie eine Linie im 2D Raum  
Spaß beiseite, ein Dreieck ist einfach durch drei Eckpunkte definiert, ob diese punkte nun 2D oder 3D sind ist egal.


----------



## Tobse (13. Dez 2016)

Wo ich so drüber nachdenke ist das glaub echt keine einfache Aufgabe... ich sehe gerade nur die Möglichkeit, aus den Punkten des 1. Dreiecks Eine Ebene abzuleiten, die Drei Strecken des 2. Dreiecks damit zu schneiden und irgendwie noch >= <= operationen mit den Koordinaten der Schnittpunkte zu rechnen ... die Lösung muss einfacher sein :O


----------



## Rubber (13. Dez 2016)

InfectedBytes hat gesagt.:


> Gerade für den Anfang würde ich dir empfehlen sowas erst recht selber zu machen, allein schon um mehr Übung zu haben.


Das Problem ist, dass es leider nicht so einfach ist, wie man denken mag.
Allerdings gibt es schon diverse Algorithmen. (wie von mir zb verlinkt)
Meine Internet recherchen haben ergeben, dass sich schon viele damit auseinander gesetzt haben.
Was mich nur wunderte ist, dass ich in c diverse snippets fand, aber kein einziges in Java.
Dachte also, bevor ich jetzt mir die mühe mache und einen der (fertigen) Allgorihtmen selber in Java implementiere, oder von c "abschreibe", dass es doch bestimmt schon der ein oder andere gemacht hat.


----------



## Thallius (13. Dez 2016)

Könnte daran liegen, dass für solche Rechenzeit intensiven Algorithmen C einfach besser geeignet ist als Java. Wer schreibt schon eine 3D Lib in Java?

Gruß

Claus


----------



## stg (13. Dez 2016)

InfectedBytes hat gesagt.:


> Spaß beiseite, ein Dreieck ist einfach durch drei Eckpunkte definiert, ob diese punkte nun 2D oder 3D sind ist egal.



Ja, schon, aber sind dann nur die Ecken gemeint, oder das durch die Ecken definierte 1-Polytop, oder das 2-Polytop? Für solch einen Kollisionstest ist das ja nicht unwichtig 
Aber ich hätte vermutlich einfach mal in die verlinkten Dokumente schauen müssen...



Rubber hat gesagt.:


> Das Problem ist, dass es leider nicht so einfach ist, wie man denken mag.


Nunja, das eigentliche Problem ist ja recht einfach lösbar. Schwierig wird es ja erst, wenn man es besonders raffiniert/effizient machen will. Ist einem das mehr oder weniger egal, dann reduziert sich das Problem doch auf 6 einfache Intersection-Tests (Wenn die zwei Dreiecke sich schneiden, dann schneidet mindestens eine Seite eines der Dreiecke die Grundfläche des zweiten. Bei 2 Dreiecken mit je 3 Seiten also maximal drei Tests.)

Und zur eigentlichen Frage: Nö, hab ich hier auch nicht rumfliegen.


----------

