Algoritma untuk triangulasi Polygon

9

Saya kesulitan menemukan algoritme atau menerbitkan makalah tentang triangulasi poligon bersilangan (juga poligon dengan struktur lubang).

Bisakah ada yang memandu saya untuk menemukan makalah / algoritma yang dipublikasikan?

PS: tolong beri tag pada seseorang pertanyaan ini dengan tepat, saya tidak punya poin reputasi yang cukup untuk melakukannya.

ds.algorithms reference-request cg.comp-geom Prashant Cholachagudda
sumber
5
Mungkin penekanan Anda adalah pada aspek berpotongan diri dari poligon Anda? Sebagian besar algoritma (seperti yang disarankan Suresh) mengasumsikan poligon sederhana. Pertama, Anda harus menghitung titik persimpangan di persimpangan diri, melalui, misalnya, sapuan bidang. Kemudian Anda dapat menerapkan algoritma Seidel.
Joseph O'Rourke

Jawaban:

7

Sudahkah Anda mempertimbangkan algoritma Seidel ?

Suresh Venkat
sumber
Algoritma Seidel, meskipun sangat cepat, perlu modifikasi untuk menangani persimpangan-diri. Bukan tidak mungkin, tetapi tidak segera jelas.
Simon F
1

Saya pikir Anda dapat melihat http://sigbjorn.vik.name/projects/Triangulation.pdf yang merupakan hasil google pertama untuk "algoritma perpotongan triangulasi Polygon" pertama-tama akan membahas tentang algoritma Seidel dan implementasinya dan kemudian akan menggeneralisasikannya dalam pembicaraan "5.2 Intersections" tentang poligon berpotongan sendiri.

Saeed
sumber