java - 在一个大的、稀疏的、嘈杂的体积中找到靠近的点

Question

提前对文字墙表示抱歉——自从我完成编程以来已经有一段时间了，可能有更好的术语来表达我的意思。搜索了我能想到的所有内容，但没有在网站上找到任何相关问题，但也许我们可以找到更好的条款，所以我们将不胜感激!

我正在尝试提高查找间隔不超过一组的对象组的性能 taxicab/Manhattan distance . 所以，假设我的距离是“x”，点“a”是点“b”的 x 个单位，点“b”是点“c”的 x 个单位，点“c”是 x+3 个单位从“a”点开始；我应该将 a、b 和 c 标识为一个组，以及其中任何一个 x 单位内的任何对象(依此类推)。

我已经确定了几种用于查找这些组的简单算法，但我认为性能可以更好。聚类算法似乎在这里应该是相关的，但我一直无法找到适合我的问题的算法。我也不确定我是否尽可能有效地存储了数据——现在我只是在处理静态数据，这样我就可以在开始之前将它复制成我需要的任何形式；但是将来我希望有一个可以有效处理添加和删除点的实现。以下是详细信息:

• 我从两个无序的 ArrayLists 对象开始，它们的许多属性中有一个唯一的整数坐标 (x,y,z) 三元组。
• 物体稀疏地散布在一个非常大的体积(比如 5 亿立方单位)上，我设置的距离相对较小(<15 个单位)
• 我不需要找到大小为 1 的组，所以有很多“噪音”。在我的数据中，三人以上的团体非常罕见。
• 超过 90% 的时间附近的对象会在相似的时间添加到 ArrayLists，所以如果可以的话，我想利用这一事实。
• 另一个有用的事实是，一个维度 (y) 的范围大约是其他两个维度的 1/10，因此二维算法可能是一种更快的开始方式，如有必要，稍后会拆分二维组。
• 找到这些组后，我需要访问组中的每个对象以进行函数调用，因此我需要识别对象，而不仅仅是坐标。

我如何才能改进仅使用偏移网格遍历 ArrayList 两次然后重新分析我创建的组的性能？我的语言是 Java，但算法比特定类型更重要和图书馆(尽管我也会带走那些!)。

Answer 1

我认为您正在尝试实现 Range search 的特例.也许将您的数据存储在 k-d tree 中会有用的。至少您应该能够轻松提取位于您正在搜索的其中一个点周围的超立方体中的点。然后你可以检查他们的距离是否符合要求。

另请参阅:“Fixed-Radius Near Neighbors and Geometric Basics ”了解一些解决方案。