基於空間代理的建模的數據結構

Question

在二維空間模擬中跟蹤代理的一些好的數據結構是什麼？

我見過一些四叉樹（我知道）和kd-trees（我不太明白）。

我正在尋找代理人可以有效地說的事情，「我知道我的位置，並且我想知道哪些代理人在我附近（在我的某個範圍內）。」

示例（僞代碼很好）將不勝感激。

我正在Java工作。

Answer 1

我發現一種叫做Bucket PR Quadtree。

Answer 2

嗯，我不確定它是如何實現的，但MASON toolkit使用的離散化算法將代理相互靠近放置在散列表的同一個「桶」中。它使得查詢速度非常快，因爲只有少數這些桶必須針對每個查詢進行檢查。

你的最好的事情可能是看看這裏的源代碼： http://code.google.com/p/mason/source/browse/trunk/mason/sim/field/continuous/Continuous2D.java?r=529