Hallo,

ich habe ein Dreieck und ein Polygon (2D) und möchte nun das Polygon vom Dreieck "wegschneiden", also die Dreiecke ermitteln, die das Dreieck minus das Polygon ergeben. Habe im Anhang eine kleine Skizze gemacht (violett: Ursprungsdreieck, grün: Polygon, schwarz: die gesuchten Dreiecke). Für Hilfe wäre ich sehr dankbar.

Gruß Joni.

Das Thema haben wir mal in einem Thread über GUI gehabt.
Ich habe eine Lösungsansatz genutzt, wo ich leider gerade nicht den namen kenne :\ .
Man nimmt ein äusseren Punkt und sucht den kürzesten inneren Punkt dazu.
Die beiden Punkte bilden eine Kante(Edge), welche die Fläche in eine offenes Polygon aufteilt.
Nun kann man einen sehr einfachen Algo verwenden, der prüft, ob ein Punkt ein sogenanntes Ohr(es liegt kein Punkt zwischen den zu bildenen Triangle) und convex ist, dann kann man die aktuellen 3 Punkte verbinden. Dann sucht man den nächsten Punkt und füllt das Polygon somit mit Triangle auf.
Vieleicht kennt wer den Namen des Algos ^^ und hier ist noch die Umsetzung zu finden https://svn.linuxprofessionals.org/filedetails.php?repname=karmarama&path=%2Fprerelease%2Fwrapper%2FKar_OGLContext.pas .
Die Methode procedure TKar_OGLShape.Tesselieren; ist das wichtige, der rest gehört entweder zur gui oder sind Hilfsfunktionen für die Tesselierung.
Der Algo betrachtet allerdings nur offene Polygone, also musst du noch die Verticeliste entsprechend, dem oben genannten Schritt zum öffnen durchführen.

Das Problem was bei den ganzen Tesselieralgos gibt sind geschlossende Polygone, wie sie bei deinem gewollten Ergebnis entstehen und die oben genannten Variante(das Polygon zu öffnen) macht den algorythmus wesentlich einfacher und um ein vielfaches schneller.

Also ist im Prinzip der erste Schritt immer zu gucken, ob deine Schnittmenge ein offenes Polygon ergibt und wenn nicht muss es geöffnet werden.
Dann kannst du über ein Algo deiner Wahl das Polygon sehr einfach tesselieren.
Der Vorteil daran ist, dass man es nicht sieht, dass es ein offenes Polygon ist, man merkt es nur an dem Speicherverbrauch, da 2 Vertice mehr anfallen oder bei indizierten verticelisten 2 indices mehr anfallen.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Hallo,

erst einmal vielen Dank für die Antwort. Ich habe versucht, es nach deinem Ratschlag zu realisieren, es klappt jedoch nicht. FCalculatedVertice sind doch die Ausgangskoordinaten und FTriangleIndices die zu berechnenden Dreicke? Ich habe den folgenden Code geschrieben:
und in deinem Code FCalculatedVertice durch Points ersetzt (und die Datentypen entsprechend angepasst). Wenn jetzt das array l die Länge 5 hat, berechnet er 2 Dreiecke und das wars. Wenn l die Länge 6 hat, rechnet er sich zu Tode (findet 1 Dreieck und kein weiteres). Hat jemand eine Idee, was ich falsch mache? Für Hilfe wäre ich sehr dankbar.

Gruß Joni.

Also die 3 Listen die du hast sind richtig, nun füllst du eine mit den verticedaten, eine mit den zu schneidenen polygon und eine bleibt erstmal leer.
Nun musst du für jedes Vertice, aus deinem Triangle, die Länge zu jedem Vertice des zu schneidenen Polygons nehmen.
Du hast einfach das erste Vertice genommen, was natürlich bei steigender komplexität von Orginal und zu schneidenem Polygon falsch wird(es könnte ein Vertice dazwischen liegen und damit würde man keine Kante bilden können).
Wenn du nun die kürzeste Verbindung ermittelt hast, dann kannst du in die Leere liste nun die Vertice vom Triangle hinzufügen.
Die Vertice sollten sortiert werden, erst nach Y und wenn doppelte Y werte auftreten dann nach X sortieren.

Im Anhang stimmt zwar die Tesselierung nicht aber ich glaube es veranschaulicht das vorgehen.
http://www-lehre.inf.uos.de/cg2/material/20021218/Tesselation.htm
Hier kannst du das Dokument finden, welches ich als Basis genommen hatte.
Wenn du noch weitere Infos zu dem Thema suchen willst, Ear clipping war der Suchbegriff für den Algo.
http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
Das Paper ist noch ziemlich gut, leider hatte ich es erst recht spät gefudnen.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Hallo,

schonmal vielen Dank, es klappt habe den Ratschlag befolgt und vom Basis-Triangle auch den nächsten Punkt gesucht und die Punkte nach dem 2. Link korrekt sortiert. Das ganze hat noch ein paar Bugs (bleibt manchmal hängen oder es fehlen einige Triangles), aber ich denke das wird noch klappen. Nochmal vielen Dank, TAK2004!

Gruß Joni.

Hallo,

meine Version war doch etwas instabil und hatte auch einige Macken (Triangles fehlten ab und zu, das Programm blieb öfters hängen), aber im Wiki war was sehr hilfreiches (hab in den Statistiken gestöbert und das ziemlich weit unten gefunden).

Gruß Joni.

Is gerade erst 1-2 Wochen alt. Vielleicht war dein Thread sogar die Inspiration dazu. Falls du dich mit Triangulation genauer beschäftigst, kannst du uns gern auf dem Laufenden halten und selber Wiki Einträge verfassen.

_________________
Blog: kevin-fleischer.de und fbaingermany.com