Hallo,

ich habe ein beliebiges Polygon, das ich in Dreiecke zerlegen möchte. Hab aber leider keine wirkliche Vorstellung, wie ich das per Algo anstellen soll. Könnte mir vielleicht mal jemand ein paar Ansätze geben? Bitte nur Ansätze was ich machen muss und keinen fertigen Code.

mfg, Lt.Cmd.Data

Ohhh...Das wird nicht so einfach gehen.

Das suchwort für das internet ist Tesselierung und Triangulation. http://wiki.delphigl.com/index.php/Tesselierung

Das Problem ist leider nicht ganz trivial, wie du an dem im Artikel verlinkten Text sicherlich merken wirst.

Aber du kannst dich ja mal einlesen, und dann sagen ob du in der Richtung noch was machen willst.

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

Naja, das Problem liegt halt darin, dass ich einen Raum mit einer Grundfläche in der Form eines Polygons habe. Um diese Grundfläche auch zu erstellen könnte ich ja theoretisch GL_POLYGON verwenden. Das das Polygon aber nicht gleichmäßig ist, klappt das leider nicht. Und ein einfaches Quad will ich auch nicht nehmen.
Kann man das irgendwie machen ohne das Polygon in Dreiecke zu zerteilen?

Ich würde mal sagen das kommt darauf an. Wenn du dich nur im Raum befindest dann spricht ja nichts dagegen ein Quad zu verweden. Wenn man auch außerhalb sein kann, dann müsstest du es schon irgendwie zerlegen. Aber woher hast du denn den Raum? Selber gemacht? Dann sollte es eigentlich kein Thema sein diesen per Hand zu splitten.

Bzw wäre auch mal interessant wie der Grundriss des Raumes aussieht? Also wie denn das Polygon aussehen würde? Evtl gehts ja noch ganz anders.

Ich bekomme von meinem Lehrer die Koordinaten für das Polygon. Deshalb müsste das halt für jedes Polygon möglich sein, egal wie es aussieht. Ob ich nur innerhalb des Raumes bin oder auch außerhalb weiß ich noch nicht genau. Aber eigentlich wollte ich schon auch nach außen gehen (gibt für Optik und Funktionalität auch Bewertung).

Aber eine Beispielform für ein Polygon ist im Anhang.

Darf man mal fragen was du machst, dass ein Lehrer so etwas haben will?

Ich hatte auch mal bei Google geschaut und folgendes pdf gefunden. Sah auch ganz brauchbar aus. So beim überfliegen.
http://www-gs.informatik.tu-cottbus.de/~wwwgs/cg_v08c.pdf

Ich hab mal nachgeguckt ("Realtime Colission Detection" - 12.5.1 "Triangulation by EarCutting) und es scheint gar nicht soo schwer zu sein, ein solches Polygon in Dreiecke zu zerlegen.

Habs nur grob überflogen, aber vllt hilfts dir trotzdem:
Nehmen wir mal an, du hast die ganzen Eckpunkt in ner Liste, und zwar in der Reihenfolge sortiert, wie sie entlang der Außenlinie vorkommen. Dann kannst du die Nachbarn eines Vertex bestimmen, in dem du in der Liste einen vor bzw. zurück gehst.
Earcutting geht nun so. Du fängst mit einem Vertex an, und baust ein Dreieck aus diesem Vertex und den beiden Nachbarn. Wenn die Verbindungslinie der beiden Nachbarn im Polygon drin liegt, dann ist es ein gültiges Dreieck, wird in einer anderen Liste abgespeichert, und das Ausgangvertex wird aus der Liste gelöscht. Dann nimmst du dir das nächste Vertex vor usw.
Ob die Verbindungslinie im Polygon liegt, und das Dreieck somit gültig ist, erkennst du daran, dass das Dreieck in der gleichen Richtung vorliegt, wie das Polygon. Wenn z.B. das Polygon im Uhrzeigersinn vorliegt, dann sind alle Dreiecke gültig, die auch im Uhrzeigersinn vorkommen. Bei allen anderen ist das gewählte Vertex Concav, und das Dreieck liegt außerhalb des Polygons.
Am Ende hast du dann das gesammte Polygon, auch wenns vorher concav war, in Dreiecke zerlegt. Funzt nur nicht, wenn dein Polygon ein Loch hat. Aber das sah im Bild ja nicht so aus.

_________________
[18:30] tomok: so wie ich das sehe : alles. was nich was anderes ist als nen Essay ist nen Essay

hi, i'm a signature viruz, plz set me as your signature and help me spread

Vor einer weile hatten wir auch mal ne New zur FastGEO. Die kann das laut featureliste auch. Allerdings dürftest du ne weile brauchen das da zu finden.