Etiket arşivi: quad tree

Quad Tree (Dörtlü Ağaç)

Quad dörtlü, tree ağaç demektir. QuadTree adı üstünde bir ağaç yapısıdır. Her nodun (node) dört adet çocuğu (child) vardır. İki boyutlu uzayda kullanılmaktadır. Üzerinde çalışılan bölge dörtlü alanlara bölünerek uygulanır.

Örnek verecek olursak; İlgilendiğimiz alan aşağıdaki gibi olsun. Alanı iki boyutlu bir uzay gibi  düşünelim. Bu bölgeye her hangi bir eleman geldiğinde bölge dörde bölünür. Ağacın şekli üçüncü resimdeki gibi olur. Root’un sadece ilk elemanı doludur.

1  3 2

Bölgeye eleman gelmeye devam etsin. İkinci eleman ilk elemandan farklı bir bölgede olduğu için alan bölme işlemine gerek kalmadı. Ağaçta ise root’un ikinci elemanı B nodu oldu.

quadtree1 5

Yeni elemanımız B ile aynı bölgede olsun. Bu durumda B’nin bulunduğu bölge dörde bölünecek ve ağacın yapısı değişecektir.

6 7

Bölgeye birkaç eleman daha ekleyelim ve ağacın durumuna bakalım.

8 9

E elemanı bölgeye eklendiğinde B’nin bulunduğu alan tekrar dörde bölünür. Ağaçta B bir alta geçerek E ile kardeş olur.

10 11

Bölgeye F elemanı eklendiğinde ise durum aşağıdaki ağaçtaki gibi olur.12 13

Sorularınız olursa yardımcı olmaya çalışırım. Konuyla ilgili buradan da bilgiye ulaşabilirsiniz.