Triangulations Algorithmus

[Lambda]

Ich benötige die Triangulation einer Punktwolke ohne Überlappungen oder Duplikate. In der englischen Community habe ich das Thema schon länger vielfach in mehreren Threads angesprochen, leider ohne Antwort.

Es wurden 3 Delaunay Versionen sowie eine individuellere für PB umgesetzt.

1. Delaunay von STARGATE: Punkte müssen geordnet sein, die Ausgabe enthält anschließend nur eine Linie
2. Delaunay von Comtois*: Funktioniert im Prinzip, es entstehen allerdings verhäuft Duplikate
* von mir abgeändert zu Verdeutlichung der Polygone
3. Delaunay von unbekannt: ebenfalls öfters doppelte Polygone an gewissen Punkten/Winkeln
4. Seymour: etwas spezieller, liefert leider auch Teils überlappende Polygone

Möglicherweise habe ich Delaunay auch falsch verstanden, und es ist nicht fehlerfrei. Gibt es noch andere Snippets oder einfach relevante Algorithmen denen ich nachgehen kann? Bitte keine brainstorming Theorien, es soll in der Praxis fehlerfrei sein.

Die Aufgabe ist die Lösung von Punkt-Clustern die mehr als 3 Punkte enthalten. Sind keine Kontur-Punkte enthalten sind es in der Regel gerade mal 4 Punkte. Um Rundungsfehlern entgegen zu wirken jongliert das ganze nur mit Ganzzahlen und wird später skaliert.

Hier der Prototyp - relevant sind nur äußere Zellen die geschnitten werden

[chi]

Hi Alexi,

kann Dir bei deinem Problem zwar nicht aktiv helfen, aber vielleicht helfen folgende Links irgendwie weiter?!

http://code.google.com/p/poly2tri/
delaunay site:blitzbasic.com
voronoi site:blitzbasic.com

Lg, chi

[Lambda]

Zu den standard Verfahren finde ich genügend Quellen, trotzdem danke. In der englischen bleiben sämtliche Threads gänzlich unbeantwortet, als wäre das Thema zu hoch, denn viele pirschen schon nach simplen Anfängerfragen.

Scheinbar muss ich das (wiedermal) auf eigene Faust angehen. Das ist nun schon sehr subatomar von meinem eigentlichen Projekt aus betrachtet, schade das hier PB die Base fehlt.

[chi]

Darf man fragen worum es in deinem "eigentlichen Projekt" geht?

[Lambda]

Um das zu entschachteln.

- die Triangulation ist das letzte Puzzle des CGS (Cluster Grid Sub-Division)
- was die perfekte Terrain-Anschmiegung (3D) des EPS (Environment Processing System) ermöglicht, extrudierte Bezier Pfade etc.
- was eines der Grundsysteme für einen sehr umfangreichen Szenen Editor darstellt
- welcher für das Projekt entwickelt wird, ein MMORPG nach der Serie "My Little Pony"

Dieser Szenen Editor ist sehr umfangreich anpassbar konzipiert, weshalb ich das ganze auch für eine kostenlose PB Version noch anpassen würde. Schade nur, dass das niemand unterstützen möchte oder kann. Das Problem ist, ich möchte keinen pseudo halbwegs verwendbaren Algorithmen nachgehen, sondern brauche eine solide Lösung, dabei geht es nicht in erster Linie um Geschwindigkeit.

[alter Mann]

Tipp: OpenGL Beispiel siehe hier

[Lambda]

Darauf bin ich auch bereits gestroßen, allerdings frage ich mich ob dadurch nicht eine gewisse Abhängigkeit entsteht? Es wäre auch schon fast overdressed für einen derart kleinen Aufgabenteil. Beschäftige mich mal eben damit, was anderes außer Zeit auch noch in eine ordentliche Triangulation zu investieren bleibt mir daneben wohl kaum übrig.

Btw: kann es sein das die Sache extrem langsam ist? Habe die Triangulation eben nur an der Stelle rechnen lassen an der sie eingesetzt werden müsste - nach etwa 3-4 Sekunden 1 Schritt abgeschlossen.

[DrShrek]

schau dir doch mal das an:
http://sites-final.uclouvain.be/mema/Poly2Tri/

[NicTheQuick]

Ich hätte jetzt auch den Sweep-Line Algorithmus vorgeschlagen, der ist einfach und solide. Ich bin nur noch nicht dazu gekommen ihn zu programmieren, sonst hätte ich dir schon helfen können.

[alter Mann]

Kann eigentlich nicht sein, dass das zu langsam ist - aber wer weiß, wie das Dein OpenGL-Treiber umgesetzt hat.

Sonst kann man auch wie folgt vorgehen :
1. nimm 2 aufeinanderfolgende Kanten (i,i+1)
2. bilde das Kreuzprodukt
3. Kreuzprodukt <= 0 (bei math. positivem Umlauf des Polygon)
i+1 -> weiter bei 1.
4. teste alle Punkte des Polygons, die nicht zu den Kanten gehören , ob sie innerhalb des Dreieck liegen
Punkt innerhalb -> i+1 -> weiter bei 1.
5. bilde Dreieck aus den 2 Kanten, ersetze die 2 Kanten durch die neue Kante aus den Endpunkten der Ursprungskanten
6. mehr als 3 Kanten im Polygon -> weiter bei 1.

- dieser Algorithmus kommt immer zu einem Ende

Punkt innerhalb eines Dreiecks :
- Bilde Vektoren zu den Endpunkten des Dreiecks
- Bilde umlaufend das Vektorprodukt zwischen je 2 Vektoren
- sind alle Vektorprodukte >= 0 (bei math. positivem Umlaufsinn) liegt der Punkt im (oder wenn ein Vektorprodukt=0 auf dem Rand vom) Dreieck