Struktur data quad-edge (Delaunay / Voronoi)

2 pertanyaan untuk ahli ilmu ukur atau ahli aljabar:

Saya baru mulai terjun ke geometri komputasi dan saya menyukainya =)

Saya mencoba membaca artikel terkenal oleh Guibas dan Stolfi yang disebut "Primitif untuk manipulasi subdivisi umum dan perhitungan Diagram Voronoi" untuk menerapkan algoritma triangulasi Delaunay. Saya tergoda untuk melewatkan semua hal teoritis dan hanya membaca deskripsi struktur data quad-edge mereka untuk menghemat waktu. Namun, saya pikir mungkin layak untuk memahami semua matematika dalam artikel jika strukturnya banyak digunakan, atau hanya karena itu mungkin indah.

Matematika itu sedikit padat bagi saya. Saya tidak sepenuhnya bodoh tentang topologi, tetapi deskripsi aljabar tepi mereka membutuhkan pengetahuan tentang aljabar abstrak yang tidak saya miliki.

Dua pertanyaan saya adalah: Apa aplikasi lain dari struktur quad-edge yang ada selain menghitung Delaunay / Voronoi? Sepertinya alat yang sangat kuat.

Pertanyaan kedua; Apa itu aljabar abstrak? Alangkah baiknya jika Anda bisa memberi saya referensi untuk pengantar aljabar abstrak, cukup supaya saya bisa memahami bagian aljabar tepi mereka.

Terima kasih!

Saya pikir formalisme "ujung aljabar" Guibas dan Stolfi sedikit tidak perlu.

Yang perlu dilakukan hanyalah mengingat perbedaan antara grafik primal dan dua grafik. Setiap wajah dari grafik primal memiliki dual titik yang sesuai f * ; setiap tepi e dari grafik primal memiliki tepi ganda yang sesuai $f$$f^*$$e$ ; dan masing-masing vertex v grafik primal memiliki sesuai ganda wajah v * . Tepi primal menghubungkan simpul primal dan memisahkan permukaan primal; tepi ganda menghubungkan simpul ganda dan memisahkan wajah ganda. Ganda dari apa pun adalah hal yang asli. Lihat Gambar 4 dalam makalah Guibas dan Stolfi:$e^*$$v$$v^*$

Guibas dan Stolfi mengusulkan berpikir tentang setiap sisi (baik primal atau rangkap) sebagai kumpulan dari empat tepi yang diarahkan, berorientasi ; untuk kesederhanaan, saya akan memanggil anak panah ini . Setiap anak panah poin dari satu titik akhir ekor ( → e ) ke titik akhir lainnya kepala ( → e ) , dan lokal memisahkan dua wajah kiri ( → e ) dan kanan ( → e ) . Pilihan titik akhir untuk memanggil ekor ( → e ) adalah milik anak panah$\vec{e}$$\text{tail}(\vec{e})$$\text{head}(\vec{e})$$\text{left}(\vec{e})$$\text{right}(\vec{e})$$\text{tail}(\vec{e})$arah , dan pilihan wajah yang akan dipanggil ke adalah orientasinya . (Guibas dan Stolfi menggunakan "Org" dan "Dest" daripada "tail" dan "head", tetapi saya lebih suka label yang lebih pendek, karena Singkatan yang Tidak Perlu Adalah Jahat.)$\text{left}(\vec{e})$

Untuk anak panah , Guibas dan Stolfi mengasosiasikan tiga anak panah terkait:$\vec{e}$

1. : Panah yang meninggalkan ekor ( → e ) berikutnya dalam urutan berlawanan arah setelah → e .$\text{tailNext}(\vec{e})$$\text{tail}(\vec{e})$$\vec{e}$
2. $\text{flip}(\vec{e})$$\vec{e}$$\text{left}(\vec{e})$$\text{right}(\vec{e})$
3. $\text{rotate}(\vec{e})$$\vec{e}$

Tiga fungsi ini memenuhi semua jenis identitas yang indah, seperti yang berikut:

• $\text{right}(\text{tailNext}(\vec{e})) = \text{left}(\vec{e})$
• $\text{right}(\text{flip}(\vec{e})) = \text{left}(\vec{e})$
• $\text{right}(\text{rotate}(\vec{e})) = \text{head}(\vec{e})^*$
• $\text{flip}(\text{flip}(\vec{e})) = \vec{e}$
• $\text{rotate}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))) = \vec{e}$
• $\text{tailNext}(\text{rotate}(\text{tailNext}(\text{rotate}(\vec{e})))) = \vec{e}$

Untuk daftar lengkap, lihat halaman 83 dari makalah (tetapi waspadalah bahwa penulis menggunakan notasi postfix $e~Flip$e.Flip

Selain itu, mengingat ketiga fungsi ini, seseorang dapat mendefinisikan beberapa fungsi berguna lainnya seperti

• $\text{reverse}(\vec{e}) = \text{rotate}(\text{flip}(\text{rotate}(\vec{e})))$
• $\text{leftNext}(\vec{e}) = \text{rotate}(\text{tailNext}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))))$$\vec{e}$$\text{left}(\vec{e})$

Akhirnya, mengetahui fungsi-fungsi ini memberi tahu Anda segala sesuatu tentang topologi subdivisi, dan setiap subdivisi poligonal dari permukaan apa pun (yang dapat diorientasikan atau tidak) dapat dikodekan menggunakan tiga fungsi ini.

Struktur data quad-edge adalah representasi yang nyaman dari grafik permukaan yang menyediakan akses ke semua fungsi ini, bersama dengan beberapa operasi waktu konstan lainnya seperti memasukkan, menghapus, membuat kontrak, memperluas, dan membalikkan tepi; membelah atau menggabungkan simpul atau wajah; dan menambah atau menghapus handle atau cross-caps.

Selamat bersenang-senang!