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.
>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.
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...
