mikrocontroller.net

Forum: PC-Programmierung Schnitt zweier Dreiecke in 2D


Autor: Helli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: DerAlbi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Helli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Helli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das hier könnte dir zb Ansätze und Gedanken liefern
http://gts.sourceforge.net/

Autor: Sven H. (dsb_sven)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das ist ganz sicher nicht Mathematik der achten Klasse.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:
Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Zum skizzierten Verfahren eine Grafik

Autor: Helli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Helli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Sven H. (dsb_sven)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)?

Autor: Helli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 
...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Frank (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die korrekte Suchphrase wäre "triangle intersection algorithm" gewesen.

http://softsurfer.com/Archive/algorithm_0105/algor...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Frank schrieb:
> Die korrekte Suchphrase wäre "triangle intersection algorithm" gewesen.
>
> 
http://softsurfer.com/Archive/algorithm_0105/algor...

Das berechnet etwas anderes :-)

Autor: Frank (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nachsatz: hier gibts weitere Anregungen:

http://www.cap-lore.com/MathPhys/IP/

Autor: Jürgen S. (engineer) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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.

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
...  Heute ist alles weggeblasen, weil man den ganzen Tag 
Projektleitermist machen muss ...

Ja, ja: Genies wie du haben es wirklich schwer.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.