Punktgitter Triangulation

[Lambda]

Ich benötige eine gleichmäßige Triangulation eines Punktgitters. Es entstehen also keine sonderbaren Situationen, lediglich das Triangulation-Muster muss im "Zig-Zag" verlaufen.

Triangulation erfolgt pro Polygon, jedes Polygon wird also einzeln trianguliert. Auch die Eckpunkte pro Polygon sind natürlich vorhanden nur hier nicht dargestellt.

Wäre super wenn jemand eine fixe Lösung hat.

[NicTheQuick]

Wenn das mit dem Zig-Zag nicht wäre, hätte ich die Delaunay Triangulation vorgeschlagen. Da gibt es genügend andere Codes zu und sollte deshalb leicht umsetzbar sein. Ich hatte das irgendwo auch mal so im Studium gehabt und programmiert.

[Danilo]

Wenn das mit dem Zig-Zag nicht wäre, hätte ich die Delaunay Triangulation vorgeschlagen.

Vor ein paar Tagen im engl. Forum: Delaunay triangulation.

Diese Version nimmt allerdings immer den äußersten Umriss des Polygons, wodurch
keine "Buchten" möglich sind.

[Lambda]

Delaunay bereits getestet, leider nicht anwendbar, teils werden Polygone Kreuz und quer vielfach überlappend gezogen.

Mein Ansatz wäre eher im Raster, wodurch auch festgestellt werden kann ob es sich um ein Zig oder Zag handelt. Die Umrangungspolygone müssen natürlich keinem Muster mehr entsprechen.

[NicTheQuick]

Delaunay bereits getestet, leider nicht anwendbar, teils werden Polygone Kreuz und quer vielfach überlappend gezogen.

Das würde ich gerne mal sehen. Da war wohl der Code falsch. Überlappen wird da nichts und die Größen der einzelnen Polygone werden optimal berechnet. Das ist nicht umsonst das Standardverfahren dafür.

[Lambda]

Auch wenn die Punktreihenfolge ungeordnet ist? Denn erst wird das Raster (innere Unterteilungen) und anschließend die Schnittlinien berechnet.

Edit: vermutlich die Delaunay Umsetzung, dieser war von STARGATE, versuche mal die Comtois'sche.

[NicTheQuick]

Ja, das ist eigentlich normal, dass die Punktreihenfolge ungeordnet ist. Im Grunde gibt man dem Algorithmus eine Punktwolke und er macht daraus ein schickes Gitter, wo jeder Punkt auf der Ecke eines Polygons liegt.
In dem Wiki-Artikel sind ja unten ein paar Links, vielleicht kannst du dir da etwas herleiten, wenn der PB-Code aus dem englischen Forum nicht funktioniert. Immerhin gibt es verschiedene Herangehensweisen dafür.

[Lambda]

Die Lösung von Comtois geht definitiv, nur hätte er das etwas autonomer umsetzen können als hardcoded in französisch. Wenn man auch noch Kürzel in französisch nimmt, kann es nichtmal übersetzt werden. Naja, einem geschenkten Gaul..

Edit: Jemand noch Ideen?

Edit2: Der Code ist sehr fies, eine anpassbarere Umsetzung wäre sehr schön, weniger "dahingerattert"

Edit3: Da ist nun der Fehler, die Version kommt nur mit Ganzzahlen zurecht.

[alter Mann]

...wenn ich das richtig interpretiere, soll eine vorhandene Triangulation durch ein Raster verfeinert werden...

in diesem Fall würde ich wie folgt vorgehen :
- für jedes Rasterquadrat - Test, ob alle Eckpunkte innerhalb des Dreiecks
-> wenn ja Triangulation im Zig-Zag
-> wenn nicht - Schneiden (und Teilen) der Dreieckskanten (Umlaufsinn beachten!) mit dem Rasterquadrat
- Schneiden (und Teilen) der Quadratkanten (gleicher Umlaufsinn!) mit dem Dreieck
- Zusammensuchen der Kontur indem (angefangen mit einer im Quadrat liegenden Dreiecksstrecke)
Anfangs- und Endpunkte der Strecken verglichen werden
-> Ergebnis ist (immer) ein konvexes Polygon, das einfach von einem Eckpunkt aus trianguliert werden kann

[Lambda]

Hier das ganze mal in Echtzeit mit der Struktur im Hintergrund.

Edit: nun vollständig. Nachdem das Umrisspolygon wesentlich Detailreicher sein kann, wäre es nur Logisch alle Punkte pro Raster-Polygon zu sammeln welches eingehalten werden muss. Benötigt ist also ein schneller also welcher entscheidet ob ein Punkt oberhalb, unterhalb eines diagonal geteilten Quaders liegt oder überhaupt.

Danach die Triangulation dieser Punkte pro Cluster, woran der Algo kein Muster mehr einhalten muss - für extrem hoch detaillierte Kurven müsste ehr allerdings konkave Wolken meistern.