kd-tree vs 3d yarıçap arama için octree

Question

Birkaç yarıçap noktası, kd-ağacı veya octree araması yapmak için hangi yapının daha iyi olacağını anlamaya çalışıyorum? Daha önce this question numaralı telefondan bahsedilmişti ancak yanıt yoktu. Bana öyle geliyor ki, octrees, yapraklar için sabit boyutlara sahip olduğundan, zaten kd-ağacı için ziyaret etmem gereken dalları hesaplayabileceğinden, yarıçap kaplanana kadar dalları tekrarlamak zorunda kalıyorsunuz.

Answer 1

3D ve sabit sorgu yarıçapı için, octrees iyi bir seçimdir. Disk üzerinde çalışmanız gerekirse, diğer veri yapıları daha iyi olabilir, ancak k-d-ağacı da burada parlamaz.

Neden her ikisini de deniyorsunuz ve verileriniz için hangisinin daha iyi çalıştığını görmüyorsunuz?

Answer 2

Projemde aralık araması için bir Octree kullanıyorum ve verimli çalışıyor ve uygulanması kolaydır. Yine de KD-Tree ile karşılaştırdım. Benim bilgime göre, bu işlem için kd ağaçlarındaki en kötü durum zaman karmaşıklığı üç boyutlu veriler için O (n^(2/3)) iken, Octree sadece O (n) 'yi garanti edebilir. Dolayısıyla, en kötü zaman karmaşıklığını önemsiyorsanız, KD Ağacı'nı seçin. (En kötü zaman karmaşıklığı umurumda değil, eğer veri kümemde bilirsem bu asla gerçekleşmeyecek.)

Answer 3

Bu amaçla hem kişisel hem de kesin olarak uygulamıştım. Octree ile daha verimli sonuçlar elde etmeyi çok daha kolay buldum. Daha kolay diyorum çünkü bu türden ince ayrımlarla düşünüyorum, aslında uygulayıcı hakkında veri yapısından çok daha fazlası var. Ama çoğu insan için, octree'yi optimize etmek için daha kolay bir zamanınız olacağını düşünüyorum. Bunun nedenlerinden biri, K-D ağaçlarının bir kerede bir boyuta bölünen ikili ağaçlar olmaları nedeniyle daha derinden daha derin olmasıdır. Bu daha derin bir doğa, yaprakta, ağaçtan aşağı doğru tek bir açık yol ile bir ışın/üçgen kesişimi gibi hassas bir eşleştirme elemanı arıyorsanız faydalı olabilir. Derin bir ağaç, dikkatli bir şekilde bölünmüş olduğunda, arama kalitesi fikriyle eşleştiğinde faydalıdır.

Ağacın yukarı ve aşağı doğru gitmesine neden olan çoğu yarıçap içinde en yakın noktayı araştırıyorsanız, dikkatle bölünmüş bir ağaca sahip olmak çok yararlı değildir. ebeveyne ve ebeveynlere kardeş olmak için ebeveyn. Herşeye önbellek dostu bir şekilde erişebilmeniz için biraz daha kolay olmasına yardımcı olur ve tüm 8 çocuğunuzu komşu olarak saklamak gibi bir octree önbellek dostu yapabilir, bu noktada bunu yapabilirsiniz:

struct OctreeNode 
{ 
    // Index of first child node. To get to the 4th node, 
    // we just access nodes[first_child+3], e.g. 
    int first_child; 
    ... 
}; 

Her neyse, bu iki seçenek ise, bu durumda octree için oy kullanıyorum. Ayrıca, bu tür yakınlık araştırması için, octree'nin çok derin olmasını istemezsiniz. Daha sığ bir ağaç ile en iyi noktadan daha fazla noktaya bakmamız gerekse bile, bu ağacın yukarı ve aşağı doğru gitmesinden daha iyi olabilir. Bir yaprakta sakladığınız noktalar bitişik ise yardımcı olur. Ağacınızı oluşturduktan sonra bir post-process ile bunu potansiyel olarak gerçekleştirebilirsiniz.

Her iki çözümle de, kardeşi düğümlerine bakmak zorunda olduğunuzu unutmayın. Bir noktaya en yakın nokta, mutlaka aynı yaprak düğümünde bulunan değil. Ayrıca, 3-boyutlu bir kılavuzun, verilerinizin niteliğine bağlı olarak, aslında bu amaç için oldukça uygun olabileceği bazı durumlar da vardır, çünkü 3D ızgarada, çocuktan ebeveyne, kardeşe gitmekten asla rahatsız olmanıza gerek yoktur. 3D ızgaralar, bellek kullanımında patlayıcı görünebilir, ancak bir 32-bit dizinine kadar bir ızgara hücresinin bellek yükünü azalttığınızda bunların mutlaka olması gerekmez. Böyle bir durumda, 100x100x100 ızgara 4 megabayttan daha az alır.