c++ - 二维最近邻搜索移动点

Question

我想做一些植绒模拟，如此处所述。

为此，我需要搜索每个 2D 点的最近邻居。但是，我不能使用像 kd 树这样的静态数据结构，因为点总是在移动......

什么是能够实现这一目标的好（简单）数据结构/库？我正在使用 C++ ...

score 5 · Accepted Answer

5

人们研究过这个问题。在这个领域寻找工作时，重要的关键词是动力学。

于 2011-08-07T10:59:39.187 回答

score 1 · Accepted Answer

也许您想尝试四叉树或空间索引？kd树有什么问题？基本上，当边缘有羊群/点时，您可以跳过检查与远处边缘的碰撞。空间索引可以是四叉树、r-tree、kd-tree 或 hilbert r-tree。可以在此处阅读更好的答案：移动物体的近似增量最近邻算法

“也就是说，递归地将“世界”划分为一个图，每个图有四个子节点。然后，树可以快速检查哪些对象在世界的特定方格内并丢弃其余对象。一种非常有效的剔除技术，通常用于提高游戏中的碰撞检测。”

2 回答 2