Quadtree

Tekrar merhaba arkadaşlar C++ ile ilgili olan yazılarımıza biraz ara verip bugün gerek oyunlarda, gerek coğrafi bilgi sistemlerinde, gerekse arazi görselleştirmesi, resim işleme ve bunun gibi bir çok alanda kullanılan bir veri yapısından kısaca bahsetmek istiyorum: “Quadtree“. Bu veri yapısının detaylarına çok girmeden önce “Spatial Data Structrues” ve “Spatial Partitioning” denilen yani Uzaysal Veri Yapıları ve Uzaysal Bölümleme konusunu bir bakalım.

Giriş

Bu tarz veri yapılarının en önemli amacı gerek görselleştirme gerek fizik işlemleri gerekse arama gibi işlerde yapılan karşılaştırma miktarını düşürmektedir (Bu sözü unutmayın nasıl sorusu bir sonraki başlıkta). Genel olarak hiyerarşik bir doğaya sahiptirler. Verinin yapısına dağılımına ve kullanım alanına göre kullanılacak veri yapısı belirlenir. Örneğin 2B noktasal veriler için “Grid” veya “Quadtree” daha öncelikli tercih edilmesi gerekirken 3 İç ortamlar için “BSP Tree” veri yapısı örneğin Octree’ye göre daha öncelikle tercih edilmelidir.

Aşağıda örnek bir Octree görebilirsiniz:

Image result for spatial partitioning octrees

Aşağıda örnek bir BSP Tree görebilirsiniz:

Quadtree

Şimdi gelelim yazımızın solistine yani Quadtree’ye. Quadtree’ler temel olarak 2B uzayın eşit bir şekilde 4 e bölünmesine dayanır. Yani her bir ağaç düğümü (node) 4 çocuk düğüm içerir ve genel olarak ilgilenilen veriler en alt seviyedeki (“leaf”) düğümlerinde tutulur. Bölümleme genel olarak her bir düğüm için tutulacak olan nesne adeti aşıldığında gerçekleşir ve bu durumda ağaç düğümü bir kez daha bölünür ve nesnelere bu düğümlere dağıtılır. Genel olarak eklenen nesneler karesel olarak ilgili düğümlerin sınırları ile karşılaştırılarak dağıtılırlar. Aşağıdaki figür veri yapısını kafanızda canlandırmanıza yardımcı olacaktır. Her seviye bir önceki ile aynı sınırlara sahip olsa da, elemanların dağıtılabileceği düğüm sayısı alt seviyelere indikçe artmaktadır. Genel olarak bu derinlik sabit bir sayı olarak belirlenir.

Yukarıdaki figürden de anlaşılacağı üzere aslında Quadtree’ler 4 çocuklu bir ağaç olarak ta düşünülebilirler. Aşağıda bu minvaldeki figürü görebilirsiniz.

Tree2D

Wikipedia dan öğrendiğimiz kadarı ile bu veri yapısı ilk defa 197 yılında Raphael Finkel ve J. L. Bentley tarafından Q-Tree olarak adlandırılmıştır.

Aslında bu anlamda yukarıda bahsettiğimiz gibi “Binary Tree”‘ye oldukça benzemektedir, sadece iki çocuk yerine dört çocuğa sahiptir. Bir çok farklı varyasonu vardır (yazımın sonunda bir kaçına değineceğim), quadtree’ler içerdikleri veri tiplerine göre (nokta, çizgi veya poligon) sınıflandırılabilmektedirler. 3B uzayı düzgün bir şekilde bölmek için ise Octree veri yapısı kullanılmaktadır. Bu veri yapısı da uzayı eşit 8 parçaya bölmekte ve ağrılıklı olarak 3B nesneler için kullanılmaktadır. Bir de daha genelleştirilmiş olan kd-tree’ler vardır ki. Buna da ayrı bir yazı ayırmayı planlıyorum.

Şimdi gelelim yazımızın başında bahsettiğim “yapılan karşılaştırma miktarını düşürmektedir” ifadesinin Quadtree’ler için nasıl işlediğine. Bunu basit bir örnek üzerinden açıklamaya çalışacağım:

 

Şimdi yukarıda verildiği gibi 6 adet nesnemizin olduğu 2 boyutlu bir dünya düşünelim. Amacımız ekranımıza giren nesneleri görüntülemek. Mevcut ekranımızda kırmızı noktalı dikdörtgen ile gösterilsin.

Şimdi Quadtree kullanmadığımız durumda hangi noktaların gösterilmesi gerektiğini anlamak için bütün noktalar ile bu ekranın kapsadığını alanı karşılaştırmamız gerekiyor. Bu da 6 karşılaştırma demek. Quadtree kullandığımız durumda ise mevcut ekranımız quadtree’nin sol üst düğümü ile kesiştiği için sadece bu düğüme bakmamız yeterli ve bu durumda da sadece 1 karşılaştırma yetiyor. Ortalama şartlara baktığımızda quadtree ve genel olarak bu tarz uzay bölümleme veri yapıları bu noktada büyük avantaj sağlamakta.

Quadtree Operasyonları

Ekleme (“Insertion”)

  • Eklenecek olan nesneyi içerecek (yani karesel alanı, quadtree düğümü sınırları içerisinde kalacak) dip (“Leaf”) düğümü bulunana kadar “recursive” olarak ilerlenir,
  • Daha sonra ilgili düğüme nesne eklenir,
  • Eğer nesnenin eklendiği düğümdeki nesne adeti izin verilen sınırlar içerisinde ise işlem tamamlanır,
  • Eğer nesnenin eklendiği düğümdeki nesne adeti izin verilen sınırı aşar ise ilgili düğüm tekrar dörde bölünür ve nesneler bu düğümlere dağıtılır.

Silme (“Delete”)

  • Silinecek olan nesneyi içerecek dip (“Leaf”) düğümü bulunana kadar “recursive” olarak ilerlenir,
  • Daha sonra ilgili düğümden nesne silinir.

Sorgulama (“Query”)

  • Kök düğümden başlanarak ilgili nesne ile düğümün sınırları karşılaştırılır ve kesişen düğüme kadar “recursive” olarak ilerlenir.
  • Eğer kesişen bir düğüm bulunur ise o düğümdeki bütün nesneler karşılaştırılır.
  • Benzer şekilde verilen dörtgensel bir alan ile kesişen elemanlar da bu şekilde bulunabilir.

Örnek Quadtree

Şimdi gelelim temel bir Quadtree sınıfına. Her veri yapısında olduğu gibi bu veri yapısı da özel
ihtiyaçlar doğrultusundan özelleştirilebilir ve de özelleştirilmelidir. Fakat ilk iterasyonda sizlere temel bir çok uygulama için ihtiyacınız karşılayacak ve genel quadtree mantığını anlatacak bir örnek vereceğim. Bu örneği baz alarak kendi ihtiyaçlarınız doğrultusunda bu veri yapısını güncelleyebilirsiniz.

İlgili quadtree sınıfının .cpp dosyasına da aşağıdan ulaşabilirsiniz.

Bu sınıf ve örnek uygulama için https://github.com/yazilimperver/DataStructures ‘den ilgili kodları çekebilirsiniz. Örnek uygulama fare sol tıkı ile nesne eklemekte ve mevcut quadtree farklı renkler ile görselleştirilmekte. Daha önce de ifade ettiğim gibi bu çok basit ve performans vs göz önüne alınmadan yazılmış bir örnek. Sadece mantığı anlatmak adına bu şekilde yazıldı. Performans odaklı bir sürümünü de yakın zamanda ilgili “repository” ekleyeceğim canlar.

Sonuç

Sonuç olarak Quadtree’ler kolay bir veri yapısı olmaları sebebi ile 2B verilerin yönetilmesinde tercih edilebilirler. Alt düğüm sınırları çalışma zamanında hesaplanabilir. Düğümleri dinamik olarak çalışma zamanında bellekte oluşturmak yerine bir havuz yapısı kullanılması da performansı arttıracaktır. Noktasal veriler için kullanılacak Quadtree’ler ile alansal veya çizgisel nesneler için farklı ve özelleşmiş quadtree’ler kullanılabilir.

Her veri yapısında olduğu gibi ihtiyaçlarınız belirleyip ona göre Quadtree kullanımına karar vermelisiniz. Quadtree değilse peki ne sorusunun diğer muhatabı genelde “uniform grid” olur. Grid yapısı için de ayrıca bir yaz yazmayı planlıyorum.

Genel olarak dinamik nesnelerin ağırlıklı olduğu durumlarda uniform grid veya özelleşmiş quadtreeler tercih edilebilir. Ayrıca statik nesnelerin indekslenmesinde ise Quadtree’ler her ne kadar sorgulamada “uniform grid”‘e nazaran çok az bir şekilde yavaş olsa da boyut anlamında büyük avantaj sağlarlar. Bunun ile birlikte indeksleyeceğiniz nesnelerin boyutları değişkense bu da “uniform grid” için sıkıntı yaratabilir (hareket durumunda bir çok hücrede güncelleme gerekecektir).

Aşağıda Quadtree’lere ilişkin bir çok bağlantı bulabilirsiniz. Bir sonraki yazımda görüşmek üzere.

http://www.umiacs.umd.edu/~ramani/cmsc878R/p187-samet.pdf => Yine bu veri yapısı ile ilgili eski ama sağlam bir kaynak

http://jimkang.com/quadtreevis/ => İnteraktif bir quadtree uygulaması

https://web.archive.org/web/20120204170335/http://homepages.ge.ucl.ac.uk/~mhaklay/java.htm#PR => Quadtree, varyasyonları ve birçok diğer veri yapısı için başvurabilirsiniz.

https://github.com/timohausmann/quadtree-js => Javascript versiyonu

https://www.gamasutra.com/view/feature/3434/continuous_lod_terrain_meshing_.php?page=4 => Arazi görselleştirmesinde kullanımına bir örnek

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.