如果您只有一个查询，那么此问题是固定的O（n），其中n是无论多少都将得到的点数。
如果您有多个查询，则比这个问题更值得探讨，但是它的解决方案比仅最邻近的搜索要复杂。请参阅本文：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.3191&rep=rep1&type=pdf
最近邻搜索问题有很多工作，所以我想知道是否要执行fixed radius range search，是否可以将这些算法用于最近邻搜索？
也许我可以一遍又一遍地进行第k个近邻搜索，直到找到超出半径范围的点，但我想这可能会造成很多浪费。
不仅“最近的邻居搜索问题有很多著作，而且有很多问题要问您的问题。最重要的是尺寸数。
如果不确定尺寸的重要性，请确保检查我的answer。>
高维空间
假设您的点位于高维空间中，则应选择Locality-Sensitive Hashing (LSH) 。此算法的一个不错的实现是E²LSH。如果您想自己实现或更好地了解会发生什么，它们还提供slides。请注意，E²LSH解决了R邻域问题的随机形式，他们将其称为（R，1-δ）-邻域问题，其中δ与逼近有关，正如他们在manual中提到的。]
您还可以检查我有关LSH here的答案。我已经在C ++中使用过它，强烈建议将它用于您要执行的固定半径搜索！
低维空间
] >>使用CGAL的spatial searching。在这种情况下，我在C ++中使用了很多次。同样，如果您想自己实现，则可以在他们拥有的不错的文档中找到大量信息，并进行相关的Google查询。
顺便回答一下，所以你得到了我的+1。 ：）
如果您只有一个查询，那么此问题是固定的O（n），其中n是无论多少都将得到的点数。
如果您有多个查询，则比这个问题更值得探讨，但是它的解决方案比仅最邻近的搜索要复杂。请参阅本文：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.3191&rep=rep1&type=pdf
以d作为尺寸数，以r作为半径，我知道至少可以使用两种不同的方法：
想象问题空间在超立方体中被大小为s的网格划分为s = r / sqrt(d)。
关于s = r / sqrt(d)的有趣之处在于，该大小的超立方体内的任何两个点都必须保证等于或小于r。
您可以对网格划分进行计数，以便每个超立方体都可以通过其角之一的索引所形成的元组来标识。这些索引元组可用作哈希结构（空间哈希）的键。
现在，这是困难的部分，您必须注意，对于网格A的任何超立方体，都有一组相邻的超立方体N = (N1, N2, ...)，它们与给定超立方体的最小距离等于或小于给定半径在几何上，它们看起来像一个超球体。您可以将集合N的元素表示为相对于A的网格索引的增量。请注意，这些索引增量仅取决于d。
例如，在二维情况下，您具有以下几何结构：
NNN index deltas: (-1, 2) ( 0, 2) ( 1, 2) NNNNN (-2, 1) (-1, 1) ( 0, 1) ( 1, 1) ( 2, 1) NNANN (-2, 0) (-1, 0) ( 0, 0) ( 1, 0) ( 2, 0) NNNNN (-2, -1) (-1, -1) ( 0, -1) ( 1, -1) ( 2, -1) NNN (-1, -2) ( 0, -2) ( 1, -2)所以，您已经拥有实现对超球体内的点进行有效搜索所需的全部：
使用包含它们的超多维数据集的索引元组作为键，将输入点推入空间哈希。
给定点p，搜索的方法是确定放置它的超立方体A，然后使用索引增量集，获取可能包含点的邻居超立方体N的集合比r更近。
从空间哈希中检索属于超立方体N的点，并检查哪些点足够接近p。
可以执行一些额外的优化，因为不检查A中的点，因为它们保证都足够接近。可以基于p相对于A的位置执行N的预过滤。
请注意，选择s = r / sqrt(d)在具有小的超立方体和不太大的集合N之间提供了很好的折衷。
每次您在树上下降一层时，您都会检查树代表的空间是否与查询超球面相交。如果是这样，则继续进行下去，否则将其从搜索中完全丢弃。
一个简单的解决方案是在sklearn.neighbors.KDTree中使用query_radius函数：
格式为：
query_radius(X, r, return_distance=False, count_only=False, sort_results=False)
如果您只有一个查询，那么此问题是固定的O（n），其中n是无论多少都将得到的点数。
如果您有多个查询，则比这个问题更值得探讨，但是它的解决方案比仅最邻近的搜索要复杂。请参阅本文：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.3191&rep=rep1&type=pdf
以d作为尺寸数，以r作为半径，我知道至少可以使用两种不同的方法：
一个简单的解决方案是在sklearn.neighbors.KDTree中使用query_radius函数：