Algorithmen für die Polygon-Triangulation

9

Es fiel mir schwer, einen Algorithmus zu finden oder Artikel über die Triangulation von sich selbst schneidenden Polygonen (auch Polygone mit Lochstruktur) zu veröffentlichen.

Kann mich bitte jemand anleiten, veröffentlichte Artikel / Algorithmen zu finden?

PS: Jemand markiert diese Frage bitte angemessen. Ich habe nicht genügend Reputationspunkte, um dies zu tun.

ds.algorithms reference-request cg.comp-geom Prashant Cholachagudda
quelle
5
Vielleicht liegt Ihr Schwerpunkt auf dem sich selbst überschneidenden Aspekt Ihrer Polygone? Die meisten Algorithmen (wie sie Suresh vorschlägt) gehen von einem einfachen Polygon aus. Zuerst müssen Sie die Schnittpunkte an den Selbstkreuzungen berechnen, z. B. über einen Ebenen-Sweep. Dann können Sie den Seidel-Algorithmus anwenden.
Joseph O'Rourke

Antworten:

7

Haben Sie Seidels Algorithmus in Betracht gezogen ?

Suresh Venkat
quelle
Seidels Algorithmus ist zwar sehr schnell, muss jedoch modifiziert werden, um Selbstüberschneidungen zu handhaben. Es ist nicht unmöglich, aber nicht sofort offensichtlich.
Simon F
1

Ich denke, Sie können sich http://sigbjorn.vik.name/projects/Triangulation.pdf ansehen. Dies war das erste Google-Ergebnis für "sich selbst überschneidender Polygon-Triangulationsalgorithmus". Zuerst wird der Seidel-Algorithmus und seine Implementierung besprochen und dann verallgemeinert in "5.2 Schnittpunkte" geht es um sich selbst schneidende Polygone.

Saeed
quelle