我在三维空间中有很多点（+100000）。我需要使用最近邻居和范围查询。首先，我使用了kdtree（k=3），但每个点都有一个速度属性。他们的位置不是一成不变的，他们会改变自己的位置。问题从这里开始。使用它们的旧位置进行最近邻居和范围查询很容易。但我必须根据它们的速度来计算它们的新位置。我必须找到最近的邻居，并在计算出他们的新位置后在范围内进行搜索。
每次点改变它们的位置，我都必须更新kdtree，但这是昂贵的。它让我慢下来。对于这种情况，你有什么建议吗？或者有什么更好的数据结构吗？
八叉树或八叉键可以更快。八进制通常使用Morton曲线或hilbert曲线。它减少了尺寸并填充了空间。它经常在地图应用程序中使用。要在三维中找到方向，格雷码可以帮助找到正确的象限。这里有一个关于移动物体的有趣线索：http://xboxforums.create.msdn.com/forums/p/59841/368276.aspx.建议使用四叉树、链表或三叉树。