我想进行一些群集模拟，就像这里描述的那样。
为此，我需要搜索每个2D点的最近邻居。但是，我不能使用静态数据结构，例如k-d树，因为这些点始终在移动...
有什么好的（易用的）数据结构/库可以实现这一点吗？我正在使用C++...
移动点的2D最近邻搜索
7
- Jan Rüegg
1
你可能会从此链接中获取到一些灵感：https://dev59.com/-Gw15IYBdhLWcg3wCXOJ - Don Reba
2个回答
2
也许您可以尝试使用四叉树或空间索引？使用k-d树有什么问题？基本上，当拥有群/点边缘时，您可以跳过检查远离边缘的碰撞。空间索引可以是四叉树、r树、kd树或希尔伯特r树。更好的答案可以在此处阅读：Approximate, incremental nearest-neighbour algorithm for moving bodies
也就是说，将“世界”递归地分割成每个具有四个子节点的图形。然后，该树可以快速检查哪些对象位于世界的特定正方形内并丢弃其余部分。这是一种非常有效的修剪技术，通常用于提高游戏中碰撞检测的性能。
- Micromega
3
k-d树（或四叉树）不是静态的吗？这意味着在每个步骤中，所有点都移动后，您必须重新构建它，对吗？ - Jan Rüegg
四叉树的思想是将二维复杂度降低到一维。当您递归地深度优先或广度优先遍历树时，填充整个树变得非常简单。 - Micromega
我猜四叉树可能会有用，但是对我来说，仅仅迭代遍历所有邻居似乎已经足够快了... - Jan Rüegg
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接