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移动点的最近邻居搜索

回答

相关问题