我在 3 维空间中有很多点（+100,000）。我需要使用最近邻和范围查询。首先我使用了 kdtree (k=3) 但每个点都有一个速度属性。它们的位置不是静态的，它们会改变它们的位置。问题从这里开始。使用旧位置进行最近邻和范围查询很容易。但我必须根据他们的速度计算他们的新位置。在计算出他们的新位置后，我必须找到最近的邻居并在范围内搜索。
每次这些点改变它们的位置时，我都必须更新 kdtree，但这很昂贵。它让我慢下来。对于这种情况，您有什么建议或有更好的数据结构吗？
问问题
148 次
1 回答
2
八叉树或八键可以更快。八键通常使用莫顿曲线或希尔伯特曲线。它减小了尺寸并填充了空间。它经常用于地图应用程序。要在 3d 中找到方向，格雷码可以帮助找到正确的象限。这是一个关于移动对象的有趣线程：http: //xboxforums.create.msdn.com/forums/p/59841/368276.aspx。它推荐四叉树、链表或三叉树。
于 2013-08-28T10:18:36.213 回答