Diagram Voronoi

Diagram Voronoi membagi bidang di antara sekumpulan titik yang disebut titik acuan: setiap titik acuan memiliki wilayah berisi semua titik yang jaraknya ke titik acuan itu tidak lebih jauh daripada ke titik acuan lain mana pun. Gambar adalah jendela ke bidang, dan arsiran di dalam wilayah hanya untuk tampilan. Probe biru adalah pusat lingkaran kosong yang menjangkau titik acuan terdekat. Di sini kamu bisa memindahkan titik acuan dan melihat wilayah tetangganya berubah, menumbuhkan setiap wilayah dari titik acuannya, melihat triangulasi Delaunay, dan meratakan sebaran titik acuan menuju pola sarang lebah.

Titik-titik yang setidaknya sama dekat ke titik acuan $p$ seperti ke titik acuan lain $q$ membentuk setengah bidang yang dibatasi garis sumbu tegak lurus ruas $pq$. Wilayah $p$ adalah irisan setengah bidang ini, satu untuk setiap titik acuan lain, sehingga wilayahnya cembung. Hanya sebagian garis sumbu ini yang menjadi sisi. Titik acuan yang wilayahnya berbagi sisi dengan wilayah $p$ adalah tetangganya; setengah bidang lainnya sudah mencakup seluruh wilayah. Bingkai hanya membatasi jendela. Sebuah wilayah menjulur tak hingga jika dan hanya jika titik acuannya berada pada batas selubung cembung semua titik acuan.

Di tempat tiga wilayah atau lebih bertemu, sudutnya berjarak sama dari titik-titik acuannya, sehingga menjadi pusat lingkaran yang melalui semuanya. Bagian dalam lingkaran itu tidak memuat titik acuan. Jika ada, titik acuan itu akan lebih dekat ke sudut dan sudut tersebut menjadi milik wilayahnya. Biasanya tepat tiga wilayah bertemu di satu sudut. Empat wilayah bertemu jika tepat empat titik acuan terletak pada satu lingkaran kosong, seperti pada kisi persegi, sesuatu yang hampir tidak pernah terjadi pada titik acuan yang disebar acak.

Tumbuhkan menumbuhkan cakram dari setiap titik acuan dengan kelajuan yang sama. Setiap titik pertama kali dijangkau oleh titik acuan terdekatnya, sehingga batas pertumbuhan bertemu tepat di sepanjang sisi. Tampilan kecil memperlihatkan pertumbuhan yang sama dari samping. Di atas setiap titik, tingginya sama dengan jarak ke titik acuan terdekat: tinggi terendah dari kerucut $z = |x - s|$ yang berdiri di titik-titik acuan. Punggung bukit adalah sisi, dan pertumbuhan adalah air yang naik. Tempat terakhir yang terendam adalah titik tertinggi lanskap di dalam bingkai, yaitu pusat lingkaran kosong terbesar dengan pusat di dalam bingkai.

Triangulasi menghubungkan dua titik acuan jika wilayahnya berbagi sisi, lalu menambahkan diagonal putus-putus jika empat titik acuan atau lebih berbagi satu lingkaran kosong, seperti pada kisi persegi. Kecuali jika semua titik acuan segaris, hasilnya adalah triangulasi Delaunay. Lingkaran luar setiap segitiga adalah lingkaran kosong yang berpusat pada salah satu sudut diagram.

Ratakan memindahkan setiap titik acuan ke sentroid wilayahnya yang dipotong oleh bingkai, lalu membuat ulang wilayah, putaran demi putaran. Inilah algoritma Lloyd. Grafik kecil menampilkan rata-rata kuadrat jarak dari suatu titik dalam bingkai ke titik acuan terdekat, dibagi luas bingkai per titik acuan. Tidak ada putaran yang dapat menaikkan nilai itu. Jika titik acuannya tetap, pembagian menurut titik acuan terdekat meminimalkannya; jika wilayahnya tetap, sentroidlah yang meminimalkannya. Garis sarang lebah adalah batas bawah: nilai untuk segi enam beraturan yang sama besar dengan titik acuan di pusatnya. Dari titik acuan yang tersebar, proses berhenti pada keadaan stabil di dekatnya, bukan sarang lebah sempurna. Biasanya masih ada segi lima dan segi tujuh berdampingan, seperti dislokasi dalam kristal.

Diagram ini dinamai menurut Georgy Voronoy, yang mempelajari pembagian seperti ini dalam sembarang dimensi pada 1908. Triangulasinya dinamai menurut Boris Delaunay, yang menjelaskannya pada 1934.