Jan*_*egg 6 c++ 2d points nearest-neighbor data-structures
我想做一些植绒模拟,如这里所述.
为此,我需要搜索每个2D点的最近邻居.但是,我不能使用像kd树这样的静态数据结构,因为这些点总是在移动......
什么是一个好的(简单的)数据结构/库能够实现这一目标？我正在使用C++ ...
也许您想尝试四叉树或空间索引？kd树有什么问题？基本上，当有边缘/点时，您可以跳过检查与远处边缘的碰撞。空间索引可以是四叉树、r 树、kd 树或希尔伯特 r 树。更好的答案可以在这里阅读：Approximate, Incremental Closest Neighbor Algorithm for Moving Body
“也就是说，递归地将“世界”划分为一个图，每个图都有四个子节点。然后，树可以快速检查哪些对象位于世界的特定方块内，并丢弃其余对象。这是一种非常有效的剔除技术，通常用于提高游戏中的碰撞检测。”