Fortune algoritmasını kullanarak Voronoi diyagramı oluşturma

Voronoi diyagramı oluşturma

• Voronoi diyagramı nedir?

  • Voronoi diyagramı, düzlemi birden çok bölgeye ayırma yöntemidir ve çoğunlukla prosedürel olarak harita üretmek için kullanılır.
  • Düzlem üzerinde 'site' adı verilen birden çok nokta seçilir ve her siteye karşılık gelen bölge, o siteye en yakın olan tüm noktaları içerir.
  • Her bölgenin sınırı, iki siteye eşit uzaklıkta olan noktalardan oluşur. Üç siteye eşit uzaklıkta olan nokta ise 'Voronoi köşesi' olarak adlandırılır.

• Fortune algoritması

  • Fortune algoritması, diyagramı oluşturmak için düzlemi soldan sağa doğru 'süpüren' bir çizgi kullanan bir yöntemdir.
  • Süpürme çizgisi bir site ile karşılaştığında, onun etrafında bir 'kabarcık' (parabol yayı) oluşur ve süpürme çizgisi uzaklaştıkça bu kabarcık büyür.
  • İki sitenin yayları çarpıştığında, bu çarpışma noktası hücrelerin sınırı olur.
  • Tüm etkin kabarcıkların sınırına 'beachline' denir.

• Terim açıklamaları

  • Site: Voronoi diyagramının şeklini belirleyen 2 boyutlu nokta.
  • Süpürme çizgisi: Bölgeyi kat eden dikey çizgi; olay kuyruğundaki her olayı işler.
  • Beachline: Birden çok yaydan oluşan çizgi; olaylar işlendiğinde yaylar eklenir veya kaldırılır.
  • Kesişim noktası: Beachline üzerindeki iki yayın buluştuğu nokta; ilgili sitelere eşit uzaklıktadır.
  • Olay kuyruğu: Site ve çember olaylarının saklandığı yer; x koordinatına göre artan sırada sıralanır.
  • Site olayı: Olay kuyruğundaki iki olay türünden biri; ilgili sitenin koordinatıyla tanımlanır.
  • Çember olayı: Kuyruktaki diğer olay türü; çember çevresi üzerindeki üç yay ile tanımlanır.
  • Voronoi köşesi: Üç siteye eşit uzaklıktaki nokta; hücrenin köşesidir.
  • Eşit uzaklık sınırı: İki siteye eşit uzaklıktaki çizgi.
  • Tamamlanmamış sınır: Bir ucu sabit bir nokta olan, diğer ucu ise iki parabol odağının kesişimiyle tanımlanan çizgi.

• Parabol teğetleri

  • Parabol kavramı ve özellikleri algoritmada çok önemlidir.
  • Parabol, odak noktası ve bir doğruyla (directrix) tanımlanır.
  • İki sitenin odaklarını belirleyip süpürme çizgisini directrix olarak ayarlarsanız, iki parabolün kesişim noktasını bularak iki siteye eşit uzaklıktaki sınır çizgisini bulabilirsiniz.

• Yeniden beachline'a dönelim

  • Beachline, süpürme çizgisinin belirli bir konumunda tüm yayların 'sınırı'dır.
  • Her yay, sitenin odak noktasıyla temsil edilebilir.
  • Beachline, basit bir nokta dizisi olarak ifade edilebilir.

• Yeni yay, süpürme çizgisi yeni bir siteyle karşılaştığında oluşur

  • Beachline bir nokta dizisidir ve her nokta bir siteyi ve bir yayı temsil eder.
  • Süpürme çizgisi yeni bir siteyle karşılaştığında yeni bir yay oluşturulur ve diziye eklenir.

• Kesişen sınırlar ve çevrel çember

  • Üç site bir çemberin çevresi üzerindeyse, çemberin merkezi bu üç noktaya eşit uzaklıktadır.
  • Çevrel çemberin merkezi bir Voronoi köşesi olur.

• Tamamlanmamış sınırlar

  • Tamamlanmamış sınırın bir ucu sabit bir nokta, diğer ucu ise iki yayın kesişim noktasıdır.
  • İki tamamlanmamış sınır çarpıştığında bir Voronoi köşesi oluşur ve tamamlanmamış sınırlar yarı sınıra dönüşür.

• Yalnızca saat yönünün tersindeki çemberler çember olayı üretir

  • Yalnızca üç yay saat yönünün tersine okunuyorsa çember olayı oluşur.

• Özet

  • Bir site kümesi verildiğinde, tüm site noktaları kuyruğa 'site' olayı olarak eklenir ve x değerine göre sıralanır.
  • Kuyruk boş olmadığı sürece, bir sonraki olay kuyruktan çıkarılıp işlenir.
  • Olay bir site olayıysa, beachline'a yeni bir yay eklenir ve tamamlanmamış sınırlar oluşturulur.
  • Olay bir çember olayıysa, Voronoi köşesi eklenir ve beachline'dan bir yay kaldırılır.