Hallo :) weiß jemand eine einfache Methode, wie man den Schnitt zweier Dreiecke im 2D berechnen kann? Ich hab unter verschiedenen Suchbegriffen gegurgelt, wie "cut triangles 2d", "collision detection triangles", "schnitt zweier dreiecke 2d", usw, aber wirklich nichts brauchbares gefunden, leider :( Kollisionserkennung wäre eine Idee gewesen, die behelfen sich aber mit dem Schnitt der Innkreise, um zu entscheiden, ob es kollidiert oder nicht. Ist aber nicht wirklich genau ... Bei meiner Anwendung müsste ich die Schnittfläche visualisieren ... Ich hab schon fast die Vermutung, dass man beide Dreiecke flood-fillen und anschließend miteinander verunden sollte, um die Schnittfläche zu erhalten. Ich hatte aber auf irgendwas einfaches mit weniger Bruteforce-Rechenaufwand gehofft, weil es eigentlich triangulierte konvexe Polygone sind und ich den Schnitt für jedes Teildreieck berechnen muss ... Würde mich über Hilfe freuen -- Helli
Beschreib die 3ecke durch 3 lin. Fuktionen. (die kanten).Dann kannst du jede Funktion mit der Anderen schneiden lassen. Die schnittpunkte müssen auf der Gerade zwischen 2 Eckpunkten liegen, dann schneidet es. fertig aus. Der Sonderfall das das eine Dreieck so klein ist, dass es im anderen ligt kannst du herausfinden indem du guckst ob ein Punkt des 3ecks im Anderen 3eck liegt. das ist mathematik der 8. Klasse. Und: wenn du darüber per google nix findest wirst du intelektuell sicher auch nicht in der lage sein die mathematik der 8. Klasse zu berherrschen. Das ist einfach faulheit.
DerAlbi schrieb: > Und: wenn du darüber per google nix findest wirst du intelektuell sicher > auch nicht in der lage sein die mathematik der 8. Klasse zu > berherrschen. Das ist einfach faulheit. Klar bin ich intellektuel in der Lage ein paar Gerade zu schneiden. Es sind halt nur ziemlich viele und jede mit jeder zu schneiden wär ein quadratischer Aufwand, was nicht wirklich toll ist. Dachte, es würde was besseres geben. Und das Statement mit der Faulheit finde ich interessant ... Wenn man irgendwas neu macht, gibts immer die Leute, die meckern, dass man das Rad ja nicht neu erfinden soll, weil's das ja alles schon gibt und das ist ja eh immer besser, als das, was man selbst machen würde. Auf der anderen Seite gibt's Leute, die meckern, wenn man nach einem fertigen Rad fragt ... -- Helli PS: Es ist pure Faulheit auf Groß- und Kleinschreibung zu verzichten ...
Helli schrieb: > Ich hab schon fast die Vermutung, dass man beide Dreiecke flood-fillen > und anschließend miteinander verunden sollte, um die Schnittfläche zu > erhalten. Wenn du nur Pixelgenaues Ergebnis brauchst, ist das eine Möglichkeit. Die andere: Das eine Dreieck wird in eine Pixelmaske gerendert, beim 2ten Dreieck dient diese Pixelmask dazu, die Pixel auszusieben, die ausserhalb liegen. Läuft im Grunde auf dasselbe raus, ist aber von der Organisation her u.U. einfacher. Mit OpenGL würde zb die Graphikhardware (Stencil Buffer) diese Operation machen können. > Bruteforce-Rechenaufwand gehofft, weil es eigentlich triangulierte > konvexe Polygone sind und ich den Schnitt für jedes Teildreieck > berechnen muss ... Dann musst du rechnen. Hast du viele kleine Dreiecke sind die schneller gerendert als du alle Schnittpunkte ausrechnen kannst, von denen es immerhin maximal 6 geben kann. Die musst du dann auch noch klasssifizieren etc. Du sagst dass dein Dreiecke durch triangulieren entstehenen. Daher vermute ich mal, dass du eigentlich die Intersection 2-er Polygone brauchst. Von daher müsstest du überlegen, ob du nicht gleich aus allen Dreieck eines Polygons einen Stencil Buffer aufbauen kannst durch den dann das andere Polygon durch muss.
Ach ja: Suchbegriffe wären: Polygon boolsche Operationen Triangle Intersection triangle boolean operation Auch wenn ich nicht denke, dass du mit Dreieck viel finden wirst. Ich denke du müsstes auf eine Lib für allgemeine boolsche Polygone ausweichen, denn nur für 3-Ecke macht man solche Operationen eher selten. Vor Jahren hab ich mal eine Lib namens 'PolyBoolean' benutzt. Keine Ahnung obs die noch gibt. Die hat sich ganz geschickt um die klassischen Probleme in den boolschen Operationen rumgebracht, indem sie alles in Integerkoordinaten abgebildet hat.
Karl heinz Buchegger schrieb: > Läuft im Grunde auf dasselbe raus, ist aber von der Organisation her > u.U. einfacher. Mit OpenGL würde zb die Graphikhardware (Stencil Buffer) > diese Operation machen können. Ich hab leider kein OpenGL, weil das später als Javascript in einem normalen Webbrowser laufen soll. Ich glaub mir bleibt nichts anderes übrig, als erstmal eine schnelle Vor-Auswahl mit z.B. Um-Kreis zu machen und dann nochmal genauer hinzuschauen, wo es nötig ist. Von O'Rourke hab ich gesehen, gibts einen Algorithmus für den Schnitt zweier konvexer Polygone mit Aufwand O(n+m), für den ich aber nirgends eine Implementierung gefunden habe. Man findet auch sonst kaum was dazu, nicht mal eine richtige Erklärung. Es soll dazu ein Paper geben, aber das gibts nicht online, sondern nur in gedruckter Form in einer uralten Fachzeitschrift. -- Helli
Sven H. schrieb: > Das ist ganz sicher nicht Mathematik der achten Klasse. Für 2 Deiecke auf einer Ebene? Doch ist es. Es geht rein um das Schneiden der Kanten. Der Rest ist Organisation und Klassifikation der Schnittpunkte zu neuen Polygonen (die Intersection 2-er Dreicke ist nicht notwendigerweise wieder ein Dreiecke) Ärger machen nur die notorischen Solid-Modelling Probleme: Dreiecke die gleiche (oder fast gleiche) Eckpunktskoordinaten aufweisen, kollineare Kanten, schleifende Schnitte, etc. Die sorgen dafür, dass ein eigentlich einfaches Problem in der Praxis einen Haufen Ärger macht. Aber die grundlegende Mathe dahinter ist einfach nur das Schneiden zweier Linien.
Noch eine Idee: Da ein Dreieck ja notwendigerweise konvex ist, könnte man auch überlegen ob man nicht ein allgemeinenes Clipping Verfahren dahingehend adaptieren kann. Clipping Verfahren wie sie zb benutzt werden, um Ausgaben in ein Grafik-Fenster auf den sichtbaren Fenster Bereich zurechtzuschneiden. Da gibts zb auch recht einfache Ansätze: Eine Gerade zerschneidet die Ebene in 2 Teile. Man nimmt nun das erste Dreick her. Vom 2-ten Dreieck nimmt man eine Kante (die ja eine Gerade ist). Diese Gerade schneidet das Dreieck irgendwo (oder auch nicht). Falls es zerschnitten wird, erhält man 2 Polygon (sonst nur eines). Mit der Geraden lässt sich nun jeder der beiden Einzelteile klassifizieren auf welcher Seite der Geraden er liegt: innerhalb oder ausserhalb des 2.ten Dreiecks, wenn man nur diese eine Kante in Betracht zieht. Uns interessiert nur der Teil innerhalb. Mit dem gehts weiter Dasselbe macht man mit der 2.ten und 3.ten Kante des 2te Dreiecks. Nach jeder Operation bleibt nur der Teil des ersten Polygons übrig, der von dieser Kante aus gesehen, auf der richtigen Seite liegt, so dass er innerhalb des Dreiecks liegt. -> sind alle 3 Kanten abgearbeitet, bleibt ein Polygon übrig, welches den 'sichtbaren' Teil des ersten Dreieck im zweiten repräsentiert - die Intersection
Karl heinz Buchegger schrieb: > Ärger machen nur die notorischen Solid-Modelling Probleme: Dreiecke die > gleiche (oder fast gleiche) Eckpunktskoordinaten aufweisen, kollineare > Kanten, schleifende Schnitte, etc. Die sorgen dafür, dass ein > eigentlich einfaches Problem in der Praxis einen Haufen Ärger macht. > > Aber die grundlegende Mathe dahinter ist einfach nur das Schneiden > zweier Linien. Genau, du hast es erfasst! Das ist das Hauptproblem. Man muss sich um soviel Kram drumrum kümmern, dass man da gleich mal einige Stunden dran sitzt und auch noch verifizieren muss, ob es funktioniert und ob alle Sonderfälle abgefangen sind ... Ich kann mich da an ein anderes triviales Problem erinnern, bei dem ich ein simples Dreieck im 3D in einen Voxelspace eintragen wollte ... Ich glaub, ich bin da ne Woche dran gesessen. Man glaubt garnicht, wo es überall Probleme geben kann, wobei das Problem doch scheinbar so einfach zu lösen ist ... Daher machen mich solche Aussagen wie "8. Klass Problem" sauer, weil das nur von Leuten kommen kann, die viel labern aber selbst nie was machen ... -- Helli
Karl heinz Buchegger schrieb: > Zum skizzierten Verfahren eine Grafik Sieht interessant aus! Aber wie würde der Fall funktionieren, dass eine Linie nicht das Dreieck in 2 Hälften schneidet? D.h. die Spitze eines Dreiecks schaut in das andere, d.h. der Schnitt ist ein Dreieck.
Helli schrieb: > Ich kann mich da an ein anderes triviales Problem erinnern, bei dem > ich ein simples Dreieck im 3D in einen Voxelspace eintragen wollte ... > Ich glaub, ich bin da ne Woche dran gesessen. Man glaubt garnicht, wo es > überall Probleme geben kann, wobei das Problem doch scheinbar so einfach > zu lösen ist ... Hi, hi Als ich mit Solid Modelling angefangen habe, hab ich mir das Buch vom Mäntylä (Schreibweise mag falsch sein) geholt, weil da offenbar eine Implementierung vorhanden war, die er beschreibt. Der Aufbau mittels Euler Operationen klang ebenfalls logisch. Der Mann wusste offenbar wovon er redet. Ich habe 10 Jahre lang immer wieder daran gearbeitet (pro Jahr mit Sicherheit mehr als 100 halbe Nächte) den Code lauffähig zu bekommen. Zuerst die trivialen C-Fehler, dann die Schnittoperation, dann die restlichen boolschen Operationen. Irgendwann hab ich dann eingesehen, dass sein Klassifikationsschema nicht funktioniert und hab einen anderen Ansatz gewählt.
Helli schrieb: > Karl heinz Buchegger schrieb: >> Zum skizzierten Verfahren eine Grafik > > Sieht interessant aus! Aber wie würde der Fall funktionieren, dass eine > Linie nicht das Dreieck in 2 Hälften schneidet? Die Schnittkante ist eine unendliche Gerade! (siehe zb in meinem Beispiel die rechte Kante) Entweder sie Teil das Dreieck, dann hat man 2 Teilergebnisse, oder sie teilt es nicht, dann hat man nur 1 Teilergebnis. Wie auch immer, jedes der Teilergebnisse wird in Bezug auf die Schnittgerade klassifiziert. Liegt es auf der richtigen Seite (dort wo auch das 2.te Dreick liegt) oder tut es das nicht. Hat man 2 Teilergebnisse und liegt das erste auf der richtigen Seite muss man das andere gar nicht mehr untersuchen und vice versa: ist das erste falsch, muss das zweite richtig sein. Bei nur einem Teilergebnis ist die Sache einfacher: liegt es auf der falschen Seite, dann ist die Schnittmenge leer. > D.h. die Spitze eines > Dreiecks schaut in das andere, d.h. der Schnitt ist ein Dreieck. Was du im Grunde machst. Du malst die beiden Dreiecke auf ein Blatt Papier. Rot und Blau. Und jetzt knickst du das Papier an einer der blauen Kanten nach hinten weg und fragst dich welche der beiden Papierseiten du weiterhin ansehen musst (natürlich die auf der die blaue Fläche ist) Dasselbe für die nächste Kante und die nächste. Das was dir am Papier als rote Fläche übrig bleibt, ist die Intersection.
Karl heinz Buchegger schrieb: > Sven H. schrieb: >> Das ist ganz sicher nicht Mathematik der achten Klasse. > > Für 2 Deiecke auf einer Ebene? > Doch ist es. Es geht rein um das Schneiden der Kanten. ... > Aber die grundlegende Mathe dahinter ist einfach nur das Schneiden > zweier Linien. So gesehen ist alles mathematik der 8ten Klasse. Oder der 7ten oder noch eher. Da werden nunmal Grundlagen vermittelt. Das Lösen komplexer Probleme gehört sicherlich nicht dazu. Und wenn das hier kein komplexes Problem sein soll, dann wundert es mich, warum ihr soviel darüber diskutieren müsst... Jetzt habe ich aber noch ne Frage zum Thema: Geht es um Dreiecke im 2D Raum oder um Dreiecke im 3D Raum (wobei letztere ja eigentlich keine Dreiecke sind.. irgendwie)?
Sven H. schrieb: > Geht es um Dreiecke im 2D Raum oder um Dreiecke im 3D Raum (wobei > letztere ja eigentlich keine Dreiecke sind.. irgendwie)? Es geht um Dreiecke in 2D ... Eigentlich geht's um konvexe Polygone in 2D, aber ich dachte, das Problem wäre einfacher zu lösen, wenn ich es auf Dreiecke runterbrechen würde. Bei konvexen Polygonen ist das trivial ...
Sven H. schrieb: > So gesehen ist alles mathematik der 8ten Klasse. Oder der 7ten oder noch > eher. Da werden nunmal Grundlagen vermittelt. > > Das Lösen komplexer Probleme gehört sicherlich nicht dazu. Und wenn das > hier kein komplexes Problem sein soll, dann wundert es mich, warum ihr > soviel darüber diskutieren müsst... :-) Weil es im Prinzip sehr einfach ist. So wie auch, im Prinzip, die Geradengleichung aus der Mittelschule eigentlich sehr einfach ist, und sie trotzdem im Bereich 'computational Geometry' nicht zu gebrauchen ist, weil man sich mit den Sonderfällen (die in der Schule wohlweislich ausgespart bzw. mal nebenher erwähnt aber ansonsten ignoriert werden) in Teufels Küche manövriert. Wie gesagt: Im Prinzip ist es einfach. Der Teufel steckt im Detail. > Das Lösen komplexer Probleme gehört sicherlich nicht dazu. Da hast du schon recht. Wobei die Komplexität hier aus den Details entsteht.
Helli schrieb: > Es geht um Dreiecke in 2D ... Eigentlich geht's um konvexe Polygone in > 2D, Hmm. Dann solltest du dir wirklich mal eine Lib ala PolyBoolean ansehen. > aber ich dachte, das Problem wäre einfacher zu lösen, wenn ich es > auf Dreiecke runterbrechen würde. Triangulierung kann wieder neue Probleme schaffen: * Der Umgang mit Löchern in Polygonen * Des öfteren entstehen sehr schmale, aber dafür sehr lange Dreiecke (brr, die sind besonders unangenehm) * Und zu guter letzt mussen natürlich die Ergebnisdreiecke wieder zu polygonalen Ergebnissen zusammengesetzt werden, was auch nicht unbedingt trivial ist.
Die korrekte Suchphrase wäre "triangle intersection algorithm" gewesen. http://softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm#Triangle-Triangle
Frank schrieb: > Die korrekte Suchphrase wäre "triangle intersection algorithm" gewesen. > > http://softsurfer.com/Archive/algorithm_0105/algorithm_0105.htm#Triangle-Triangle Das berechnet etwas anderes :-)
>Das ist ganz sicher nicht Mathematik der achten Klasse.
Der Satz ist durchaus nicht ganz falsch. Ich kann mich erinnern, daß wir
genau in der 8.Klasse den Schul- und später Landeswettbewerb Mathematik
hatten und es gab dort in der Tat solche Aufgaben.
Ich hatte allerdings nur deshalb keine Probleme mit diesen Sachen, weil
ich wegen meiner Telespieleprogrammiererei im Vorfeld schon solche
Sachen ausgetüftelt habe. (z.b. die Frage: "rammt" ein abgeschossener
und sich drehender Raumschiffbrocken den Spieler, oder nicht).
Damals wusste ich die Lösungsformeln für solche Probleme mehr oder
weniger auswändig. Heute ist alles weggeblasen, weil man den ganzen Tag
Projektleitermist machen muss :-)
Es ist schon erstaunlich, wie weit man kommen kann, wenn man als Schüler
Zeit ohne Ende hat und sich mit den Sachen befasst.
... Heute ist alles weggeblasen, weil man den ganzen Tag Projektleitermist machen muss ... Ja, ja: Genies wie du haben es wirklich schwer.
In Matlab: % this define the vertexes (x,y) of first triangle trian1x =[ 0 0.5 1 0]; trian1y =[ 0 1 0 0]; % this define the vertexes (x,y) of second triangle trian2x =[ 0 0.25 0.5 0]; trian2y =[ 0 0.5 0 0]; % (xi,yi) are the intersection points [xi,yi] = polyxpoly(trian1x,trian1y,trian2x,trian2y,'unique'); figure, plot(trian1x,trian1y,'b') hold on plot(trian2x,trian2y,'r') hold on plot(xi,yi,'*g') Quelle: https://de.mathworks.com/matlabcentral/answers/124271-intersection-of-two-triangles ...warum bei 0 Anfangen wenn andere schon Vorarbeit geleistet haben...?? Ich programmiere die FEM auch nicht neu...ich nutze schon vorhandene Ansätze...
Thread beobachten
Seitenaufteilung abschalten
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.