algorithm - CUDA Thrust 查找近邻点

Question

在我的问题中，域中有 N 个点，它们以某种方式随机分布。对于每个点，我需要找到距离小于给定 double float DIST 的所有相邻点。在 Thrust 中有一种有效的方法可以做到这一点吗？在串行中，我会使用邻域表并希望实现大约 O(n) 而不是 O(n^2) 的朴素算法。
我找到了 2D 桶排序的推力示例，它非常适合我的问题的第一部分。但这还不够，因为对于每个桶，我需要找到相邻桶中的所有点，然后计算它们的距离，看看是否有任何点小于 DIST。查找邻居和计算距离应该相对容易，但是将那些符合条件的点添加到结果数组对我来说似乎很难在 Thrust 中实现。重述这个特定问题的一种方法是——我有两个二维数组 A1 和 A2，列号代表二维桶的索引，每列都有不同数量的元素，这些元素是我的点的索引。 A1 的 column(i) 中的每个元素将与 A2 的 column(i) 中的每个元素形成潜在对，并且所有符合条件的对都应记录到结果数组中。我可以使用 CUDA 内核并分配大量可能未使用的内存作为解决方法，但这是我最不想做的事情。提前致谢。

Answer 1

完整的解决方案超出了单个 Stack Overflow 答案的范围，但是在这个存储库中讨论了如何使用 Thrust 构建 2D 空间索引:

https://github.com/jaredhoberock/thrust-workshop