Selama beberapa minggu terakhir, saya telah berupaya mengimplementasikan algoritma Fortune di C ++. Algoritma ini mengambil banyak poin 2D dan membangun diagram Voronoi darinya. Jika Anda tidak tahu apa itu diagram Voronoi, maka lihatlah gambar:


Untuk setiap titik masuk, yang disebut "situs," kita perlu menemukan banyak titik yang lebih dekat ke tempat ini daripada orang lain. Set titik-titik tersebut membentuk sel-sel yang ditunjukkan pada gambar di atas.

Sangat luar biasa dalam algoritme Fortune bahwa ia membuat diagram seperti itu pada waktunya $$$O (n \ log n)$ (yang optimal untuk algoritma perbandingan), di mana $$$n$ Apakah jumlah tempat.

Saya menulis artikel ini karena saya menganggap implementasi algoritma ini tugas yang sangat sulit. Saat ini, ini adalah algoritma paling rumit yang harus saya implementasikan. Karena itu, saya ingin berbagi masalah yang saya temui, dan bagaimana menyelesaikannya.

Seperti biasa, kode diposting di github , dan semua bahan referensi yang saya gunakan tercantum di akhir artikel.

Deskripsi algoritma keberuntungan

Saya tidak akan menjelaskan bagaimana algoritma bekerja, karena orang lain telah melakukannya dengan baik. Saya dapat merekomendasikan mempelajari dua artikel ini: di sini dan di sini . Yang kedua sangat menarik - penulis menulis demo interaktif dalam Javascript, yang berguna untuk memahami operasi algoritma. Jika Anda memerlukan pendekatan yang lebih formal dengan semua bukti, saya sarankan membaca Bab 7 dari Computational Geometry, edisi ke-3 .

Selain itu, saya lebih suka berurusan dengan detail implementasi yang tidak terdokumentasi dengan baik. Dan merekalah yang membuat implementasi algoritma begitu rumit. Secara khusus, saya akan fokus pada struktur data yang digunakan.

Saya baru saja menulis pseudo-code dari algoritma sehingga Anda mendapatkan gambaran tentang struktur globalnya:

  tambahkan acara tempat ke antrian acara untuk setiap tempat
 hingga antrian acara kosong
     ambil kembali acara teratas
     jika acara tersebut adalah acara tempat
         masukkan busur baru ke garis pantai
         periksa acara lingkaran baru
     jika tidak
         buat simpul dalam diagram
         kami menghapus dari garis pantai busur yang dikencangkan
         hapus acara yang tidak valid
         periksa acara lingkaran baru 

Bagan struktur data

Masalah pertama yang saya temui adalah memilih cara untuk menyimpan diagram Voronoi.

Saya memutuskan untuk menggunakan struktur data yang banyak digunakan dalam geometri komputasi yang disebut daftar tepi terhubung ganda (DCEL).

Kelas VoronoiDiagram saya menggunakan empat kontainer sebagai bidang:

 class VoronoiDiagram { public: // ... private: std::vector<Site> mSites; std::vector<Face> mFaces; std::list<Vertex> mVertices; std::list<HalfEdge> mHalfEdges; } 

Saya akan berbicara secara rinci tentang masing-masing dari mereka.

Kelas Site menjelaskan titik masuk. Setiap tempat memiliki indeks, yang berguna untuk meletakkannya dalam antrian, koordinat, dan penunjuk ke sel ( face ):

 struct Site { std::size_t index; Vector2 point; Face* face; }; 

Verteks sel diwakili oleh kelas Vertex , mereka hanya memiliki bidang koordinat:

 struct Vertex { Vector2 point; }; 

Berikut ini adalah implementasi dari setengah sisi:

 struct HalfEdge { Vertex* origin; Vertex* destination; HalfEdge* twin; Face* incidentFace; HalfEdge* prev; HalfEdge* next; }; 

Anda mungkin bertanya-tanya, apa itu iga? Tepi dalam diagram Voronoi adalah umum untuk dua sel tetangga. Dalam struktur data DCEL, kami membagi tepi ini menjadi dua sisi setengah, satu untuk setiap sel, dan mereka dihubungkan oleh pointer twin . Selain itu, setengah-tepi memiliki titik awal dan akhir. Bidang incidentFace menunjukkan wajah yang dimiliki setengah-tepi. Sel-sel dalam DCEL diimplementasikan sebagai daftar setengah sisi siklik ganda, di mana setengah sisi yang berdekatan dihubungkan bersama. Oleh karena itu, bidang prev dan next menunjukkan setengah-tepi sebelumnya dan berikutnya dalam sel.

Gambar di bawah ini menunjukkan semua bidang ini untuk setengah sisi merah:


Akhirnya, kelas Face mendefinisikan sel. Ini hanya berisi pointer ke tempatnya dan yang lain ke salah satu tulang rusuknya. Tidak masalah bagian tepi mana yang dipilih, karena sel adalah poligon tertutup. Dengan demikian, kami mendapatkan akses ke semua sisi-setengah saat melintasi daftar terkait siklik.

 struct Face { Site* site; HalfEdge* outerComponent; }; 

Antrian acara

Cara standar untuk mengimplementasikan antrian acara adalah dengan antrian prioritas. Dalam proses memproses acara tempat dan lingkaran, kami mungkin perlu menghapus acara lingkaran dari antrian karena tidak lagi valid. Tetapi sebagian besar implementasi antrian prioritas standar tidak memungkinkan Anda untuk menghapus item yang tidak di atas. Ini berlaku khususnya untuk std::priority_queue .

Ada dua cara untuk mengatasi masalah ini. Yang pertama, lebih sederhana adalah menambahkan bendera yang valid ke acara. valid awalnya disetel ke true . Kemudian, alih-alih menghapus acara lingkaran dari antrian, kita dapat dengan mudah mengatur benderanya menjadi false . Akhirnya, saat memproses semua peristiwa dalam loop utama, kami memeriksa untuk melihat apakah nilai flag yang valid dari acara tersebut false , dan jika demikian, maka lewati saja dan proses yang berikutnya.

Metode kedua yang saya terapkan adalah tidak menggunakan std::priority_queue . Sebaliknya, saya menerapkan antrian prioritas saya sendiri, yang mendukung penghapusan elemen apa pun yang terkandung di dalamnya. Implementasi antrian semacam itu cukup sederhana. Saya memilih metode ini karena membuat kode algoritma lebih bersih.

Garis pantai

Struktur data garis pantai adalah bagian kompleks dari algoritma. Dalam hal implementasi yang salah, tidak ada jaminan bahwa algoritma akan dieksekusi di $$$O (n \ log n)$ . Kunci untuk mendapatkan kompleksitas waktu ini adalah menggunakan pohon penyeimbang sendiri. Tapi itu lebih mudah diucapkan daripada dilakukan!

Sebagian besar sumber daya yang telah saya pelajari (dua artikel yang disebutkan di atas dan buku Geometri Komputasi ) disarankan untuk menerapkan garis pantai sebagai pohon di mana node internal menunjukkan titik istirahat dan daun menunjukkan busur. Tetapi mereka tidak mengatakan apa-apa tentang bagaimana menyeimbangkan pohon. Saya pikir model seperti itu bukan yang terbaik, dan inilah alasannya:

• ada informasi yang berlebihan di dalamnya: kita tahu bahwa ada titik istirahat antara dua busur yang berdekatan, sehingga tidak perlu untuk mewakili titik-titik ini sebagai simpul
• itu tidak memadai untuk menyeimbangkan diri sendiri: hanya subtree yang dibentuk oleh break point yang bisa diseimbangkan. Kami benar-benar tidak dapat menyeimbangkan seluruh pohon, karena jika tidak, busur dapat menjadi simpul internal dan daun break point. Menulis algoritma untuk menyeimbangkan hanya subtree yang dibentuk oleh node internal seperti mimpi buruk bagi saya.

Karena itu, saya memutuskan untuk menyajikan garis pantai secara berbeda. Dalam implementasi saya, garis pantai juga merupakan pohon, tetapi semua node adalah busur. Model seperti itu tidak memiliki kelemahan apa pun yang terdaftar.

Berikut adalah definisi Arc arc dalam implementasi saya:

 struct Arc { enum class Color{RED, BLACK}; // Hierarchy Arc* parent; Arc* left; Arc* right; // Diagram VoronoiDiagram::Site* site; VoronoiDiagram::HalfEdge* leftHalfEdge; VoronoiDiagram::HalfEdge* rightHalfEdge; Event* event; // Optimizations Arc* prev; Arc* next; // Only for balancing Color color; }; 

Tiga bidang pertama digunakan untuk struktur pohon. Bidang leftHalfEdge menunjukkan setengah sisi yang ditarik oleh titik paling kiri dari busur. Dan rightHalfEdge berada di setengah sisi yang ditarik oleh titik kanan ekstrem. Dua pointer, prev dan next digunakan untuk mendapatkan akses langsung ke busur garis pantai sebelumnya dan berikutnya. Selain itu, mereka juga memungkinkan Anda untuk memotong garis pantai sebagai daftar tertaut ganda. Akhirnya, setiap busur memiliki warna yang digunakan untuk menyeimbangkan garis pantai.

Untuk menyeimbangkan garis pantai, saya memutuskan untuk menggunakan skema merah-hitam . Saat menulis kode, saya terinspirasi oleh buku Introduction to Algorithms . Bab 13 menjelaskan dua algoritma yang menarik, insertFixup dan deleteFixup , yang menyeimbangkan pohon setelah penyisipan atau penghapusan.

Namun, saya tidak bisa menggunakan metode insert yang diperlihatkan dalam buku ini, karena tombolnya digunakan untuk menemukan titik penyisipan simpul. Tidak ada kunci dalam algoritme Fortune, kita hanya tahu bahwa kita perlu memasukkan busur sebelum atau sesudah yang lain di garis pantai. Untuk mengimplementasikan ini, saya membuat metode insertBefore dan insertAfter :

 void Beachline::insertBefore(Arc* x, Arc* y) { // Find the right place if (isNil(x->left)) { x->left = y; y->parent = x; } else { x->prev->right = y; y->parent = x->prev; } // Set the pointers y->prev = x->prev; if (!isNil(y->prev)) y->prev->next = y; y->next = x; x->prev = y; // Balance the tree insertFixup(y); } 

Memasukkan y sebelum x dilakukan dalam tiga langkah:

1. Temukan tempat untuk menyisipkan simpul baru. Untuk melakukan ini, saya menggunakan pengamatan berikut: anak kiri x atau anak kanan x->prev adalah Nil , dan yang adalah Nil adalah sebelum x dan setelah x->prev .
2. Di dalam garis pantai, kita menjaga struktur daftar yang ditautkan ganda, jadi kita harus memperbarui petunjuk prev dan next dari elemen x->prev , y dan x .
3. Akhirnya, kita cukup memanggil metode insertFixup yang dijelaskan dalam buku untuk menyeimbangkan pohon.

insertAfter diimplementasikan dengan cara yang sama.

Metode penghapusan yang diambil dari buku dapat diterapkan tanpa perubahan.

Batas grafik

Berikut ini adalah output dari algoritma Fortune yang dijelaskan di atas:


Ada masalah kecil dengan beberapa tepi sel di perbatasan gambar: mereka tidak ditarik karena tidak terbatas.

Lebih buruk lagi, sel mungkin bukan fragmen tunggal. Sebagai contoh, jika kita mengambil tiga titik yang berada di garis yang sama, maka titik tengahnya akan memiliki dua sisi setengah tak terbatas yang tidak terhubung bersama. Ini tidak sesuai dengan kita, karena kita tidak akan dapat mengakses salah satu dari setengah tepi, karena sel adalah daftar tepi yang terhubung.

Untuk mengatasi masalah ini, kami akan membatasi diagram. Maksud saya, kita akan membatasi setiap sel diagram sehingga tidak lagi memiliki tepi yang tidak terbatas dan setiap sel adalah poligon tertutup.

Untungnya, algoritme Fortune memungkinkan kita menemukan tepi tanpa ujung dengan cepat: mereka bersesuaian dengan setengah sisi yang masih di garis pantai di akhir algoritme.

Algoritme pembatasan saya menerima kotak sebagai input dan terdiri dari tiga langkah:

1. Ini menyediakan penempatan setiap simpul diagram di dalam persegi panjang.
2. Potong setiap tepi yang tak terbatas.
3. Menutup sel.

Tahap 1 sepele - kita hanya perlu memperluas persegi panjang jika tidak mengandung simpul.

Tahap 2 juga cukup sederhana - ini terdiri dari menghitung persimpangan antara sinar dan persegi panjang.

Tahap 3 juga tidak terlalu rumit, hanya membutuhkan perhatian. Saya melakukannya dalam dua tahap. Pertama, saya menambahkan titik sudut persegi panjang ke sel-sel di simpul yang seharusnya. Lalu saya memastikan bahwa semua simpul sel terhubung oleh setengah-tepi.

Saya sarankan Anda mempelajari kode dan mengajukan pertanyaan jika Anda memerlukan detail tentang bagian ini.

Berikut adalah diagram output dari algoritma pembatas:


Sekarang kita melihat bahwa semua tepian digambar. Dan jika Anda memperkecil, Anda dapat memastikan bahwa semua sel ditutup:

Persimpangan dengan persegi panjang

Hebat! Tetapi gambar pertama dari awal artikel lebih baik, bukan?

Dalam banyak aplikasi, penting untuk memiliki persimpangan antara diagram Voronoi dan persegi panjang, seperti yang ditunjukkan pada gambar pertama.

Hal yang baik adalah bahwa setelah membatasi grafik, itu jauh lebih mudah dilakukan. Berita buruknya adalah meskipun algoritmanya tidak terlalu rumit, kita harus berhati-hati.

Idenya adalah ini: kita memutar setengah sisi setiap sel dan memeriksa persimpangan antara setengah sisi dan persegi panjang. Ada lima kasus yang mungkin:

1. Setengah rusuk benar-benar di dalam persegi panjang: kita menyimpan setengah rusuk seperti itu
2. Setengah rusuk benar-benar di luar persegi panjang: kita membuang setengah rusuk seperti itu
3. Setengah tulang rusuk keluar dari persegi panjang: kita memotong setengah tulang rusuk dan menyimpannya sebagai setengah tulang rusuk terakhir yang keluar .
4. Setengah rusuk masuk ke dalam persegi panjang: kita memotong setengah rusuk untuk menghubungkannya dengan setengah rusuk terakhir yang keluar (kita simpan dalam kasus 3 atau 5)
5. Setengah rusuk melintasi kotak dua kali: kita memotong setengah rusuk dan menambahkan setengah rusuk untuk mengaitkannya dengan setengah rusuk terakhir yang keluar , dan kemudian menyimpannya sebagai setengah rusuk terakhir baru yang keluar .

Ya, sudah banyak kasus. Saya membuat gambar untuk menunjukkan semuanya:


Poligon oranye adalah sel asli, dan merah adalah sel terpotong. Setengah rusuk yang terpotong ditandai dengan warna merah. Iga hijau telah ditambahkan untuk menghubungkan setengah iga memasuki persegi panjang dengan setengah iga keluar.

Menerapkan algoritma ini ke diagram terikat, kami mendapatkan hasil yang diharapkan:

Kesimpulan

Artikel itu ternyata cukup panjang. Dan saya yakin banyak aspek yang masih belum jelas bagi Anda. Meskipun demikian, saya berharap ini akan bermanfaat bagi Anda. Periksa kode untuk detailnya.

Untuk meringkas dan memastikan bahwa kami tidak membuang waktu dengan sia-sia, saya mengukur pada laptop saya (murah) waktu untuk menghitung diagram Voronoi untuk sejumlah tempat yang berbeda:

• $$$n = 1000$ : 2 ms
• $$$n = $ 10.00$ : 33 ms
• $$$n = $ 100.00$ : 450 ms
• $$$n = $ 1.000.00$ : 6600 ms

Saya tidak memiliki apa pun untuk membandingkan indikator-indikator ini, tetapi tampaknya ini sangat cepat!

Referensi

• Artikel asli oleh Stephen Fortune
• Geometri Komputasi, edisi ke-3 oleh Mark de Berg, Otfried Cheong, Marc van Kreveld dan Mark Overmars
• Algoritma Fortunes: Penjelasan intuitif di jacquesheunis.com
• Algoritma dan implementasi Fortune di blog.ivank.net
• Pengantar Algoritma, edisi ke-3 oleh Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest dan Clifford Stein