代码之家 › 专栏 › 技术社区 › DuckQueen

在动态世界中,什么是用于查询的类似KDtree的数据结构?

updates 3d data-structures algorithm

1

DuckQueen · 技术社区 · 7 年前

所以我们有一个无界的3d世界,我们需要查询最近的点。然而,我们的点有标识符,并且一直在移动。支持数据点的数据结构类似KDtree\Octree。连续移动,在搜索+更新方面不会比3d情况下的KDtree\Octree复杂多少?

2 回复 | 直到 7 年前

1

Mauricio Cele Lopez Belon 7 年前

看看AABB树。这是一种主要用于游戏中快速碰撞检测的空间数据结构,也是CGAL、libigl和类似软件包中距离计算的最先进数据结构。此外,它还用于查找曲面上的最近点以及多面体中的点包容和最近邻。

最后,“动态AABB树”显然用于加速数千个刚体的物理模拟。

见:

http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/

2

1

TilmannZ 7 年前

PH-Tree (我自己的)。它的工作原理有点像具有超立方体寻址(非常快的更新和kNN搜索)的良好八叉树实现,但它也能很好地处理强集群数据,并且不能退化(最大深度等于值中的位数,通常为32或64)。假设只存储点(而不是形状/矩形),则可能需要 PhTree (对于整数数据)或 PhTreeF