Membuat Diagram Voronoi dengan Algoritme Fortune

• Fortune’s Algorithm dapat membuat diagram Voronoi dalam waktu O(n log n), tetapi implementasinya sulit; kecuali jika perlu membuat diagram berskala besar berulang kali, implementasi O(n²) atau pustaka akan lebih realistis
• Diagram Voronoi membagi bidang menjadi wilayah terdekat berdasarkan beberapa site, dan batasnya dibentuk oleh titik-titik yang berjarak sama dari dua site
• Algoritme ini mempertahankan sweep line yang bergerak dari kiri ke kanan dan beachline, yaitu garis depan dari busur-busur parabola, serta hanya memproses site event dan circle event
• site event menyisipkan busur baru, membelah busur yang sudah ada, dan membuat incomplete edge; circle event menghapus busur tengah sambil menyelesaikan Voronoi Vertex dan half edge
• Dalam implementasi praktis, event queue, beachline, peta incomplete edge, dan DCEL harus ditangani bersama; penghapusan circle event yang tidak valid dan perapian edge yang tersisa sangat meningkatkan kompleksitas

---

Tingkat kesulitan implementasi dan cakupan penerapan

• Fortune’s Algorithm adalah algoritme yang menghasilkan diagram Voronoi dalam waktu O(n log n)
• Untuk penggunaan nyata, sebaiknya pertimbangkan dulu skala yang dibutuhkan daripada langsung mengimplementasikannya
  • Jika tidak perlu membuat beberapa diagram besar per detik, implementasi O(n²) bisa menjadi pilihan yang lebih mudah
  • Alternatif yang lebih realistis adalah menggunakan pustaka yang sudah ada
• Hasil kerja algoritme ini menarik secara visual, tetapi proses implementasinya cenderung sulit dan cukup membuat frustrasi

Konsep dasar diagram Voronoi

• Diagram Voronoi adalah cara membagi bidang menjadi beberapa wilayah, dan sering digunakan dalam pembuatan peta prosedural
• Titik-titik yang dipilih sebagai input disebut site atau seed
• cell yang bersesuaian dengan tiap site adalah himpunan titik pada bidang yang paling dekat dengan site tersebut
• Batas cell terdiri dari titik-titik yang berjarak sama dari dua site
• Voronoi Vertex, tempat sisi-sisi cell bertemu, adalah titik yang berjarak sama dari tiga site

sweep line, beachline, event

• Fortune’s Algorithm menggunakan sweep line, yaitu garis vertikal yang bergerak dari kiri ke kanan
• Saat sweep line bertemu sebuah site, terbentuk busur parabola yang menjadikan site tersebut sebagai fokus; semakin jauh sweep line bergerak, semakin besar busurnya
• Titik pertemuan dua busur dari site yang berbeda berjarak sama dari kedua site, sehingga menjadi batas cell
• Saat dua batas bertemu, terbentuk simpul pada diagram
• Garis depan dari busur-busur yang aktif disebut beachline
• Implementasi sebenarnya tidak menggerakkan sweep line per piksel, melainkan hanya memproses event, yaitu titik-titik tertentu yang dapat dihitung
  • site event: didefinisikan oleh koordinat site yang sudah diketahui sebelumnya; saat diproses, busur baru ditambahkan ke beachline
  • circle event: didefinisikan oleh tiga busur pada beachline; saat diproses, satu busur dihapus dan Voronoi Vertex serta half edge dibuat

Menemukan batas dengan parabola

• Dalam algoritme ini, parabola ditangani dengan locus definition, bukan bentuk umum y = ax^2 + bx + c
• Parabola didefinisikan oleh satu focus point dan satu directrix
  • focus point menjadi site
  • directrix menjadi sweep line
• Titik potong dua parabola yang menggunakan sweep line yang sama sebagai directrix berjarak sama dari kedua site
• Karena itu, dengan mencari titik potong dua parabola, kita dapat menemukan equiedge di antara dua site
• Digunakan pseudocode untuk menghitung koordinat x parabola, serta contoh bagaimana titik potong dua parabola bergerak mengikuti batas saat posisi sweep line berubah

Representasi beachline dan pemrosesan site event

• Tiap busur pada beachline dapat direpresentasikan hanya dengan koordinat site terkait
  • sweep line berlaku sama untuk semua busur
  • Dalam implementasi, busur diperlakukan sebagai koordinat 2D, bukan objek terpisah
• beachline dapat direpresentasikan sebagai urutan titik sederhana
  • Contoh: [arc1, arc2], [arc1, arc2, arc3]
  • Busur dari site yang sama dapat muncul beberapa kali pada beachline
  • Contoh: [arc1, arc3, arc1, arc2]
• Saat site event terjadi, cari busur pada beachline yang ditemui jika menarik garis ke kiri dari site baru, lalu busur baru membelah busur tersebut
• Jika site baru L membelah j pada beachline yang sudah ada [.., i, j, k, ..], strukturnya menjadi [.., i, j, L, j, k, ..]
• Site dimasukkan ke queue berdasarkan urutan koordinat x, dan setiap kali diproses, beachline serta kandidat event diperbarui

circle event dan circumcircle

• Pada tiga busur [.., i, j, k, ..] di beachline, jika terjadi situasi dua batas bertemu, busur tengah j menghilang
• Pada saat itu ada circumcircle yang melalui ketiga site, dan pusat lingkarannya berjarak sama dari ketiga site
• Pusat circumcircle menjadi Voronoi Vertex
• circle event ditempatkan dalam event queue berdasarkan circle point, yaitu titik paling kanan lingkaran
• Jika sebuah site baru ditemukan di dalam lingkaran sebelum sweep line mencapai circle point, circle event yang ada menjadi tidak valid
  • Ini karena site baru lebih dulu membelah busur tengah, sehingga kombinasi tiga busur tersebut tidak lagi dipertahankan
  • triple lama i, j, k menghilang, dan triple baru seperti i, j, L, L, j, k harus diperiksa

incomplete edge dan half edge

• incomplete edge adalah garis yang salah satu ujungnya sudah tetap, tetapi ujung lainnya didefinisikan sebagai titik potong dua busur parabola
• Saat busur baru disisipkan oleh site event, dua incomplete edge dibuat
  • Titik tetapnya adalah koordinat tempat busur baru bertemu beachline yang sudah ada
  • Jika busur baru j membelah busur lama i, edge yang bersesuaian dengan titik potong [i, j] dan [j, i] akan dibuat
• Saat dua incomplete edge bertabrakan pada circle event, titik tabrakan itu menjadi Voronoi Vertex
• incomplete edge yang sudah ada diselesaikan menjadi half edge di titik ini, dan incomplete edge baru dibuat di antara dua busur yang baru menjadi bersebelahan

Hanya lingkaran berarah berlawanan jarum jam yang menjadi circle event

• Saat beachline memiliki [i, j, k, j, i], ijk dan kji sama-sama dapat membentuk lingkaran, tetapi tidak keduanya merupakan circle event yang valid
• Kasus busur tengah menghilang hanya terjadi pada sisi tempat batas benar-benar berkumpul
• Dalam program, orientation dari tiga titik ditentukan dengan determinant
  • Jika determinant negatif, arahnya berlawanan jarum jam dan menjadi circle event
  • Jika determinant positif, arahnya searah jarum jam dan bukan circle event
  • Jika determinant 0, ketiga titik segaris sehingga tidak ada lingkaran

Alur keseluruhan algoritme

• Urutkan site input berdasarkan koordinat x dan masukkan ke queue sebagai site event
• Sampai queue kosong, ambil dan proses event berikutnya
• Pemrosesan site event:
  • Hapus circle event yang tersisa di masa depan jika site baru masuk ke dalam lingkarannya
  • Cari busur pada beachline yang akan dibelah oleh site baru
  • Sisipkan busur baru untuk membelah busur yang sudah ada
  • Tambahkan dua incomplete edge
  • Periksa apakah triple baru yang terbentuk dapat membuat circle event
• Pemrosesan circle event:
  • Tambahkan pusat circumcircle sebagai Voronoi Vertex
  • Hapus busur tengah dari beachline
  • Hapus circle event mendatang yang menjadi tidak valid akibat busur yang dihapus
  • Periksa triple dari busur-busur yang baru bersebelahan dan tambahkan circle event
• Jika queue kosong, perpanjang incomplete edge yang tersisa sampai batas diagram, dan buat Voronoi Vertex pada titik pertemuannya dengan batas

Struktur data dalam implementasi Odin

• Contoh implementasi ditulis dalam Odin, bahasa alternatif untuk C
• Kode lengkap ada di repositori RedPenguin101/voronoi
• Tipe dasar:
  • V2: titik 2D berbentuk [2]int
  • PointPair: pasangan dua V2
  • Event: struct {site: bool, a, b, c: V2}
• Makna Event bergantung pada tipenya
  • Pada site event, a adalah koordinat site, sedangkan b dan c tidak digunakan
  • Pada circle event, a, b, c adalah tiga busur pada beachline yang membentuk event tersebut
• Struct Fortune mengelola state berikut
  • beachline: array V2
  • queue: array Event
  • incomplete_edges: map PointPair -> V2
  • vd: DCEL yang menyimpan Voronoi Diagram

Bagian yang dihilangkan atau disederhanakan dalam implementasi

• beachline direpresentasikan sebagai vector, tetapi untuk meningkatkan efisiensi, binary tree lebih cocok
• event queue secara konseptual adalah priority queue, tetapi contoh implementasi menanganinya dengan penyisipan terurut ke dalam array
• Invalidasi circle event dilakukan dengan menelusuri dan memeriksa event mendatang, dan ada TODO bahwa metode yang lebih cepat diperlukan
• clean_beachline_edges adalah prosedur untuk memotong busur yang tidak diperlukan di kedua ujung beachline
• Implementasi mencakup penanganan kasus khusus seperti site dengan koordinat x yang sama, circle point yang sama dengan site, dan tabrakan titik referensi
• Tahap akhir untuk merapikan incomplete edge yang tersisa setelah queue kosong, half edge tanpa twin, dan vertex hanya ditangani sebagai perhitungan matematika sederhana

Menyimpan diagram Voronoi dengan DCEL

• Diagram Voronoi biasanya disimpan sebagai Doubly Connected Edge List(DCEL)
• DCEL adalah struktur data yang merepresentasikan cell-complex berisi vertex dan edge agar mudah dimanipulasi
• Representasinya berpusat pada edge, tetapi informasi vertex dan face juga disimpan bersama
• Edge biasa tidak memiliki arah, tetapi dalam DCEL, setiap edge disimpan sebagai dua half edge dengan arah berlawanan
• Dalam diagram Voronoi, vertex yang disimpan di DCEL bukan site, melainkan Voronoi Vertex
• Tujuan edge E diperoleh dari E.twin.origin, dan face di sebelah kanan diperoleh dari E.twin.left

[GN⁺]

Pendapat Hacker News

• Dulu saya pernah membuat implementasi dengan ClojureScript yang menampilkan jalannya algoritma Fortune dalam bentuk animasi: https://voronoi.ajwerner.net/#/app-diagrams
  Ini benar-benar algoritma yang indah
  Tetapi sejak proyek itu, saya jadi agak tidak suka dengan algoritma Fortune, karena stabilitas numerik floating-point-nya kurang baik
  Kalau titik-titiknya segaris atau hampir segaris menurut floating-point, hasilnya bisa rusak
  Kalau saya ingat dengan benar, untuk hal ini delaunator lebih baik: https://github.com/mapbox/delaunator

  • Animasinya termasuk yang terbaik yang pernah saya lihat
    Saya melihat ada tautan implementasi “old” di halaman referensi, jadi saya penasaran apakah ada kemungkinan versi animasi saat ini juga akan dirilis sebagai open source

• Beberapa tahun lalu saya membuat visualisasi 3D seperti ini: https://x.com/KangarooPhysics/status/1253336959755251716

• Ada implementasi JavaScript oleh Raymond Hill, yang terkenal lewat uBlock Origin: https://github.com/gorhill/Javascript-Voronoi
  Saya sempat mengutak-atiknya sedikit supaya bisa bergerak: https://animations.adgent.com/voronoi.html

  • Animasi ini mengingatkan saya pada gaya A Scanner Darkly (2006)
    Saya jadi penasaran apakah ini bisa dimasukkan ke algoritma yang menerima video sebagai input lalu menampilkannya dengan cara Voronoi
    Pada titik itu mungkin secara teknis bukan lagi diagram Voronoi, tetapi sepertinya akan terlihat cukup keren

• D3.js punya implementasi baru: https://github.com/d3/d3-delaunay
  Di bagian bawah halaman itu ada penjelasan tentang algoritma sweep yang digunakan dan daftar implementasi dalam bahasa lain selain JavaScript
  d3-voronoi lama akan dihentikan, tetapi masih bisa dilihat di sini: https://github.com/d3/d3-voronoi

• Kalau Anda tidak peduli pada sisi-sisinya dan hanya perlu mewarnai setiap wilayah titik dengan warna berbeda, Anda bisa memakai variasi flood fill yang dimulai dari titik benih
  Cukup masukkan piksel ke stack hanya jika jarak warna itu lebih pendek daripada warna yang sudah mewarnai piksel tersebut

  • Buat saja adegan 3D dari kerucut tegak dengan warna berbeda, masing-masing memiliki puncak di setiap titik pada bidang 2D dan sumbunya tegak lurus terhadap bidang
    Jika dirender dari atas puncak dengan proyeksi ortografis 2D, z-buffer akan mempertahankan piksel dari puncak terdekat
    Mungkin ada cara melakukannya dengan shader, tetapi demo kerucut 3D klasik sangat mudah dipahami dan diimplementasikan

• Menarik bahwa D3 beralih dari algoritma Fortune ke https://mapbox.github.io/delaunator/
  Alasannya adalah karena “saat membuat triangulasi Delaunay atau diagram Voronoi, ini 5–10 kali lebih cepat daripada d3-voronoi, lebih kokoh secara numerik, memiliki rendering Canvas bawaan, serta menyediakan penelusuran graf Delaunay dan berbagai peningkatan lainnya”

  • Jika D3 menganggap delaunator adalah pilihan terbaik untuk efek seperti ini, maka sekarang saya tidak punya alasan lain untuk tidak menambahkannya ke library canvas saya selain kebiasaan menunda yang sudah mengakar
    Kode saya saat ini untuk menghitung tile sangat naif sampai menyakitkan
    Diskusi baru: https://github.com/KaliedaRik/Scrawl-canvas/discussions/120

• Gara-gara tulisan ini saya jadi mencari tahu Steve sekarang ada di mana
  Kami saling kenal beberapa dekade lalu

• Bacaan terkait yang layak dilihat: https://news.ycombinator.com/item?id=37998923 - Membuat diagram Voronoi dan triangulasi Delaunay dalam O(n log n) dengan algoritma Fortune (2020)
  Tulisan dan diskusi sebelumnya juga punya ringkasan singkat tentang algoritma-algoritma lain
  Secara pribadi, saya masih paling suka Jump Flooding Algorithm: https://en.wikipedia.org/wiki/Jump_flooding_algorithm