Delaunay-Triangulation

[jfheins]

Ist es eine Option, einen vorhandenen Netzgenerator herzunehmen?
Da habe ich zum Beispiel Triangle gefunden. Dem kann man eine passende Datei geben, und er gibt die das Netz zurück.

Ansonsten: Advancing-Frint geht wie folgt vor: Du unterteilst deine Außenkontur zunächst in Knoten und Kanten. Da kannst du ganz stumpf machen, dass du eine Wunschlänge definierst, und dann an jeder Polygonkante schaust, wie viele Unterknoten da denn eingezogen werden müssen.

Advancing-Front geht jetzt schrittweise die Knoten durch, die auf der aktuellen Front liegen und verkleinert die Front (bzw. genauer: das eingeschlossene Gebiet). Wenn die Front leer ist, hast du das Gebiet vollständig vernetzt. Es gibt dabei drei Möglichkeiten:

1. Es wird ein neuer Punkt mit zwei Kanten erzeugt. Bevorzuge ein gleichseitiges Dreieck.
2. Es wird ein Punkt erzeugt, der drei Kanten erhält
3. Es wird eine Kante erzeugt

Welche Fall eintritt, hängt von dem Winkel der aktuellen Kante mit der nächsten Kante zusammen. Guckst du hier: http://www.iue.tuwien.ac.at/phd/fleischmann/node39.html der Winkel alpha.

Das Netz, dass daraus hervoirgeht, kannst du dann natürlich auch noch auf Delaunay überprüfen und Kanten ggf. flippen.

Allgemein würde ich dir aber empfehlen, einen fertigen Netzgenerator zu verwenden.

Edit: Habe gerade noch eine gute Arbeit gefunden: http://elib.uni-stuttgart.de/opus/vo.../geomaindt.pdf
Ab Seite 29.

[Bjoerk]

Ich fürchte du überschätzt (mal wieder) meine mathematischen Fähigkeiten. Ich hab' Anfang der 80iger studiert und spätestens Anfang der Neunziger so ziemlich wieder alles vergessen (mit Ausnahme der TM natürlich). Ich krieg das schon hin, aber anders. Ein PolygnonHatch hab' ich schon, da kann man sogar Winkel und Abstand einstellen (ist mir vorhin eingefallen). Das könnte ich als Punkegenerator verwenden. Ich kann es nur nicht einbauen weil solange meiner Delaunaytriangulation die Umkreisprüfung fehlt werdern die Dreiecke (teilweise) falsch. Deshalb die Frage nach einem eleganten Flip-Algorithmus?

[Bjoerk]

So. Jetzt wirds langsam. Flippen geht aber Hatch ist nicht so prickelnd.

Jens, weißt du noch nach welchem Verfahren du deine Polygone "vorgedreieckt" hast?

[Jens01]

Zitat:

"vorgedreieckt"

Äh, was meinst Du genau?

[Bjoerk]

Zitat von Jens01:

Zitat:

"vorgedreieckt"

Äh, was meinst Du genau?

Damit könnte man Polygone wunderbar Delaunay like vorbereiten und dann easy weiter verfeinern.
(Siehe TDelaunayTriangulation.Triangulate in #18)