I have a point cloud that consist of nearly 20000 points. We consider a point in the point cloud. I want to determine the set of points that are inside an spherical space around each point within the a predefined radius. In the image below there is a very clear illustration of what I mean, [A point with a spherical space around it [Gross et al. (2007)][1]] 1
I have written the simplest way to find each set of point by using two loops. Here is the function,
void FindPointsInsideSphere(std::vector<Point>& points, double radius)
{
for (int i = 0; i < points.size(); i++)
{
for (int j = 0; j < points.size(); j++)
{
if (i != j && Distance(points[i], points[j]) < radius)
{
points[i].Sphere.push_back(points[j]);
}
}
}
}
The issue here is that the proposed algorithm is very time consuming. I wanted to know if there are any suggestions that can accelerate the process.
There was a similar question on stackexchange: https://cstheory.stackexchange.com/questions/17971/search-for-all-nearest-neighbors-within-a-certain-radius-of-a-point-in-3d
After discussing with @AMA and googling I realized that both KDTree and uniform grids improve the time complexity of brute force.
Radius search complexity:
O(log(n) + k)
Where k is the approximate number of neighbours inside the sphere.
I've never personally tried this approach but as @AMA pointed it has better time complexity than kdtree query.
After a quick google search I found this implementation on github.
Radius search complexity:
O(sqrt(n) + k)
Where k is the approximate number of neighbours inside the sphere.
The best open source implementation the KDTree search FLANN, wich comes with multiple languages support.
Take a look at the manual in section: 3.1.4 flann::Index::radiusSearch
If you want to implement this by yourself you can take a look at the source code in github for inspiration.