通過距離查找附近xyz點的最佳數據結構？

我正在使用Python，但我想這不會影響問題本身。通過距離查找附近xyz點的最佳數據結構？

我正在做一個遊戲，我需要存儲實體，其中每個實體都有一個[x，y，z]的世界。我需要能夠運行「Y點的X歐氏距離內的所有實體」。

這些實體將移動相當頻繁。

什麼是最有效的方式來存儲實體儘可能快？

2013-06-21 Salis

rel：http://stackoverflow.com/q/11053820/989121 – georg

這就是所謂的地理空間搜索，您可以在數據庫和編程語言中找到它的各種實現。 – DhruvPathak

作爲已經建議的替代方案，如果您不需要精確的距離，也可以使用spatial hashing，這很容易實現。

總之，您必須將您的世界視爲一個網格，其中網格中的每個單元格將對應於散列表中的一個存儲桶。由於您的實體經常移動，因此您可以在每個新框架上清除並重建整個表格，並根據實體的位置將實體放到相應的桶中。然後，對於任何給定的實體，您只需檢查附近的單元格並獲取實體列表。

2013-06-21 10:34:06 Pin

您可以使用kd-tree（鏈接有照片和代碼和示例）或octree（該鏈接是您可以使用的C++類模板）。實際使用可見於this open-source game engine

2013-06-21 07:59:40

你能否詳細說明一下，或者將我鏈接到解釋如何在這裏應用它的東西？我認爲我理解結構（原則上，你將實體位置分成網格，然後消除除了附近的所有網格之外的所有網格？我不確定），但我怎樣才能將數據實際應用到結構中？ – Salis

有一個鏈接到八叉樹結構的維基頁面，並有鏈接在那裏實現（現在鏈接很好，以前我粘貼了一個錯誤的鏈接）。 –

我已更新答案，謝謝。 –

回答