2D移動點的最近鄰居搜索

爲此，我需要搜索每個2D點的最近鄰居。但是，我不能使用像k-d樹這樣的靜態數據結構，因爲點總是在移動...

什麼是能夠實現這個目標的好（簡單）數據結構/庫？我正在使用C++ ...

2011-08-07 Jan Rüegg

你可能會從http://stackoverflow.com/questions/6871682/approximate-nearest-neighbour-algorithm-for-moving-bodies –

也許你想嘗試一個四叉樹或空間索引？ k-d樹有什麼問題？基本上當羊羣/點有邊緣時，可以跳過檢查與遠處邊緣的碰撞。空間索引可以是四叉樹，r-樹，kd-tree或hilbert r-樹。一個更好的答案可以在這裏讀到：Approximate, incremental nearest-neighbour algorithm for moving bodies

「也就是說，遞歸分區‘世界’成爲圖形有四個子節點每個樹就可以快速檢查哪些對象是全世界的一個特定的正方形內，並丟棄。通常用於提高遊戲中碰撞檢測性能的非常有效的剔除技術。「

來源

2011-08-07 08:25:27 Bytemain

得到一些想法是不是kd樹（或四叉樹，就此而言）靜態的？意思是在所有點移動之後，你必須在每一步中重建它？ –

四叉樹的想法是將二維複雜度降低到一維複雜度。當你遞歸遍歷樹深度優先或寬度優先時，填充完整樹就變成了一個簡單的任務？ – Bytemain

我想四叉樹可以工作，有點。然而，簡單地遍歷所有鄰居似乎對我來說足夠快... –

有人有studied這個問題。在這個領域尋找工作時，重要的關鍵字是動力學。

來源

2011-08-07 10:59:39 carlosdc

2D移動點的最近鄰居搜索

回答

相關問題