Struktur data untuk kompleks sel umum (non-tetrahedral)

Untuk jerat poligonal 2D, representasi struktur data QuadEdge dan HalfEdge cukup untuk menyimpan dan memungkinkan kueri yang efisien dari semua informasi topologi dan insiden. Apakah ada struktur data yang kompak dan efisien untuk jerat polihedral 3D? Saya tahu ada beberapa karya terbaru tentang representasi kompak untuk jerat tetrahedral, seperti, misalnya SOT . Saya tidak cukup tahu tentang ini untuk mengetahui apakah mereka menggeneralisasi ke jerat non-tetrahedral yang tidak terstruktur.

Saya bisa membayangkan bahwa setengah sisi mungkin menggeneralisasi ke setengah wajah dengan setengah sisi terkait, tetapi sepertinya itu adalah banyak data untuk disimpan, dan mungkin ada representasi yang lebih kompak. Saya harus menambahkan bahwa saya benar-benar hanya peduli tentang mengambil informasi facet (seperti facet mana yang berada di perbatasan, yang facet milik sel tertentu); informasi insiden tepi tidak berguna.

data-structures computational-geometry Victor Liu
sumber

Jawaban:

Ada ekstensi setengah-tepi dalam dimensi apa pun, yang disebut panah di peta kombinatorial . Ada dua paket di CGAL yang memungkinkan untuk menggunakan peta kombinatorial ini dalam dimensi apa pun (lihat di sini untuk peta kombinatorial dan di sini untuk LinearCellComplex ).

Anda dapat menggunakan struktur data ini untuk mewakili objek 3D terbagi berorientasi berjenis Quasi manifold . Mengutip dari laman web CGAL (bagian 2.4 Properti Peta Kombinasi):

Objek quasi-manifold didefinisikan sebagai:

Manifold kuadrat dD adalah objek yang diperoleh dengan mengambil beberapa sel-d yang terisolasi, dan memungkinkan untuk merekatkan sel-sel d sepanjang (d-1) sel.

dan berorientasi sebagai:

Dapat diorientasikan jika memungkinkan untuk menanamkannya di ruang Euclidean dan untuk menentukan arah global "kiri" dan "kanan" di setiap titik objek yang disematkan.

gdamiand
sumber

Bagaimana hal ini dibandingkan dengan representasi FacetEdge dari Dobkin & Laszlo? Sepertinya itu satu-satunya hal lain yang bisa kutemukan.

Victor Liu

Mereka setara. Dalam representasi FacetEdge, ada terutama 3 fungsi: jam , Enext dan Fnext ; dan dalam peta kombinatorial 3D, ada 3 fungsi , dan .

β_{1}

$\beta_1$

β_{2}

$\beta_2$

β_{3}

$\beta_3$

gdamiand

Perhatikan bahwa situs ini adalah tentang ilmu komputer , bukan implementasi perpustakaan. Karena itu, kami menghargai jawaban yang mengandung ide dan konsep, bukan hanya referensi untuk implementasi.

Raphael