如何在c或C++中實現3d kDTree構建和搜索算法？

Question

如何在c或C++中實現3d kDTree構建和搜索算法？我想知道，如果我們有一個工作代碼遵循

Answer 1

我想推薦你兩個好介紹入手：

• "Introduction to k-d trees"
• "Lecture 6: Kd-trees and range trees"。

都需要開始編寫自己的實現，它們都提供了kd-trees背後的基本思想，簡短的可視化示例和代碼片段。

Answer 2

我發現Vlastimil Havran的出版物非常有用。他的Ph.d Thesis給出了一個很好的kd樹和遍歷算法的介紹。進一步的文章是關於幾個改進，例如如何在O(nlogn)中構建kd-tree。在不同的圖形庫中也有很多實現。你應該只是谷歌。

Answer 3

有關C中3D kd-tree實現的示例，請參閱kd3。它不是通用的圖書館，需要輸入數據的具體形式，但思想和方法應該是可轉移的。

披露：我是kd3的作者。

免責聲明：這是書面作爲證明的概念代碼爲現有的應用程序，因此不能作爲一般也不以及測試所應當的。錯誤報告/修復是受歡迎的。