Quadtree

Bir dörtlü ağaç ya da kuaterner ağacı ( S ağacı ) a, ağaç benzeri veri yapısı her bir düğüm dört çocuk sahip olduğu. Dörtlü ağaçlar genellikle iki boyutlu bir alanı yinelemeli olarak dört düğüme bölerek bölmek için kullanılır .

Dörtlü ağaçlar iki boyutlu benzetme vardır octrees . İsim dörtlü ve ağaçtan oluşur . Dört ağacın her düğümü, temsil ettiği alanı dört alt alana böler.

Türler

Dört ağaçlar, bölgeler, noktalar, çizgiler ve eğriler dahil olmak üzere temsil ettikleri veri türüne göre sınıflandırılabilir. İşte bazı yaygın dörtlü ağaç türleri:

Dörtlü ağaç "bölgesi"

Dörtlü ağaç "bölgesi", bölgeyi dört eşit çeyreğe bölerek uzayın iki boyutta bir bölümünü temsil eder, ardından her çeyrek dört alt çeyreğe bölünür ve her "terminal düğümü" belirli bir alt kısma karşılık gelen verileri içerir bölge. Ağacın her bir düğümünün tam olarak: ya dört çocuğu vardır ya da hiçbiri (bir terminal düğümü durumunda). Dörtlü ağaç "bölgesi" bir tür önek ağacıdır .

Derinliği n olan bir "bölge" dörtlü ağaç  , her bir pikselin değerinin 0 veya 1 olduğu 2 n  × 2 n piksellik bir görüntüyü temsil etmek için kullanılabilir . Ana düğüm tüm görüntüyü temsil eder. Belirli bir bölgedeki piksellerin tümü 0 değilse veya tümü 1 değilse, bu bölge alt bölümlere ayrılır. Bir görüntünün böyle bir temsilinde, her bir terminal düğümü tümü 0 veya tümü 1 olan bir piksel bloğunu temsil eder.

Bir "bölge" dörtlü ağacı, bir veri alanının değişken çözünürlüklü temsili olarak da kullanılabilir. Örneğin, bir alanın sıcaklıkları, her bir terminal düğümünün temsil ettiği alt bölgenin ortalama sıcaklığını depoladığı bir dörtlü ağaçta saklanabilir.

Bir nokta kümesini temsil etmek için bir "bölge" dörtlü ağacı kullanılırsa (örneğin, bir şehir grubunun enlemleri ve boylamları), bölgeler, her bir terminal düğümü yalnızca bir nokta içerene kadar alt bölümlere ayrılır.

"Nokta" dörtlü ağaç

"Nokta" dörtlü ağaç , iki boyutlu bir "nokta" verisini (örneğin, bir coğrafi koordinat) temsil etmek için kullanılan, ikili bir ağacın bir uyarlamasıdır . Bir alt bölümün merkezi her zaman bir noktada olduğundan, gerçek bir ağaç iken tüm dörtlü ağaçların özelliklerini paylaşır . Ağacın şekli, verilerin işlenme sırasına bağlıdır. Bu tür bir temsil, genellikle O (log n) zamanında çalışan, sıralı iki boyutlu "nokta" verilerine kıyasla genellikle çok verimlidir .

Bir "nokta" dörtlü ağacın bir düğümünün yapısı

"Nokta" dörtlü ağacın düğümü, ikili ağacın düğümüne benzer , bu büyük fark: ilkinde dört işaretçi bulunur (her çeyrek için bir tane), ikincisinde ise yalnızca iki tane ("sol" ve "sağ") vardır. Diğer bir fark, bir anahtar genellikle x ve y koordinatlarına göre iki kısma ayrılır. Bu nedenle bir düğüm aşağıdaki bilgileri içerir:

  • dört işaretçi: dörtlü ['HAYIR'], dörtlü ['NE'], dörtlü ['SO'] ve dörtlü ['SE']
  • sırayla şunları içeren bir nokta:
    • bir anahtar: genellikle koordinatlar (x, y)
    • bir değer: örneğin, bir ad.

"Kenar" dörtlü ağaç

"Kenar" dörtlü ağaçları, noktalar yerine özellikle çizgileri depolamak için kullanılır. Eğriler, hücrelerin çok ince bir çözünürlüğe bölünmesi ile yaklaştırılır. Bu, aşırı derecede dengesiz ağaçlara neden olabilir, dolayısıyla indekslemenin değerini geçersiz kılar.

"Poligonal harita" dörtlü ağacı

"Poligonal harita" dörtlü ağacı (veya CP dörtlü ağacı), potansiyel olarak dejenere (yani izole köşelere veya kenarlara sahip) çokgen koleksiyonlarını depolamak için kullanılan bir dörtlü ağacın bir varyasyonudur. Her bir "siyah düğüm" içinde hangi bilgileri depoladıklarına bağlı olarak değişen üç ana CP-dörtlü ağaç sınıfı vardır. CP3 dörtlü ağaçlar herhangi bir miktarda "kesmeyen kenarları" ve en fazla bir noktada depolayabilir. CP2 dörtlü ağaçlar, tüm kenarların aynı uç noktayı paylaşması gerekmesi dışında CP3 dörtlü ağaçlarla aynıdır. Son olarak, CP1 dörtlü ağaçlar CP2 dörtlü ağaçlara benzer, ancak "siyah düğümler" bir noktayı ve kenarlarını veya yalnızca bir noktayı paylaşan bir kenar kümesini içerebilir (ancak bir nokta ve bir dizi kenara sahip olamazsınız. bu nokta).

Dörtlü ağaçların bazı yaygın kullanımları

Sözde kod

Aşağıdaki sözde kod , bir dörtlü ağacın yalnızca noktaları işlemenin olası bir uygulamasını gösterir. Başka geçerli yaklaşımlar var.

Önkoşullar

Aşağıdaki yapıların kullanıldığı varsayılmaktadır.

// Objet de coordonnées simples pour représenter des points et des vecteurs struct XY { float x; float y; function __construct(float _x, float _y) {...} } // Zone de délimitation alignée sur l'axe, représentée par sa demi-dimension et son centre struct AABB { XY center; XY halfDimension; function __construct(XY center, XY halfDimension) {...} function containsPoint(XY p) {...} function intersectsAABB(AABB other) {...} }

QuadTree sınıfı

Bu sınıf hem bir dörtlü ağacı hem de onun ana düğümünü temsil eder.

class QuadTree { // Constante arbitraire indiquant combien d'éléments peuvent être stockés dans ce nœud de quadtree constant int QT_NODE_CAPACITY = 4; // Zone de délimitation alignée sur l'axe (représentée par sa demi-dimension et son centre) // représentant les limites de ce quadtree AABB boundary; // Points de ce nœeud de quadtree Array of XY [size = QT_NODE_CAPACITY] points; // Enfants QuadTree* northWest; QuadTree* northEast; QuadTree* southWest; QuadTree* southEast; // Méthodes function __construct(AABB _boundary) {...} function insert(XY p) {...} function subdivide() {...} // créer quatre enfants permettant de diviser ce quadrant en quatre quadrants d'égales dimensions function queryRange(AABB range) {...} }

Yerleştirme

Aşağıdaki yöntem, gerekirse bir bölme gerçekleştirerek, dörtlü bir ağacın uygun çeyreğine bir nokta ekler.

class QuadTree { ... // Insérer un point dans le QuadTree function insert(XY p) { // Ignorer les objets qui n'appartiennent pas à ce quadtree if (!boundary.containsPoint(p)) return false; // l'objet ne doit pas être ajouté // S'il reste de la place dans ce quadtree, y ajouter l'objet if (points.size < QT_NODE_CAPACITY) { points.append(p); return true; } // Sinon, subdiviser le quadtree, puis ajouter le point au nœud qui l'acceptera if (northWest == null) subdivide(); if (northWest→insert(p)) return true; if (northEast→insert(p)) return true; if (southWest→insert(p)) return true; if (southEast→insert(p)) return true; // Sinon, le point ne peut être inséré, pour une raison inconnue (cela ne devrait jamais arriver) return false; } }

Bir bölgede ara

Aşağıdaki yöntem, bir "arama kutusu" içindeki tüm noktaları bulur.

class QuadTree { ... // Trouver tous les points apparaissant à l'intérieur d'une «zone de recherche» function queryRange(AABB range) { // Préparer le tableau de résultats Array of XY pointsInRange; // Tout interrompre si la «zone de recherche» n'intersecte pas ce quadrant if (!boundary.intersectsAABB(range)) return pointsInRange; // liste vide // Vérifier les objets à ce niveau de quadrant for (int p := 0; p < points.size; p++) { if (range.containsPoint(points[p])) pointsInRange.append(points[p]); } // Terminer ici, s'il n'y a pas d'enfant if (northWest == null) return pointsInRange; // Sinon, relancer la recherche sur les 4 enfants et ajouter les points trouvés pointsInRange.appendArray(northWest→queryRange(range)); pointsInRange.appendArray(northEast→queryRange(range)); pointsInRange.appendArray(southWest→queryRange(range)); pointsInRange.appendArray(southEast→queryRange(range)); return pointsInRange; } }

Ayrıca görün

Notlar ve referanslar

Notlar

  1. Hanan Samet  (içinde) ve Robert Webber. "Dörtlü Ağaçları Kullanarak Bir Çokgen Koleksiyonunun Saklanması". Grafiklerde ACM İşlemleri Temmuz 1985: 182-222. InfoLAB . Ağ. 23 Mart 2012
  2. Tomas G. Rokicki, "  Uzay ve Zamanın Sıkıştırılması İçin Bir Algoritma  " ,1 st Nisan 2006(erişim tarihi 20 Mayıs 2009 )
  3. Henning Eberhardt, Vesa Klumpp, Uwe D. Hanebeck, Verimli Doğrusal Olmayan Durum Tahmini için Yoğunluk Ağaçları , 13. Uluslararası Bilgi Füzyonu Konferansı Bildirileri , Edinburgh, Birleşik Krallık, Temmuz 2010.

Genel referanslar

  1. Raphael Finkel ve JL Bentley , "  Dörtlü Ağaçlar: Kompozit Anahtarlarda Geri Alma İçin Bir Veri Yapısı  ", Acta Informatica , cilt.  4, n o  1,1974, s.  1–9 ( DOI  10.1007 / BF00288933 )
  2. Mark de Berg , Marc van Kreveld , Mark Overmars ve Otfried Schwarzkopf , Hesaplamalı Geometri , Springer-Verlag ,2000( ISBN  3-540-65620-0 )Bölüm 14: Dörtlü Ağaçlar: s.  291–306 .
  3. Hanan Samet ve Robert Webber , "  Dörtlü Ağaçları Kullanarak Çokgen Koleksiyonunun Saklanması  " ,Temmuz 1985( 23 Mart 2012'de erişildi )

Dış bağlantılar