java - 查找距点一定距离内的所有 3D 对象

Question

我有一组对象(我们称之为 points )，其中包含它们在某个确定空间内的位置的 x- y- 和 z- 分量。我想对 points 中的对象之间的交互进行建模但是，除非我能够快速找到该集合中与该集合中的某个对象的距离小于一定距离的对象，否则我无法这样做。

这无疑听起来有点不清楚，所以让我换一种说法:如果 points 中的第一点有坐标<x, y, z> ，我想找出 points 中的哪些对象与第一个点的距离小于[某个任意值]。

我正在考虑用 Java 实现 R-Tree 来完成此任务，但我觉得这是一个很常见的问题，因此存在更简单的解决方案。如果没有，我希望对查询 R 树以查找一定距离内的对象的方法进行简单解释 x来自树中的一个对象，其中 x已经是已知的了。

编辑:请注意这些对象的位置值将会改变

Answer 1

R* 树是一个非常好的数据结构，特别是当点发生变化时。实际上，它是为变化而设计的。

k-d-tree 更简单，但它不能很好地支持更改。它专为一次性批量施工而设计。

但是，由于您的数据只是三维的:如果您的数据足够小以适合内存，并且 x、y、z 的最大值和最小值已知，则可以使用八叉树或简单的网格可能是您需要的简单性和性能的权衡。

特别是如果您事先修复了查询半径，则网格文件很难被击败。当您需要支持多个半径、窗口查询、最近邻查询等时，R* 树会变得很有吸引力。