kd-tree vs三維半徑搜索的八叉樹

Question

我試圖找出哪個結構會更好地做點，kd樹或八叉樹的幾個半徑搜索？它已在this question中提及，但沒有答案。在我看來，由於八叉樹具有固定大小的葉子，因此可以計算出我需要訪問的分支，而對於kd樹，您必須迭代訪問分支，直到覆蓋半徑。

Answer 1

對於3D和固定查詢半徑，八叉樹是一個不錯的選擇。如果你需要在磁盤上工作，其他數據結構可能會更好，但k-d-tree也不會在這裏發光。

爲什麼不嘗試兩種方法並查看哪種方法對您的數據更好？

Answer 2

在我的項目中，我使用八叉樹進行範圍搜索，它的工作效率很高，並且易於實現。雖然沒有把它與KD-Tree比較。 據我所知，kd樹中這種操作的最壞情況時間複雜度是三維數據的O（n ^（2/3）），而Octree只能保證O（n）。所以如果你關心最壞的時間複雜度，選擇KD樹。 （我不在乎最糟糕的時間複雜性，如果我知道在我的數據集中這絕不會發生。）

Answer 3

我已經爲此目的實現了個人化和精確化，將爲八叉樹投票。我發現用八叉樹獲得更高效的結果要容易得多。我說比較容易，因爲我認爲這些微妙的區別，更多的是關於實現者而不是數據結構。但我認爲對於大多數人來說，你會更容易優化八叉樹。

其中一個原因是因爲K-D樹本質上更深層次是二叉樹一次在一個維度上分裂。如果您在葉子上尋找精確的匹配元素，比如光線/三角形交叉點以及沿着樹的單一明確路徑，那麼這種更深的性質可能會有所幫助。當一棵深度分割的樹匹配搜索質量的想法時，它非常有用。

如果您在最大半徑範圍內搜索最近的點，那麼最終花費大部分時間只是在樹上上下移動，從葉到樹父母同胞到祖父母到同胞兄弟姐妹等等。如果你可以以緩存友好的方式訪問所有東西，並且你可以很容易地創建一個八叉樹緩存友好的東西，比如連續存儲所有8個孩子，那麼你可以這樣做：

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; 
    ... 
}; 

因此無論如何，如果這是兩種選擇，那麼我在這種情況下投票選八叉樹。同樣對於這種類型的鄰近搜索，您不一定希望八叉樹太深。即使我們不得不用更淺的樹來觀察更多的點而不是更好的點，這可能比不得不在樹上上下很多。如果你存儲在葉中的點是連續的，它確實有幫助。在完成構建樹之後，您可以通過後續過程來實現這一目標。

注意這兩種解決方案，你必須看看兄弟節點。到一個點的最近點不一定是駐留在同一個葉節點中的點。也有一些情況下，根據數據的性質，只有三維網格實際上可以非常適合此目的，因爲使用3D網格，您甚至不必從孩子到父母再到兄弟姐妹。 3D網格在內存使用中看起來很具爆炸性，但如果您將網格單元的內存開銷降低到32位索引，則它們不一定非要。在這種情況下，100x100x100的網格不到4兆字節。