Apa manfaat menggunakan Half Edge dibandingkan Winged Edge?

Untuk representasi jala, apa manfaat menggunakan struktur data Half Edge over Winged Edge?

Saya mengerti kedua representasi jala, satu-satunya perbedaan adalah bahwa setengah tepi menggunakan tepi terarah dan tepi bersayap menggunakan tepi tidak langsung. Sejauh ini, saya tidak bisa memikirkan apa kegunaan menggunakan directional edge, namun hanya memberikan konsumsi memori lebih banyak.

Sejauh yang saya tahu, keunggulan utama half-edge adalah bahwa traversal bisa sedikit lebih sederhana karena jaminan tepi memiliki orientasi yang konsisten di setiap wajah.

Pertimbangkan masalah iterasi pada semua simpul atau tepi wajah tertentu, dalam urutan berlawanan arah jarum jam. Dalam struktur setengah sisi, ini dapat dilakukan dengan mulai dengan setengah sisi sewenang-wenang dari wajah itu dan cukup mengikuti petunjuk "berikutnya" sampai Anda kembali ke tempat Anda mulai.

Sebaliknya, melakukan ini dalam struktur ujung bersayap agak menjengkelkan, karena ujungnya berorientasi secara sewenang-wenang; setiap tepi tertentu yang Anda temui mungkin mengarah searah jarum jam atau berlawanan arah jarum jam ke wajah yang Anda coba putar di sekitar, jadi Anda harus melakukan pemeriksaan bersyarat tambahan pada setiap langkah untuk melihat apakah Anda harus melintasi tepi saat ini maju atau mundur.

Jenis lain dari permintaan konektivitas berperilaku serupa: versi setengah-tepi memungkinkan Anda mengikuti tautan dalam urutan yang konsisten sementara versi sisi-sayap memerlukan pemeriksaan orientasi di setiap langkah.

Apakah persyaratan sebenarnya masalah kinerja untuk winged-edge mungkin akan tergantung pada faktor-faktor lain. Untuk implementasi "naif" dengan pointer segala cara dan data yang tersebar di seluruh memori, saya berharap cache miss overhead untuk membanjiri segala efek kondisional. Di sisi lain, jika Anda memiliki struktur data yang padat dengan segala sesuatu yang panas di cache, Anda mungkin melihat beberapa efek dari kondisi karena prediksi cabang yang salah, dll. Sulit dikatakan.

Membiarkan kinerja saja, saya lebih suka setengah-tepi hanya karena tampaknya lebih mudah untuk berpikir tentang dan menulis kode yang benar, bahkan jika itu menghasilkan sedikit overhead memori.

Ngomong-ngomong, ada beberapa pilihan desain lain dengan struktur data mesh yang sering tampak bingung dengan yang satu ini. Seorang komentator menyebutkan tautan tunggal vs ganda, tetapi secara alami Anda dapat melakukan tautan tunggal atau ganda dengan setengah-tepi atau ujung-sayap. (Meskipun saya tidak melihat bagaimana penautan tunggal dengan ujung bersayap akan bekerja, karena seperti yang disebutkan di atas, Anda mungkin harus melintasi tepi baik ke belakang atau ke depan dalam proses kueri.)

Juga, ada pertanyaan apakah vertex dan struktur muka menyimpan daftar semua tepinya, atau hanya satu (dan mengharuskan Anda untuk melintasi tepi untuk menemukan sisanya). Memiliki daftar panjang sisi variabel per simpul / muka yang sangat menyulitkan logika jika Anda ingin melakukannya secara efisien (yaitu tidak memiliki alokasi tumpukan terpisah per simpul / wajah), tetapi sekali lagi ini tidak tergantung apakah tepi setengah-tepi atau ujung bersayap.