找到所有3D对象在一定距离点

Question

我有一个集中的对象(让我们叫它 points)含有x-y和z组成的自己的立场内的一些明确的空间。我想模型之间的相互作用的对象 points, 然而，我不能这样做，除非我可以很快找到对象的设置，都小于一定距离的对象之一，在这集中。

这无疑听起来有点不清楚，所以让我把它放的另一个方式：如果第一点 points 有坐标 <x, y, z>, 我想找出其中的对象 points 有一段距离小于[一些任意的价值]从第一点。

我是在考虑实施一个R-树上这样做，但我觉得好像这是一个共足够的问题，一个简单的解决方案的存在。如果没有一个，我会理解一个简单的解释的方法，通过这种方法的一种查询一个R-树，以便找到对象是在一些距离 x 从一个目的在树里 x 是已知的。

编辑：注意位置的价值观的这些对象会被改变

Answer 1

r * -tree是一个非常好的数据结构，特别是当点变化时。它专为实际而设计的变化。

k-d-tree更简单，但它不支持变化很好。它专为一次性批量建设而设计。

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

特别是如果您预先修复了查询半径，则难以击败网格文件。r * -trees在需要支持多个半径，窗口查询，最近的邻居查询和所有此时获得有吸引力。

Answer 2

编辑：方=立方(但是想象它在2D空间也许会更好，那么你可以把它变成3D易)

我想我想我解决了它。然而，这仅仅是"我"的解决方案，我没有参考。

你创建的类"方"，其中有位置、宽度和列表中的点对象。

所有方将储存列或哈希的基础上他们的位置，使它们可以很快，如果你知道的位置你的目的。

所有的广场将分发定期，所以自的观点"点实例"-你不必要知道所有的现有方块图在固定时间在这个属于你。(例如：我知道有方带宽度40和他们分布距离的20.我在位置10001，所以我知道属于我到广场中的位置9980和10000)

方将通过每个其他，因此一点就可以在更广场。

当你做一些事情，对于每个点，你只的检查点，它们是储存在广场这一点。当然方必须足够大，并越过了足以实现自己的目标。

当点移动，他们是负责登记和注销成的正方形。

---

1D例如：

类： Line segment 和 Point

Attrributes:

Line segment : int position, List<Points> points

Point : int position, List<LineSegment> lineSegments

我想进行交互只有点距离的20.

所以我创造的实例 Line segments 与宽度40和我把他们一一个在距离的20.

因此，他们将在位置0, 20, 40, 60 ....

第一一个将复盖的区域的0-40，第二20至60等。

我把它们放进入阵列，并与已知立场，我能够访问它们迅速： arrayOfLineSegments[position/20]

当我创建一点上，我加入他的 line segments 它属于。

当我更新，每个点只与分在lineSegments.

当我移动一点，它注册和注销lineSegments它属于。

Answer 3

可以使用for循环来检查对象数组。

使用以下公式：d = sqrt[(x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2]

x1，y1，z1是生成的第一点，x2，y2，z2是您要检查的对象的点。这将检查您的已知点VS所有其他点。如果距离（d）小于您所需的距离，则为Points，那么无论您要做什么程序要做。