Fortune Algoritması ile Voronoi Diyagramı Oluşturmak

• Fortune’s Algorithm, Voronoi diyagramını O(n log n) sürede oluşturabilir; ancak uygulaması zor olduğundan, büyük diyagramları tekrar tekrar üretmek gerekmiyorsa O(n²) bir uygulama ya da bir kütüphane kullanmak daha gerçekçidir
• Voronoi diyagramı, düzlemi birden çok site noktasına göre en yakın bölgelere ayırır ve sınırlar, iki site noktasına eşit uzaklıktaki noktalar tarafından oluşur
• Algoritma, soldan sağa hareket eden bir sweep line ile parabol yaylarından oluşan cephe hattı beachline'ı korur ve yalnızca site event ile circle event'leri işler
• site event, yeni bir yay ekleyerek mevcut bir yayı böler ve incomplete edge oluşturur; circle event ise ortadaki yayı kaldırırken Voronoi Vertex ve half edge'leri tamamlar
• Pratik bir uygulamada event queue, beachline, incomplete edge haritası ve DCEL birlikte ele alınmalıdır; geçersiz circle event'leri kaldırmak ve kalan edge'leri temizlemek karmaşıklığı ciddi biçimde artırır

---

Uygulama zorluğu ve kullanım kapsamı

• Fortune’s Algorithm, Voronoi diyagramını O(n log n) zamanda üreten bir algoritmadır
• Gerçek kullanım amacı varsa, doğrudan uygulamaya başlamadan önce gerekli ölçeği değerlendirmek daha iyidir
  • Saniyede birden fazla büyük diyagram üretmeniz gerekmiyorsa, O(n²) bir uygulama daha kolay bir seçenek olabilir
  • Daha gerçekçi bir alternatif, mevcut bir kütüphane kullanmaktır
• Algoritmanın çalışma sonucu görsel olarak ilgi çekicidir, ancak uygulama süreci zordur ve sık sık hayal kırıklığı yaratabilir

Voronoi diyagramının temel kavramı

• Voronoi diyagramı, düzlemi birden çok bölgeye ayırma yöntemidir ve prosedürel harita üretiminde sık kullanılır
• Girdi olarak seçilen noktalara site veya seed denir
• Her site'a karşılık gelen cell, düzlemde o site'a en yakın olan noktaların kümesidir
• Hücre sınırları, iki site'a eşit uzaklıktaki noktalardan oluşur
• Hücre köşelerinin buluştuğu Voronoi Vertex, üç site'a eşit uzaklıktaki noktadır

sweep line, beachline, event

• Fortune’s Algorithm, soldan sağa hareket eden dikey bir doğru olan sweep line kullanır
• sweep line bir site ile karşılaştığında, odağı o site olan bir parabol yayı oluşur; sweep line uzaklaştıkça yay büyür
• Farklı site'lara ait iki yayın kesiştiği nokta, iki site'a eşit uzaklıkta olduğu için hücre sınırı olur
• İki sınır birleştiğinde diyagramın bir köşesi oluşur
• Etkin yayların cephe hattına beachline denir
• Gerçek uygulama, sweep line'ı piksel piksel ilerletmek yerine yalnızca hesaplanabilir belirli noktalar olan event'leri işler
  • site event: Önceden bilinen site koordinatlarıyla tanımlanır; işlendiğinde beachline'a yeni bir yay eklenir
  • circle event: beachline üzerindeki üç yayla tanımlanır; işlendiğinde bir yay kaldırılır ve Voronoi Vertex ile half edge oluşturulur

Parabollerle sınır bulmak

• Algoritmada paraboller, alışılmış y = ax^2 + bx + c biçimi yerine locus definition ile ele alınır
• Bir parabol, bir focus point ve bir directrix ile tanımlanır
  • focus point, site olur
  • directrix, sweep line olur
• Aynı sweep line'ı directrix olarak kullanan iki parabolün kesişim noktası, iki site'a eşit uzaklıktadır
• Bu nedenle iki parabolün kesişimini bulmak, iki site arasındaki equiedge'i bulmayı sağlar
• Parabolün x koordinatını hesaplayan sözde kod ile, sweep line konumu değiştikçe iki parabolün kesişiminin sınır boyunca nasıl hareket ettiğini gösteren örnek kullanılır

beachline gösterimi ve site event işleme

• beachline üzerindeki her yay, yalnızca ilgili site'ın koordinatlarıyla ifade edilebilir
  • sweep line tüm yaylar için ortaktır
  • Uygulamada yaylar ayrı nesneler yerine 2D koordinatlar olarak ele alınır
• beachline, noktaların basit bir sırası olarak temsil edilebilir
  • Örnek: [arc1, arc2], [arc1, arc2, arc3]
  • Aynı site'a ait yaylar beachline üzerinde birden fazla kez görünebilir
  • Örnek: [arc1, arc3, arc1, arc2]
• Bir site event oluştuğunda, yeni site'dan sola doğru bir çizgi çekildiğinde karşılaşılan beachline yayı bulunur ve yeni yay bu yayı böler
• Yeni site L, mevcut beachline [.., i, j, k, ..] içindeki j yayını bölerse yapı [.., i, j, L, j, k, ..] olur
• site'lar x koordinatına göre sırayla kuyruğa girer ve her işleme sonrasında beachline ile event adayları güncellenir

circle event ve circumcircle

• beachline üzerindeki [.., i, j, k, ..] üç yayında iki sınırın birleştiği bir durum oluşursa ortadaki j yayı kaybolur
• Bu sırada, üç site'dan geçen bir circumcircle vardır ve çemberin merkezi üç site'a eşit uzaklıktadır
• circumcircle merkezi, Voronoi Vertex olur
• circle event, çemberin sağ uç noktası olan circle point temel alınarak event queue'ya yerleştirilir
• Yeni bir site, circle point'e ulaşmadan önce çemberin içinde bulunursa mevcut circle event geçersiz hale gelir
  • Çünkü yeni site önce ortadaki yayı böler ve üç yay kombinasyonu artık korunmaz
  • Eski i, j, k üçlüsü kaybolur; bunun yerine i, j, L, L, j, k gibi yeni üçlüler incelenmelidir

incomplete edge ve half edge

• incomplete edge, bir ucu sabitlenmiş, diğer ucu ise iki parabol yayının kesişimiyle tanımlanan bir doğrudur
• Yeni bir yay site event ile eklendiğinde iki incomplete edge oluşur
  • Sabit nokta, yeni yayın mevcut beachline ile buluştuğu koordinattır
  • Yeni yay j, mevcut yay i'yi bölerse [i, j], [j, i] kesişimlerine karşılık gelen edge'ler oluşur
• Bir circle event sırasında iki incomplete edge çarpışırsa bu çarpışma noktası Voronoi Vertex olur
• Mevcut incomplete edge'ler bu noktada half edge olarak tamamlanır ve artık komşu hale gelen iki yay arasında yeni bir incomplete edge oluşturulur

Yalnızca saat yönünün tersine olan çemberler circle event olur

• beachline üzerinde [i, j, k, j, i] varsa ijk ve kji her ikisi de bir çember oluşturabilir, ancak ikisi de geçerli circle event değildir
• Ortadaki yayın kaybolduğu durum, yalnızca sınırların gerçekten yakınsadığı taraftır
• Programda üç noktanın orientation'ı determinant ile belirlenir
  • determinant negatifse saat yönünün tersinedir ve bir circle event olur
  • determinant pozitifse saat yönündedir ve circle event değildir
  • determinant 0 ise üç nokta doğrusaldır ve çember yoktur

Algoritmanın genel akışı

• Girdi site'ları x koordinatına göre sıralayıp site event olarak kuyruğa koyun
• Kuyruk boşalana kadar sıradaki event'i çıkarıp işleyin
• site event işleme:
  • Henüz gerçekleşmemiş circle event'ler içinde yeni site'ın çemberin içine girdiği event'leri kaldırın
  • Yeni site'ın böleceği beachline yayını bulun
  • Yeni yayı ekleyip mevcut yayı bölün
  • İki incomplete edge ekleyin
  • Yeni oluşan üçlülerin circle event üretip üretemeyeceğini kontrol edin
• circle event işleme:
  • circumcircle merkezini Voronoi Vertex olarak ekleyin
  • Ortadaki yayı beachline'dan kaldırın
  • Kaldırılan yay yüzünden geçersiz hale gelen gelecekteki circle event'leri kaldırın
  • Yeni komşu olan yayların üçlülerini inceleyip circle event ekleyin
• Kuyruk boşaldığında, kalan incomplete edge'leri diyagram sınırına kadar uzatın ve sınırla kesişen noktalarda Voronoi Vertex oluşturun

Odin uygulamasındaki veri yapıları

• Örnek uygulama, C'ye alternatif bir dil olan Odin ile yazılmıştır
• Tüm kod RedPenguin101/voronoi deposunda bulunur
• Temel türler:
  • V2: [2]int biçiminde bir 2D nokta
  • PointPair: iki V2'den oluşan çift
  • Event: {site: bool, a, b, c: V2} yapısı
• Event'in anlamı türüne göre değişir
  • site event'te a, site koordinatıdır; b ve c kullanılmaz
  • circle event'te a, b, c, event'i oluşturan beachline üzerindeki üç yaydır
• Fortune yapısı şu durumu yönetir
  • beachline: V2 dizisi
  • queue: Event dizisi
  • incomplete_edges: PointPair -> V2 haritası
  • vd: Voronoi diyagramını saklayan DCEL

Uygulamada atlanan veya basitleştirilen kısımlar

• beachline bir vektör olarak gösterilmiştir, ancak verimlilik için binary tree daha uygundur
• event queue da kavramsal olarak bir priority queue'dur, ancak örnek uygulamada diziye sıralı ekleme yöntemi kullanılır
• circle event geçersizleştirme işlemi, gelecekteki event'leri dolaşıp kontrol ederek yapılır; daha hızlı bir yönteme ihtiyaç olduğuna dair bir TODO bulunur
• clean_beachline_edges, beachline'ın iki ucundaki gereksiz yayları kesip atma prosedürüdür
• Uygulama; aynı x koordinatına sahip site'lar, circle point ile site'ın çakıştığı durumlar ve referans noktası çakışmaları gibi istisna işlemlerini içerir
• Kuyruk boşaldıktan sonra kalan incomplete edge'leri, twin'i olmayan half edge'leri ve vertex'leri temizleyen son adım yalnızca basit matematik işlemleri olarak ele alınır

DCEL ile Voronoi diyagramını saklamak

• Voronoi diyagramı genellikle Doubly Connected Edge List (DCEL) ile saklanır
• DCEL, vertex ve edge'lerden oluşan bir cell-complex'i işlemeyi kolaylaştıran bir veri yapısıdır
• Edge merkezli bir gösterimdir, ancak vertex ve face bilgilerini de birlikte tutar
• Normal bir edge'in yönü yoktur, fakat DCEL'de her edge iki yönlü iki half edge olarak saklanır
• Voronoi diyagramında DCEL'e kaydedilen vertex'ler site değil, Voronoi Vertex'lerdir
• E edge'inin hedefi E.twin.origin ile, sağdaki face ise E.twin.left ile elde edilir

[GN⁺]

Hacker News yorumları

• Bir süre önce ClojureScript ile Fortune algoritmasının ilerleyişini animasyonlu gösteren bir uygulama yapmıştım: https://voronoi.ajwerner.net/#/app-diagrams
  Gerçekten çok güzel bir algoritma
  Ancak o projeden sonra Fortune algoritmasından biraz soğudum; çünkü kayan nokta sayısal kararlılığı iyi değil
  Noktalar aynı doğru üzerindeyse ya da kayan nokta açısından neredeyse aynı doğru üzerindeymiş gibi yakınsa bozulabiliyor
  Yanlış hatırlamıyorsam bu açıdan delaunator daha iyi: https://github.com/mapbox/delaunator

  • Animasyon şimdiye kadar gördüklerimin en iyisi
    Referans sayfasında “old” uygulamasına bir bağlantı görünüyor; mevcut animasyon sürümünü de açık kaynak olarak yayımlama ihtimali var mı merak ediyorum

• Birkaç yıl önce böyle bir 3D görselleştirme yapmıştım: https://x.com/KangarooPhysics/status/1253336959755251716

• uBlock Origin ile tanınan Raymond Hill’in bir JavaScript uygulaması var: https://github.com/gorhill/Javascript-Voronoi
  Burada biraz kurcalayıp hareketli hale getirdim: https://animations.adgent.com/voronoi.html

  • Bu animasyon bana A Scanner Darkly (2006) tarzını hatırlatıyor
    Bir videoyu girdi olarak alıp Voronoi biçiminde gösteren bir algoritmaya vermek mümkün mü merak ediyorum
    O noktada teknik olarak Voronoi diyagramı olmayabilir ama oldukça havalı görünebilir

• D3.js’te yeni bir uygulama var: https://github.com/d3/d3-delaunay
  O sayfanın alt tarafında kullanılan süpürme algoritmasının açıklaması ve JavaScript dışındaki dillerdeki diğer uygulamaların listesi var
  Eski d3-voronoi kullanımdan kaldırılacak, ama buradan görülebilir: https://github.com/d3/d3-voronoi

• Kenarlarla ilgilenmiyor, yalnızca her noktayı farklı bir renkle boyamak istiyorsanız, tohum noktalarından başlayan bir flood fill varyasyonu kullanabilirsiniz
  Bir pikseli yalnızca o rengin mesafesi, pikselde hâlihazırda boyanmış renkten daha kısa olduğunda yığına eklemek yeterli

  • 2D düzlemdeki her noktayı tepe noktası yapan, farklı renklerde dik dairesel konilerden oluşan bir 3D sahne kurup ekseni düzleme dik yerleştirebilirsiniz
    Tepelerin üstünden 2D ortografik projeksiyonla render ederseniz z-buffer, en yakın tepe noktasının pikselini korur
    Bunu shader ile yapmanın bir yolu da vardır, ama klasik 3D koni demosunu anlamak ve uygulamak çok kolaydır

• D3’ün Fortune algoritmasından https://mapbox.github.io/delaunator/’a geçmiş olması ilginç
  Gerekçe şu: “Delaunay üçgenlemesi veya Voronoi diyagramları oluştururken d3-voronoi’den 5–10 kat daha hızlı, sayısal olarak daha sağlam, yerleşik Canvas render desteğine sahip ve Delaunay grafı üzerinde gezinme ile çeşitli iyileştirmeler sunuyor”

  • D3 bu tür efektler için delaunator’ın en iyi seçenek olduğunu düşünüyorsa, bunu artık kendi canvas kütüphaneme eklememek için doğal erteleme alışkanlığım dışında bir bahanem kalmadı
    Şu an döşemeleri hesaplayan kod acı verecek kadar saf
    Yeni tartışma: https://github.com/KaliedaRik/Scrawl-canvas/discussions/120

• Bu yazı Steve’in bu aralar nerede olduğunu aramama neden oldu
  Onu onlarca yıl önce tanıyordum

• Konuyla ilgili okunmaya değer bir yazı: https://news.ycombinator.com/item?id=37998923 - Fortune algoritmasıyla O(n log n) sürede Voronoi diyagramları ve Delaunay üçgenlemesi oluşturmak (2020)
  Önceki yazı ve tartışmada diğer algoritmaların kısa özetleri de var
  Kişisel olarak hâlâ en çok Jump Flooding Algorithm hoşuma gidiyor: https://en.wikipedia.org/wiki/Jump_flooding_algorithm