Membuat Diagram Voronoi dengan Memanfaatkan Algoritma Fortune

Membuat Diagram Voronoi

• Apa itu diagram Voronoi?

  • Diagram Voronoi adalah metode untuk membagi bidang menjadi beberapa wilayah, dan terutama digunakan untuk menghasilkan peta secara prosedural.
  • Beberapa titik yang disebut 'site' dipilih pada bidang, dan wilayah yang berkorespondensi dengan setiap site adalah wilayah yang mencakup semua titik yang paling dekat dengan site tersebut.
  • Batas setiap wilayah terdiri dari titik-titik yang berjarak sama dari dua site. Titik yang berjarak sama dari tiga site disebut 'verteks Voronoi'.

• Algoritma Fortune

  • Algoritma Fortune adalah metode untuk membuat diagram menggunakan garis yang 'menyapu' bidang dari kiri ke kanan.
  • Saat sweep line bertemu site, 'bubble' (busur parabola) terbentuk di sekitarnya, dan bubble membesar ketika sweep line menjauh.
  • Ketika busur dari dua site bertabrakan, titik tumbukan itu menjadi batas sel.
  • Batas dari semua bubble yang aktif disebut 'beachline'.

• Penjelasan istilah

  • Site: titik 2 dimensi yang menentukan bentuk diagram Voronoi.
  • Sweep line: garis vertikal yang melintasi wilayah dan memproses setiap event dalam event queue.
  • Beachline: garis yang terdiri dari beberapa busur, di mana busur ditambahkan atau dihapus saat event diproses.
  • Titik perpotongan: titik tempat dua busur pada beachline bertemu, dan berjarak sama dari site yang terkait.
  • Event queue: tempat site dan circle event disimpan, diurutkan berdasarkan koordinat x secara menaik.
  • Site event: salah satu dari dua jenis event dalam event queue, yang didefinisikan oleh koordinat site terkait.
  • Circle event: jenis event lain dalam queue, yang didefinisikan oleh tiga busur pada keliling lingkaran.
  • Verteks Voronoi: titik yang berjarak sama dari tiga site, yaitu sudut sel.
  • Batas ekuidistan: garis yang berjarak sama dari dua site.
  • Batas tidak lengkap: garis yang salah satu ujungnya adalah titik tetap, dan ujung lainnya didefinisikan oleh titik perpotongan dua fokus parabola.

• Garis singgung parabola

  • Konsep dan sifat parabola sangat penting dalam algoritma ini.
  • Parabola didefinisikan oleh titik fokus dan garis lurus (direktriks).
  • Dengan menetapkan fokus dari dua site dan menetapkan sweep line sebagai direktriks, kita dapat menemukan garis batas yang berjarak sama dari dua site dengan mencari titik perpotongan dua parabola.

• Kembali ke beachline

  • Beachline adalah 'batas' dari semua busur pada titik tertentu dari sweep line.
  • Setiap busur dapat direpresentasikan sebagai titik fokus site.
  • Beachline dapat direpresentasikan sebagai urutan titik yang sederhana.

• Busur baru dibuat saat sweep line bertemu site baru

  • Beachline adalah urutan titik, dan setiap titik merepresentasikan site dan busur.
  • Saat sweep line bertemu site baru, busur baru dibuat dan disisipkan ke dalam urutan.

• Batas yang berpotongan dan lingkaran luar

  • Ketika tiga site berada pada keliling lingkaran, pusat lingkaran berjarak sama dari ketiga titik.
  • Pusat lingkaran luar menjadi verteks Voronoi.

• Batas tidak lengkap

  • Batas tidak lengkap memiliki satu ujung berupa titik tetap, dan ujung lainnya adalah titik perpotongan dua busur.
  • Ketika dua batas tidak lengkap bertabrakan, verteks Voronoi terbentuk, dan batas tidak lengkap diubah menjadi half-edge.

• Hanya lingkaran berlawanan arah jarum jam yang menghasilkan circle event

  • Circle event hanya dihasilkan ketika tiga busur dibaca berlawanan arah jarum jam.

• Ringkasan

  • Jika diberikan himpunan site, masukkan semua titik site ke dalam queue sebagai event 'site' dan urutkan berdasarkan nilai x.
  • Selama queue tidak kosong, ambil event berikutnya dari queue dan proses.
  • Jika itu site event, tambahkan busur baru ke beachline dan buat batas tidak lengkap.
  • Jika itu circle event, tambahkan verteks Voronoi dan hapus busur dari beachline.