Quadtree ve k-d ağacı

Kısaca: Quadtree ve k-d ağacı, bir konumun yakınındaki noktaları hepsini denetlemeden hızla bulmak için uzayı özyinelemeli bölgelere ayırır.

Biraz daha ayrıntılı: İkisi de uzamsal indeks yapılarıdır. “Bu dikdörtgende hangi noktalar var?” veya “Hangi nokta en yakın?” sorularını O(n) yerine yaklaşık O(log n)‘de yanıtlarlar.

Ayrıntılı

• Quadtree: Bir alanı dört eşit çeyreğe böler; gerekirse bunlar daha da bölünür. Oyunlarda (çarpışma denetimi), harita karolarında ve görüntü sıkıştırmada popülerdir. 3B varyantı octree’dir.
• k-d ağacı: Medyanda dönüşümlü olarak bir koordinata göre bölen (x, sonra y, sonra z, …) ikili bir ağaç. Düşük boyutlarda en yakın komşu araması için iyi.
• Sınır: Çok sayıda boyutta (yaklaşık 20+) avantajlarını kaybederler (“boyutluluk laneti”). O zaman yaklaşık yöntemli vektör indeksleri kullanılır.
• İlgili: Dikdörtgenler için R-ağaçları (PostGIS), haritalar için geohash.
• Hareketli nesneler: Ağaçtan çıkarılıp yeniden eklenmelidir; bu pahalı olabilir.

Ayrıca bak: İkili arama