找到所有点半径为r的球体绕任意坐标 [英] Find all points in sphere of radius r around arbitrary coordinate

问题描述

我正在寻找，对于与已知高度，宽度和长度的空间中，给定一个固定的半径R的高效算法，和点的列表N，与该空间的3维坐标，会发现所有的点内对电网的任意点的固定半径R。这个查询将进行多次与不同点，因此昂贵的pre-处理/排序步骤，以换取快速的查询可能是值得的。这是一个有点我工作的一个应用程序的一个瓶颈工序，因此任何时候，我可以切断它是非常有用的。

I'm looking for an efficient algorithm that for a space with known height, width and length, given a fixed radius R, and a list of points N, with 3-dimensional coordinates in that space, will find all the points within a fixed radius R of an arbitrary point on the grid. This query will be done many times with different points, so an expensive pre-processing/sorting step, in exchange for quick queries may be worth it. This is a bit of a bottleneck step of an application I'm working on, so any time I can cut off of it is useful

事我已经试过到目前为止：

Things I have tried so far:

-The天真的算法，遍历所有点和计算距离

-The naive algorithm, iterate over all points and calculate distance

-Divide空间与长度r的立方体网格，并把点到这些。通过这种方式，对于每一个点，我只需要不断查询最相邻水桶。这有显著加速

-Divide the space into a grid with cubes of length R, and put the points into these. That way, for each point, I only have to ever query the immediate neighboring buckets. This has a significant speedup

-I've尝试使用曼哈顿距离为启发。即，水桶内，计算距离的任何点之前，使用曼哈顿距离过滤掉那些不可能是内半径R（即，那些与℃的曼哈顿距离; = SQRT（3）* R）。我认为这将提供一个加速，因为它仅需要加法，而不是乘法，但它实际上是由一点点

-I've tried using the manhattan distance as a heuristic. That is, within the buckets, before calculating a distance to any point, use the manhattan distance to filter out those that can't possibly be within radius R (that is, those with a manhattan distance of <= sqrt(3)*R). I thought this would offer a speedup, as it only needs addition instead of multiplication, but it actually slowed the program down by a little bit

编辑：比较的距离，我用的平方距离，以消除不必使用sqrt函数

To compare the distances, I use the squared distance to eliminate having to use a sqrt function.

显然，将会对我多少能加快这一些限制，但我可以用的东西有什么建议现在就试试。

Obviously, there will be some limit on how much I can speed this up, but I could use any suggestions on things to try now.

不，它可能在重要的算法级，但我在C工作。

Not that it probably matters on the algorithmic level, but I'm working in C.

推荐答案

您可能会得到一个速度受益于一个的 kd树有三个方面。这会给你searchs在O（log n）的分期时间。

You may get a speed benefit from storing your points in a k-d tree with three dimensions. That will give you searchs in O(log n) amortized time.

这篇关于找到所有点半径为r的球体绕任意坐标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！